aspose file tools*
The moose likes Programming Diversions and the fly likes Need help with Project Euler algorithm Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Need help with Project Euler algorithm" Watch "Need help with Project Euler algorithm" New topic
Author

Need help with Project Euler algorithm

Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
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 ]

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

Joined: Mar 06, 2001
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

Joined: Jan 17, 2006
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

Joined: Mar 06, 2001
Posts: 13459

Hmm, also consider the following:

Given:


If B>=C choose A-B-D, otherwise choose A-C-D
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
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

Joined: Mar 27, 2006
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.


Vikrant Pandit
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
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

Joined: Jan 17, 2006
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

Joined: Jan 17, 2006
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.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Need help with Project Euler algorithm