Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Need help with Project Euler algorithm

Garrett Rowe
Ranch Hand
Posts: 1296
Hey everyone, I posted in another thread that I was having problems coming up with an algorithm for this problem in Project Euler:

Could someone please give me a nudge in the direction of the "clever algorithm" that they could be referring to?. I thought about just taking the maximum from each decision point, but I can't prove that that would always give me the correct answer. As a matter of fact it seems like I can prove that it doesn't:

Just choosing the best local decision here would give me
1 + 3 + 5 + 6 = 15

when the real maximum path is
1 + 2 + 6 + 9 = 18
[ March 21, 2008: Message edited by: Garrett Rowe ]

David O'Meara
Rancher
Posts: 13459
Have you done any 'graph' problems? that is node-vector stuff.

You should be able to come up with a greedy algorithm that looks at the largest number in each row and tries to match with the largest on the row up and down - like the inverse of Djikstra (sp?)

Actually, you probably want to find largest pairs, then try to join them into a link from the top to the bottom eg in the first rom you have

"from one to two max is 75 + 95" so we store (1, 1, 2, 1, 180)
(row one item one and row two item 1 gives 180)
Then "From two to three max is 64 + 82" giving (2, 2, 3, 3, 146)
Looking back, we can't match these two, so you need to either decide to add
(1,1,2,2,75+64) so you can join them to make (1,1,3,3,75+64+146) or select the next largest from row 2 to 3.

Not perfect, but drop us a line if you refine it.

Garrett Rowe
Ranch Hand
Posts: 1296
Alright so here's the algorithm I thought of, although is seems like this would have to check every path also:

I just need to translate that into code.

David O'Meara
Rancher
Posts: 13459
Hmm, also consider the following:

Given:

If B>=C choose A-B-D, otherwise choose A-C-D

Garrett Rowe
Ranch Hand
Posts: 1296
Originally posted by David O'Meara:
Hmm, also consider the following:

Given:

If B>=C choose A-B-D, otherwise choose A-C-D

My thinking was given the triangle

There is exactly 1 maximum path from B to the end and 1 maximum path from C to the end, so the maximum path from A to the end is A + max(maximumPath(B), maximumPath(C)), that way A doesn't have to explore the entire path, it just looks at B and C's maximum path and appends itself to whichever is greater. I wrote the code in Haskell, because I'm trying to learn the language:

I got the right answer, but my algorithm isn't efficient enough to complete Problem 67

Vikrant Pandit
Ranch Hand
Posts: 245
Garrett,

You can try the following pseudo code . Not sure if it is same as yours

For a try of height 100 (having 100 leaf nodes), it would require around 100 * 99 /2 iterations
Not very effcient , but just might work.

Garrett Rowe
Ranch Hand
Posts: 1296
Here's some Java code that's a quick and dirty translation of the Haskell code:

[ March 22, 2008: Message edited by: Garrett Rowe ]
[ March 22, 2008: Message edited by: Garrett Rowe ]

Garrett Rowe
Ranch Hand
Posts: 1296
If I understand what you're saying correctly Vivek, you're saying I should reduce the Triangle from the bottom up:

So starting from the second to last line, the max sum for the 5 is 5 + 9, the max sum for the 7 is 7 + 6, and the max sum for the 8 is 8 + 6, so I can reduce the triangle by eliminating the bottom line and replace the second to last line with each corresponding max sum.

I like that, I think thats a very workable solution.
[ March 22, 2008: Message edited by: Garrett Rowe ]

Garrett Rowe
Ranch Hand
Posts: 1296
FWIW, that algorithm worked flawlessly and almost instantaneously. Again I coded the solution in Haskell, but I'm sure it would work equally fast in Java. It even eliminated the need to create the unnecessary data structure.