Project Euler – Problem 18 Solution

Problem

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.

image

 

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

image

 

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

With the warning of problem 67 in mind, I set out to tackle this problem with a somewhat efficient solution which will also work for problem 67. To start off, let’s look at the simple example, as you traverse down the triangle from the top you have two options at every turn – go left, or go right. From the third row onwards, some of the paths will end up in the same place in the triangle:

image

From the above image you can see that the path 3-7-4 and 3-4-4 both exit the mini triangle at the same location but carrying two different totals – green = 14, red = 11. If you were to continue down the triangle from this point on, regardless of whether you’re going to turn left or right in the next move, the max total will surely have to come from the path which has generated the highest total so far.

If we apply the same logic to the entire triangle we can build up a triangle of totals for the raw triangle where every element represents the max total achievable by any path that has lead to it:

image

Let’s call this triangle of totals T, and the original triangle R, we have:

image image

You can see that T(2,1) differed from T(2,0) and T(2,2) in that it required us to find the greater between T(1,0) and T(1,1). For simplicity sake, let’s say that for a given row n, in T (where n >= 2) we have:

image

The max total from top to bottom of the triangle R is equal to the max total in the last row of the triangle T. Seeing as we’re only interested in the max total rather than the triangle T itself, my solution below only returns the last row of T which is all we need to solve the problem:


Subscribe to my newsletter and get new contents delivered straight to your inbox :-)