Project Euler: Problem 81 – Path sum: two ways

Problem 81:

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331

Find the minimal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

Idea:

This problem is identical to problem 18, except in the form of a matrix instead of tree, and I want the minimal path instead of maximum path. I modified the algorithm I used for problem 18 to go either right or down (instead of down, or down and to the right). Tested it out and it worked.

int answer = -1;
int[][] tree = EulerUtils.readMatrix("Problem_81.txt");
EulerUtils.SumTreePath path = EulerUtils.matrixPath(tree,false);
answer = path.getSum();

Project Euler: Problem 67 – Maximum path sum II

Problem 67:

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 in triangle.txt (right click and ‘Save Link/Target As…’), a 15K text file containing a triangle with one-hundred rows.
 
NOTE: This is a much more difficult version of Problem 18 (and my attempt). It is not possible to try every route to solve this problem, as there are 299altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Idea:

Since I already did the work for this on problem 18, I decided to just do what I did for that problem, and sure enough, it worked rather quickly. On my computer, less than a second.

int answer = -1;

int[][] tree = EulerUtils.readMatrix("Problem_67.txt");
long start = System.currentTimeMillis();
EulerUtils.SumTreePath path = EulerUtils.treePath(tree,true);
long end = System.currentTimeMillis();
System.out.println("Start: "+start+"\tEnd: "+end);
answer = path.getSum();

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];
}