The challenge set by problem 18 was
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 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
A 15-row triangle was then supplied for which the program must determine the corresponding maximum value taking a similar path through the data. A footnote to the problem highlighted that due to the “limited” number of paths for this puzzle it could be solved using brute force determining the total for each path through the triangle and selecting the maximum total returned. However a link to problem 67 was provided which exactly the same problem, but this time the data was for a hundred-row triangle. For that problem a brute force attack could not be used as the number of possible routes meant that:
If you could check one trillion routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)
In researching possible approaches I came across an Excel solution by Tushar Metha. This really simplified the approach, turning the data upside down and starting on the last row, taking two adjacent cells (“c1” and “c2”) and their corresponding cell on the row below “c3” (remember triangle has been turned upside down). The two routes for that subset were determined and the maximum value was placed in cell “c3”. In the example, 5 is “c1”, 9 is “c2” and 4 is “c3”. So “c1 + c3” = 9 whilst “c2 +c3” = 13, so the contents of c3 is replaced with 13. This process is repeated for the entire row.
5 9
4
Once the entire row has processed you “move” down a row and repeat the process. For problem 67, instead of taking 20 billion years it takes less than a second – so quite a nice time saving over the brute force approach.
Problem Stats:
- 23 out of 299 problems solved (2 more until first level!)
- No Ranking (based on problems 275 to 299)
Over the past couple of years I keep on coming back to Project Euler, it’s nice when you just want a quick challenge, or to try your maths skills. It’s highlighted how rusty some of my concepts were, and I’ve learnt a whole load of new ones along the way. I really like the way that the example problem given is quite quick to determine using brute force, but the desired answer always needs a . . .
I’m trying to start up on project Euler again, one thing I do like is that it highlights how poor some of my maths knowledge actually is. Neither school or college covered many of these algorithms; which is a bit of a surprise given that I did a four-year mechanical apprenticeship with applied mathematics…..still never too late to learn So I (re)started on problem 24 which read: A permutation is an ordered arrangement of objects. . . .