Win a copy of Zero to AI - A non-technical, hype-free guide to prospering in the AI era this week in the Artificial Intelligence and Machine Learning 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Liutauras Vilda
• Paul Clapham
• Bear Bibeault
• Jeanne Boyarsky
Sheriffs:
• Ron McLeod
• Tim Cooke
• Devaka Cooray
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Jj Roberts
• Stephan van Hulst
• Carey Brown
Bartenders:
• salvin francis
• Scott Selikoff
• fred rosenberger

# Project Euler: problem 15

Rancher
Posts: 261
12
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

Marshal
Posts: 70625
288
• 1
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)?

Bartender
Posts: 4103
156
• 1
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: 70625
288
How did yoiu get six? Was that 3! ?

Sheriff
Posts: 7108
184
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: 70625
288

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: 261
12
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
Bartender
Posts: 4103
156
• 1
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: 261
12
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
Bartender
Posts: 4103
156
• 1
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: 261
12
Piet, I am not going to let her read your post.  I have to protect myself