# Project Euler : problem 15

Mamadou Diallo

Greenhorn

Posts: 4

posted 7 years ago

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.

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.

posted 7 years ago

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.

2x2 grid=6 routes

3x3 grid=? routes

...

20x20 grid=? routes

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

K. Tsang OCPJP7 OCMJEA6

Ryan McGuire

Ranch Hand

Posts: 1105

7

Myke Enriq

Ranch Hand

Posts: 115

posted 4 years ago

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.

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

Posts: 1105

7

dennis deems

Ranch Hand

Posts: 808

posted 4 years ago

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.

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.

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