Win a copy of Pro Spring MVC with WebFlux: Web Development in Spring Framework 5 and Spring Boot 2 this week in the Spring forum!
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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Jeanne Boyarsky
• Liutauras Vilda
Sheriffs:
• Rob Spoor
• Bear Bibeault
• Tim Cooke
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Piet Souris
Bartenders:
• Frits Walraven
• Himai Minh

Project Euler : problem 15

Greenhorn
Posts: 4
• Number of slices to send:
Optional 'thank-you' note:
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.

Bartender
Posts: 3648
16
• Number of slices to send:
Optional 'thank-you' note:
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.

Bartender
Posts: 1202
22
• Number of slices to send:
Optional 'thank-you' note:
One word... Recursion.
(Spoiler) Look at this.

Ranch Hand
Posts: 115
• Number of slices to send:
Optional 'thank-you' note:
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
Bartender
Posts: 1202
22
• Number of slices to send:
Optional 'thank-you' note:

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.

lowercase baba
Posts: 12988
66
• 1
• Number of slices to send:
Optional 'thank-you' note:
pascal's triangle is also appropriate here...

Ranch Hand
Posts: 808
• Number of slices to send:
Optional 'thank-you' note:

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!

Bartender
Posts: 612
7
• Number of slices to send:
Optional 'thank-you' note:
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
Posts: 12988
66
• Number of slices to send:
Optional 'thank-you' note:

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.