My Programming Notes & Code Snippets

ORIGINAL PROBLEM   By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27.
5
9 6
4 6 8
0 7 1 5

I.e. 5 + 9 + 6 + 7 = 27. Write a program in a language of your choice to find the maximum total from top to bottom in triangle.txt, a text file containing a triangle with 100 rows.

---

This problem is popularly known as Euler's 67th problem . The logic is that starting from second last row, find the max of two adjacent values (of next row that) can be reached. Once we find the max, for each item of the row, add the max value to the row value. This will eliminate the last row. Now, we can work our way backwards, i.e to the top. Note that as we move upwards the triangles, the number of rows reduces, till we reach the top. Once we reach 2nd row from top, adding the top value to the max of two values,
of the 2nd row, we get our answer.





Solution
Place the text file "triangle.txt" in D drive  of your computer else change path accordingly in code. 
triangle.txt


SOURCE CODE in Java

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class Traingular_Sum {
private static int heightOfTriangle = 100;
private final String fileName = "D://triangle.txt";
private int[][] triangle;

public int maxValue() throws IOException {
readTriangle();

for (int i = Traingular_Sum.heightOfTriangle - 2; i>= 0; i--)
for (int j = 0; j<= i; j++) 
triangle[i][j] += triangle[i + 1][j] > triangle[i + 1][j + 1] ? triangle[i + 1][j] : triangle[i + 1][j + 1];

return triangle[0][0];
}

private void readTriangle() throws IOException {
triangle = new int[Traingular_Sum.heightOfTriangle][];

BufferedReader bufferedReader = new BufferedReader(new FileReader(fileName));
for (int i = 0; i < Traingular_Sum.heightOfTriangle; i++) {
triangle[i] = new int[i + 1];
String[] values = bufferedReader.readLine().split(" ");
for (int j = 0; j <= i; j++)
triangle[i][j] = Integer.parseInt(values[j]);
}
}

public static void main(String[] args) throws IOException {
System.out.println(new Traingular_Sum().maxValue());
}
}