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 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. It is not possible to try every route to solve this problem, as there are 2⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Analysis

Used the program from problem 18. It takes less than a second as compared to waiting for the sun to burn out.

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 PE67 = $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 max_n().
• See problem 18, problem 81, 82 & 83.