Project Euler 67: Find the maximum total from top to bottom in a large triangular array

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

To solve this problem and problem 18 (which is markedly easier), 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 above to show how this works.

3
7 5
2 4 6
8 5 9 3
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.

It takes less than a fraction of a second as compared to waiting for the sun to burn out.

Project Euler 67 Solution

Afterthoughts

• Here’s a backup of the data file used for Project Euler 67 if it’s inaccessible from the Project Euler site: triangle.txt.
  
• See also, Project Euler 18 Solution: