Project Euler: Problem 18 – Maximum path sum I

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 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];
}
Bookmark the permalink.

2 Comments

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *