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. That is, 3 + 7 + 4 + 9 = 23. Find the maximum total from top to bottom of the triangle below: 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)
Related: Project Euler/67
- Initial idea was marginal sums, change directions when marginal sum changes
- Normalized marginal sums
Actually implemented these, failure
- Summing up sub-triangles on left and right
This actually gets you pretty close to correct, but not quite.
I knew the algorithm was flawed in a very subtle way because it worked for contrived examples and for smaller triangles, but not for larger triangles. Counter-example was needed.
I ended up writing a recursive solution to solve the problem via brute force (about 1 second) and that gave me the correct path. At this point I could have solved this problem, but not Problem 67.
I compared the brute force solution path to the path that my algorithm was predicting, and found a counterexample:
82 23 75 77 73 7
This is a counterexample to my proposed method of finding the correct route, because the left subtriangle has a larger sum than the right subtriangle, and therefore my algorithm recommends choosing 23 then 77, instead of the more obvious 75 then 73.
This arises because we cannot utilize all of the outcomes in the left and right subtriangles - we need a way to say, yes, having a really huge number somewhere in your subtriangle is important - that's why we always want to sum over the entire subtriangle. However, we also need a way to account for the importance of the first choice we make over all the other choices - that is, choosing to go left because there is a value of 100 somewhere 5 levels away in the left sub-triangle is different from choosing to go left because you are choosing between 1 and 100.
The two should be weighted differently.
This leads to a more formalized approach to the problem. Of course, we should have seen this earlier, but this is precisely what the Project Euler questions are intended to do.
We can take a statistical/mathematical approach to the problem of finding the maximum cost function over a group of discrete choices: we say wewant to maximize the expectation of our sum.
We are given a choice between left and right, and we want to make a quantitative choice between left and right, so we assign a value. The value is the expected sum, the expected value of the sum, if we take the average over all the paths that the left choice would lead us to, versus the average over all the paths that the right choice would lead us to.
In the example tree above:
E(left subtriangle) = E(level 1) + E(level 2) = 23 + [ (1/2)(77) + (1/2)(73) ] = 98
whereas for the right tree:
E(right subtriangle) = E(level 1) + E(level 2) = 75 + [ (1/2)(73) + (1/2)(7) ]
Project Eulerproject euler notes
Round 1: Problems 1-20
Round 2: Problems 50-70
Round 3: Problems 100-110
Round 4: Problems 500-510
Round 5: Problems 150-160
Round 6: Problems 250-260
Round 7: Problems 170-180