# Need help with Project Euler algorithm

- 0

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

- 0

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.

- 0

I just need to translate that into code.

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

- 0

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

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

- 0

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

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

- 0

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 ]

- 0

I agree. Here's the link: http://aspose.com/file-tools |