This week's book giveaway is in the Java in General forum.
We're giving away four copies of Event Streams in Action and have Alexander Dean & Valentin Crettaz on-line!
See this thread for details.
Win a copy of Event Streams in Action this week in the Java in General forum!
  • 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
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Knute Snortum
  • Rob Spoor
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Piet Souris
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

Project Euler: problem 15

 
Rancher
Posts: 122
7
IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all,

I like solving problem sets on Project Euler. I came across the following one (problem 15) and I wouldn't know how to start tackling it. It is about finding the number of ways to traverse a 2x2 grid (see image attachment).

I am not looking for the solution (I am, but I would like to find it myself   ) but I don't know which knowledge or algorithm is required to solve it. Could someone point me in the right direction?
Screenshot-2019-07-20-at-11.50.09.png
[Thumbnail for Screenshot-2019-07-20-at-11.50.09.png]
ProjectEuler_Problem15
 
Marshal
Posts: 65050
247
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Don't know. You will have to do some problem solving. Let's think a bit about it.
  • 1: You have fencepost numbers. Their 2×2 grid has three nodes across its / diagonal.
  • 2: Turn the entire diagram ¼π (=45°) to the right. Now your right‑or‑down becomes downward.
  • 3: For each node, work out how many routes there are to it from the top node.
  • See if you can get a pattern for the whole diagram.

    Aternative suggestion:- If there are 6 paths through your 2×2, what is going to happen if you add one row and one column to its right/bottom (now 3×3)?
     
    Saloon Keeper
    Posts: 3411
    149
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    hi Brecht,

    the way I did that exercise (and similar, more complicated, to follow), was to compare this exercise to drawing without replacement from an urn with white and red balls. A white ball was for going down, a red ball for going right. Now, how many red and white balls do you have here, and how many different ways are there to draw all these balls?
     
    Campbell Ritchie
    Marshal
    Posts: 65050
    247
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    How did yoiu get six? Was that 3! ?
     
    Sheriff
    Posts: 6109
    157
    Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    This, like a lot of Project Euler projects, is "easy" doing the math way and hard doing the "programming" way.

    The programming way might involve using recursion and backtracking.  Not beginning programming stuff.

    Honestly, the way I solved this and other problems was to look for a pattern in the solutions I knew and then see if there was a mathematical equation to represent that pattern.  I don't think this is "cheating" at all, but is probably the way the authors intended us to do it.
     
    Campbell Ritchie
    Marshal
    Posts: 65050
    247
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Knute Snortum wrote:. . . I don't think this is "cheating" at all, but is probably the way the authors intended us to do it.

    Agree; I think that is how Project Euler expect you to solve their problems. If you try it with heavy programming, you are likely to get slow execution and run out of time.
     
    Brecht Geeraerts
    Rancher
    Posts: 122
    7
    IntelliJ IDE Spring Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I tend to agree with that. From what I read, Project Euler is more focussed on the underlying mathematics and is less coding-oriented per se. Of course, you need a combination of both. It is nice to see that there are others here who also like to solve such puzzles for fun. My wife thinks I'm mad for doing this.  

    Rotating the grid by 45° did help me see it as a tree-like structure. I started off with 1x1 grid then a 2x2 and a 3x3 grid but it was difficult to find a relationship between the grid size and the number of ways to get to the endpoint. I had to brush up on my math skills but I managed to get it solved.

    I learned something today. Thanks, folks!

    @Piet, could you elaborate on your suggestion? There should have been 4 balls, right? (i.e. two white ones and two red ones, for a 2x2 grid). How does this relate to a bigger grid? I'm curious and like to understand it.
     
    Piet Souris
    Saloon Keeper
    Posts: 3411
    149
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    hi Brecht,

    Yes, I can elaborate a little. As I wrote, I compare it to drawing from an urn filled with white and red balls. If I have 2 white and two red balls in the urn, then if I draw them, I could get say WRRW, meaning down-right-right-down. In other words, one such drawing is equivalent to a path. Now, the question is then: having 2 white and 2 red balls, hoe many sequences are there? Well, that is a well known formula from the Combinatorics. It is the Binomial Coefficient (4 over 2) = 4! / (2! * 2!) = 6.

    Likewise, for a 20x20 grid, we would have 20 white and 20 red balls. I will stop now, since I do not want to reveal more details. But no doubt you can fill in the rest. I used a spreadsheet for this.
     
    Brecht Geeraerts
    Rancher
    Posts: 122
    7
    IntelliJ IDE Spring Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks a lot, Piet. I now better understand your analogy with the red and white balls.

    It was a fun exercise. Luckily there are still several hundreds left.  

    Thanks Piet and Campbell for the help.
     
    Piet Souris
    Saloon Keeper
    Posts: 3411
    149
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    You're welcome!

    And don't worry about the mrs: my experience is that they will accept that Euler thing, as long as the dishwashing and vacuumcleaning are still done in time. And, most important: do not forget the wedding anniversaries while doing Euler...
     
    Brecht Geeraerts
    Rancher
    Posts: 122
    7
    IntelliJ IDE Spring Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Piet, I am not going to let her read your post.  I have to protect myself
     
    It is sorta covered in the JavaRanch Style Guide.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!