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?
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?
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.
All things are lawful, but not all things are profitable.
posted 1 year ago
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.
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.
posted 1 year ago
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.
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.
posted 1 year ago
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...