programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Need help with Project Euler algorithm

Ranch Hand
Posts: 1296
• Number of slices to send:
Optional 'thank-you' note:
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 ]

Rancher
Posts: 13459
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
Hmm, also consider the following:

Given:

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

Garrett Rowe
Ranch Hand
Posts: 1296
• Number of slices to send:
Optional 'thank-you' note:

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

Ranch Hand
Posts: 245
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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.

 Consider Paul's rocket mass heater.