Select Page

Project Euler 18 Problem Statement

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

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)

Solution

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 above to show how this works.

A step-by-step look at this algorithm

   3
  7 5
 2 4 6
8 5 9 3
  1. Starting at the bottom, take the first pair, 8 and 5, pick the maximum and replace the 2 in the previous row with their sum 8+2=10.
  2. Take the next pair, 5 and 9, pick the maximum and replace the 4 in the previous row with their sum 9+4=13.
  3. Finally, take the last pair, 9 and 3, pick the maximum and replace the 6 in the previous row with their sum 9+6=15.

Now our array looks like:

   3
  7  5
10 13 15

Let’s do it again.

  1. Take the larger of 10 and 13 and add it to 7 making 13+7=20.
  2. Take the larger of 13 and 15 and add it to 5 making 15+5=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 20+2=23.
And our array looks like:

23

Which is the maximum total path in the triangle.

HackerRank version

HackerRank Project Euler 18 doesn’t add more to the challenge other than running 10 test cases. The data for this problem is kept in the REPL.IT file tab named pe18.txt.

Python 2.7 Source

Last Word

The first line of the program reads the data file, pe18.txt, into a two dimensional array named table.