Problem with Project Euler problem 18

• July 19th, 2013, 09:01 AM
sara_magdy
Problem with Project Euler problem 18
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle
this is my code but it gives 21 instead of 23 what is wrong in the code thanks
Code :

``` public static void main(String[] args) { List<List<Integer>> twoDim = new ArrayList<List<Integer>>(); int tempSum; int temp ;   String[] inputLines = {"3","7 4","2 4 6","8 5 9 3"};   for (String line : inputLines) { List<Integer> row = new ArrayList<Integer>();   Scanner s = new Scanner(line); while (s.hasNextInt()) row.add(s.nextInt());   twoDim.add(row); } int lines = twoDim.size();   for (int i = lines-2 ; i >= 0; i--) { for (int j = 0; j <= i; j++) {   twoDim.get(i).add(j,twoDim.get(i).get(j)+Math.max(twoDim.get(i+1).get(j),twoDim.get(i+1).get(j+1)));       } } System.out.println(twoDim.get(0).get(0)); }```
• July 19th, 2013, 10:43 AM
GregBrannon
Re: Problem with Project Euler problem 18
While your approach may be clever - then again, maybe TOO clever - it is not easy to understand or troubleshoot. I suggest you simplify the part of your program that chooses which value of the next row to add to the total so that you can add test lines to see what is going wrong. Think about how you'd do it in your head or with pencil and paper and code that.
• July 19th, 2013, 12:46 PM
helloworld922
Re: Problem with Project Euler problem 18
Choosing the maximum adjacent value is not guaranteed to give the maximum sum from top to bottom (as demonstrated here).

Here's a more obvious example:

1
1 1
2 1 1
1 1 8 9

Your approach will choose 1 + 1 + 2 + 1, but the best approach is 1 + 1 + 1 + 9.

If you want to solve this problem the "lazy way", you can use a brute force solver and try every path. As the problem hint suggests, this will work here, but not on problem 67.

There's a more efficient solution, though (as the problem suggested). As a hint, think about the problem going backwards.