**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.

374 246 8 593

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

**NOTE:** As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

**Idea:**

Before I noticed the note at the bottom, I *was* going to use a brute-force method. However, seeing recurring themes / patters in these problems (i.e. especially with prime numbers), and given the fact that this same problem occurs again in Problem 67, I figured might as well do it right the first time.

Thinking back to Problem 14, I realized I could make it more efficient by only computing the Collatz chain for a given number once, storing it, then just retrieving it whenever another number produced a chain that landed on that number. I figured I’d try a similar approach with this problem. However, I couldn’t do it from a top down approach (as that would be relatively equivalent to a brute-force method).

I decided to start from the base and work my way up, keeping track of the maximal path to the bottom for each node as I went. By the time I get to the top, I’ll have the maximal path to the bottom at that particular node (the starting node), which itself is the answer. I chose to use a custom data type to store not only the path length, but also a reference to the next node along the path to help me visualize the path from top to bottom, just in case I needed something like that for future problems.

int answer = -1; int[][] tree = readTree("Problem_18.txt"); //Reads the tree into a 2D array //In the form of a right triangle, max element is [i][i] per row //SumTreePath is a helper class that stores the current value, the total sum //thus far, and the reference to the next SumTreePath node Euler.SumTreePath path = treePath(tree,true); answer = path.getSum(); System.out.println("Answer: "+answer); //========================================== private static Euler.SumTreePath treePath(int[][] tree, boolean maximal) { Euler.SumTreePath[][] sumTree; boolean MAXIMAL = maximal; sumTree = new Euler.SumTreePath[tree.length][]; //initialize last row of sums sumTree[tree.length-1] = new Euler.SumTreePath[tree[tree.length-1].length]; for(int i = 0; i < tree[tree.length-1].length; i++) { sumTree[tree.length-1][i] = new Euler.SumTreePath(tree[tree.length-1][i],tree[tree.length-1][i], 0); } //ignore last row, already populated for(int i = tree.length-2; i >= 0; i--) { sumTree[i] = new Euler.SumTreePath[tree[i].length]; for(int j = 0; j < tree[i].length; j++) { //calculate cumulative sum of left choice int sum1 = tree[i][j] + sumTree[i+1][j].getSum(); //calculate cumulative sum of right choice int sum2 = tree[i][j] + sumTree[i+1][j+1].getSum(); Euler.SumTreePath sumTreeValue = new Euler.SumTreePath(tree[i][j],sum1,tree[i+1][j]); if(sum2 > sum1 && MAXIMAL) { sumTreeValue = new Euler.SumTreePath(tree[i][j],sum2,tree[i+1][j+1]); } sumTree[i][j] = sumTreeValue; } } //Return root node (current value, current sum, reference to next node) return sumTree[0][0]; }

Pingback: Project Euler: Problem 67 – Maximum path sum II | Pursuit of Intellectual Curiosity

Pingback: Project Euler: Problem 81 – Path sum: two ways | Pursuit of Intellectual Curiosity