Project Euler – Maximum path sum (Part 1)

This is what I am currently working on:

Maximum_path_sum_problem_description.png

I don’t have the solution yet, so this blog post will contain some thoughts that hopefully will at least lead me in the right direction.

Always pick the highest number?

My first idea was to always pick the highest adjacent number. This is what’s done in the given example: 3 + 7 + 4 + 9.

example

 

This would lead to 75 + 95 + 47 + 87 + 82 + 75 + 73 + 28 + 83 + 47 + 43 + 73 + 91 + 67 + 98 = 1064. Unfortunately this is not the correct solution.

Therefore going for the highest number is not the correct strategy.

Is it a tree?

This looks like a tree. But I have to be careful.

tree_1.png

This is not the kind of tree I am looking for, as I could never reach from node “4” to the adjacent node with the same value:

tree_2.png

What I need is a tree that looks like the following:

tree_3.png

So how to do I create such a structure programmatically?

The problem shows a root node plus 14 additional node levels. This might result in heavy typing which I want to avoid.

Work from top or bottom?

Once I have a tree, how do I process it? Looks like a call for recursion? Top-down? Bottom-up?

Sanity check

I know that 1064 is not the correct solution. Therefore the solution must be a larger number. Also it cannot be more than 1313. Most likely the solution is closer to 1064.

 

2 thoughts on “Project Euler – Maximum path sum (Part 1)

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