Project Euler/18

The 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.

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)

Link: https://projecteuler.net/problem=18

Related: Project Euler/67

The Solution

Note:

• Initial idea was marginal sums, change directions when marginal sum changes

Next idea:

• Normalized marginal sums

Actually implemented these, failure

Third idea:

• 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) ]

Code

Problem 18 code: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round1_001-020/018

Problem 67 code: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/067