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 ]

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

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

Joined: Jan 17, 2006
Posts: 1296

posted

0

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

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

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.

Vikrant Pandit

Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296

posted

0

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

Joined: Jan 17, 2006
Posts: 1296

posted

0

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

Joined: Jan 17, 2006
Posts: 1296

posted

0

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.

Don't get me started about those stupid light bulbs.