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


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Project Euler : problem 15" Watch "Project Euler : problem 15" New topic
Author

Project Euler : problem 15

Mamadou Diallo
Greenhorn

Joined: Mar 05, 2009
Posts: 4
I'm learning java with Head First Java,and having a go at projects Euler problems, learning algorithms as I go along....

I'm completely lost about how to tackle problem15. http://projecteuler.net/index.php?section=problems&id=15
is that a graph theory problem? should I use List or Matrices to represent the grid in an algorithm?

Any hints(just hints!) will be appreciated.

Thanks.


K. Tsang
Bartender

Joined: Sep 13, 2007
Posts: 1963
    
    7

I have try Euler problems before but not this one. Ultimately it's all math.

2x2 grid=6 routes
3x3 grid=? routes
...
20x20 grid=? routes

Once you figure out the pattern.... voila.


K. Tsang JavaRanch SCJP5 SCJD/OCM-JD OCPJP7
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 988
    
    1
One word... Recursion.
(Spoiler) Look at this.

Myke Enriq
Ranch Hand

Joined: Feb 13, 2012
Posts: 102
It is a simple problem , very simpel solution:

a 20x20 grid will be traversed in a lot of way. But each way is composed of 40 simple actions
_simple_action_DOWN: from current point move one step down (1 unit)
_simple_action_LEFT: from current point move one step left (1 unit)

So the question is equivalent to: given 40 indexes place 20 DOWN and 20 LEFT on them
Meaning given 40 indexex that are all DOWN , chose 20 random ones and palce LEFT on them. meaning Combinations of 40 taken by 20.


Same generalization for a rectangle of sizes L and l : given L+l position , choose randomly L of them = Combinations of (L+l) taken by l


Sorry for the English , not my native language.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 988
    
    1
Ok, how about this variation:

How many ways are there to get from (0,0) to (20,20) (in the lower right quadrant, for the sake of discussion) if you're allowed to backtrack at most once? i.e. You're allowed one step to the left or one step up, but not both.

fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10911
    
  12

pascal's triangle is also appropriate here...


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
fred rosenberger wrote:pascal's triangle is also appropriate here...

This is far and away the most helpful comment pertaining to this problem that I have yet seen. Thank you, thank you!
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 556
    
    7

FYI: Myke's post should have been the best post as the answer is simply 20C40. And yes a py tri will work, but why. You don't need it.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10911
    
  12

Steve Fahlbusch wrote:FYI: Myke's post should have been the best post as the answer is simply 20C40. And yes a py tri will work, but why. You don't need it.

I was trying to give a hint without giving away the entire solution. Just saying "the answer is 'how can you choose 20 out of 40 elements'?" doesn't help the person understand WHY it is the answer.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Project Euler : problem 15
 
Similar Threads
Euler Problem One
Project Euler Problem 25
Project Euler #17
Project Euler problems with Scala
Project Euler : Problem 23