Project Euler – Maximum path sum (Part 2)

Time to pick up a Project Euler problem that was resting on my mental shelf since the beginning of September, “Maximum Path Sum I”. For a quick introduction just jump to the old post.

screenshot_14.png

What about using a tree?

Using a tree and traversing it, most likely recursively, was my first idea.

As one can possibly guess, many possible tree implementations exist.
Here is an example taken from Stanford’s computer science department:

screenshot_13.png

Using such a construct, I started building a tree “by hand”. Something along the lines of…

root = new Node(75);
root.left = new Node(95);
root.left = new Node(64);
root.left.left = new Node(17);
...

Definitely not the way to go. Gave up. Failed.

Pen and paper approaches

I had already figured out that the number I was looking for must be somewhere between 1064 and 1313.
1064: Start at the top and always pick the highest adjacent number.
1313: Just take the highest number of each row and add them all together, even though no connection exists, just to get a very rough estimate.

Then I started browsing the interwebs for “inspiration”, which gave me some ideas, but unfortunately the solution as well.

The amount of new knowledge gained so far: ZERO! But at least I now had access to the Project Euler forum posts for this particular problem. The holy grail of algorithmic knowledge.

Apparently some forum members figured this one out using just “pen and paper”:

I just make a greedy approach with eyes, done in the second try.

Or:

I did this by eye – buffed the triangle with spaces properly and replaced everything under 50 with ’00’ in a text editor, then chose the line that looked the most line-ish 🙂 solved in about 3 minutes.

These were unfortunately not the answers to satisfy my curiosity, but I also found forum posts which looked way more algorithmic:

just paper and pencil, reduce the bottom two lines to one line containing the best sum for each element, then proceed the same with the upper level and so on. at the top you will have the answer. Same algorith will be used at the triangle with 1000 lines. (hope will work) best regards

Someone named “mather” was the first one to post an answer along these lines.

Let’s have a look at his approach using the sample triangle given in the original problem description:

screenshot_16.png

The algorithm starts at the bottom line, not on the top. I stick to the tree language by the way. Each leaf has a parent node. For example 2 is the parent node of leaf 8 and 5. 4 is the parent node of leaf 5 and 9 and so on.

Now, for each node (leaf) we create a the sum of its value and the value of its parent. The higher sum will be kept. We just store it as new value in the parent node.

screenshot_18.png

8 + 2 = 10.
5 + 2 = 7.
10 > 7, keep 10.

screenshot_19.png

Now 5 + 4 = 9.
9 + 4 = 13.
13 > 9, keep 13.

And last 9 + 6 = 15.
3 + 6 = 9.
15 > 9, keep 15.

That’s how to proceed upwards.

screenshot_20.png

The final result is 23, which is exactly the number we are looking for.

And this is an algorithm that can be turned into  a program! Almost there.

Finally a program

Credit goes to a user named “dchuhay”.

This little program follows exactly the approach described above.

screenshot_21.png

The program flow starts in this row of the pyramid:

screenshot_24.png

For each node value in this row the algorithm builds two sums, one for each of the two child-nodes, and stores the higher sum in the original node.

E.g. i = 13, j =0. The node triangle[13][0] is 63.
Now, is triangle[13 + 1][0] < triangle[13 + 1][0 + 1]? 04 < 62? Yes!
Therefore add triangle[13 + 1][0 + 1] to triangle[13][0] and store it as new value in triangle[13][0]. 63 + 62 = 125.

Now proceed with the next node in this row, which is 66, until we run out of values.
Once all values in this row were replaced by new values (= highest sum) proceed on, one row upwards.

screenshot_25.png

for (int i = triangle.length – 2; i >= 0; i–) is correct, as we need to assign a value to triangle[0][0], which will be our final result.

Dynamic programning

One forum post containing a C# solution starts with the following line:

Classical dynamic programming task.

I had to look this up. According to Wikipedia:

In mathematics, management science, economics, computer science, and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup.) The technique of storing solutions to subproblems instead of recomputing them is called “memoization”.

Does this apply to the problem at hand?

Is it a complex problem? For sure. Can it be broken down into a collection of simpler subproblems? Hmmm, what would be a simpler subproblem? Exactly what is done above. For each combination of a node and its two sub-nodes find the higher sum. Keep the result. Wash, rinse, repeat until the root node is reached.

I am glad I did some research on this Project Euler problem. Lots of new knowledge gained.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s