• Post Reply Bookmark Topic Watch Topic
  • New Topic
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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • paul wheaton
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Ron McLeod
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Tim Holloway
  • Carey Brown
  • salvin francis

Need help with Project Euler algorithm

 
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmm, also consider the following:

Given:


If B>=C choose A-B-D, otherwise choose A-C-D
 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Barry's not gonna like this. Barry's not gonna like this one bit. What is Barry's deal with tiny ads?
Enterprise-grade Excel API for Java
https://products.aspose.com/cells/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!