Project Euler — Problem 18 Solution

Problem

By start­ing at the top of the tri­an­gle below and mov­ing to adja­cent num­bers on the row below, the max­i­mum total from top to bot­tom is 23.

image

 

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

Find the max­i­mum total from top to bot­tom of the tri­an­gle below:

image

 

NOTE: As there are only 16384 routes, it is pos­si­ble to solve this prob­lem by try­ing every route. How­ev­er, Prob­lem 67, is the same chal­lenge with a tri­an­gle con­tain­ing one-hun­dred rows; it can­not be solved by brute force, and requires a clever method! ;o)

Solution

With the warn­ing of prob­lem 67 in mind, I set out to tack­le this prob­lem with a some­what effi­cient solu­tion which will also work for prob­lem 67. To start off, let’s look at the sim­ple exam­ple, as you tra­verse down the tri­an­gle 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 tri­an­gle:

image

From the above image you can see that the path 3–7-4 and 3–4-4 both exit the mini tri­an­gle at the same loca­tion but car­ry­ing two dif­fer­ent totals – green = 14, red = 11. If you were to con­tin­ue down the tri­an­gle from this point on, regard­less of whether you’re going to turn left or right in the next move, the max total will sure­ly have to come from the path which has gen­er­at­ed the high­est total so far.

If we apply the same log­ic to the entire tri­an­gle we can build up a tri­an­gle of totals for the raw tri­an­gle where every ele­ment rep­re­sents the max total achiev­able by any path that has lead to it:

image

Let’s call this tri­an­gle of totals T, and the orig­i­nal tri­an­gle R, we have:

image image

You can see that T(2,1) dif­fered 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 sim­plic­i­ty sake, let’s say that for a giv­en row n, in T (where n >= 2) we have:

image

The max total from top to bot­tom of the tri­an­gle R is equal to the max total in the last row of the tri­an­gle T. See­ing as we’re only inter­est­ed in the max total rather than the tri­an­gle T itself, my solu­tion below only returns the last row of T which is all we need to solve the prob­lem: