This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
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 Android Security Essentials Live Lessons this week in the Android 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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Need help with Project Euler algorithm
 
Similar Threads
Read an integer line by line
100 times "hello world" without loop or recursive
http://xml.apache.org/axis/ HttpErrorCode:401
Project Euler problems with Scala
Project Euler #17