Problem Description

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 5
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
… {data continues} …

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)

Analysis

To solve this problem and problem 67, which is much larger, start the search from the bottom to the top, adding the maximums along the way. This will “bubble” the maximum total to the top of the pyramid.

Let’s follow this technique, step by step, with the 4 row triangle example to show how this works.

3
7 5
2 4 6
8 5 9 3
OK, starting at the bottom,
We look at 8 and 5, pick the maximum, 8 in this case, and replace the 2 in the previous row with their sum 10.
We look next at 5 and 9, pick the maximum, 9, and replace the 4 in the previous row with their sum 13.
We look lastly at 9 and 3, pick the maximum, 9, and replace the 6 in the previous row with their sum 15.
Now our array looks like:
3
7 5
10 13 15

Let’s do it again. Take the larger of 10 and 13 and add it to 7 making 20.
Take the larger of 13 and 15 and add it to 5 making 20.
Now our array looks like:
3
20 20

At last we take the larger of 20 and 20 (yes, I know they’re the same) and add it to 3 making 23.
And our array looks like:
23
The maximum total path in the triangle.

Solution

Runs < 1 second in Perl.

my @rows = map { [split /s/] } <DATA>; 
my $nrows =  $#rows;
 
for (my $i = $nrows; $i>0; $i--) {
  for my $j (0 .. $i-1) { 
    $rows[$i-1][$j] += max_n( $rows[$i][$j], $rows[$i][$j+1] ); 
  }
} 
print "Answer to PE18 = $rows[0][0]"; 
__DATA__ 
3
7 5
2 4 6
8 5 9 3

Comments

• We’ve included the sample data as an example.
• The first line of the program reads the data file, which is appended to the end of the program after the __DATA__ separator, into a two dimensional array named @rows. $nrows is the last index of the array so in this case 3.
• Check here for more information on the max_n function.
• See also problem 67, 81, 82 & 83.