Granny's Programming Pearls "inside of every large program is a small program struggling to get out" JavaRanch.com/granny.jsp
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

Grid Routes

Sam Benry
Ranch Hand
Posts: 89
Starting in the top left corner of a 2�2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20�20 grid?

hmm.. I dont have any idea to how change this problem to a code... can anyone help me with ideas?

Campbell Ritchie
Marshal
Posts: 56536
172
There are 3 routes out of the top left node: down right and oblique-down-right. Work out how you get 6 from that, then try the same exercise for a 3x3 grid etc.

Rob Spoor
Sheriff
Posts: 21135
87
You have to find a pattern, so like Campbell said, try it for 1, 3 and if needed 4. That should help you a lot.

Sam Benry
Ranch Hand
Posts: 89
ok I've been thinking and thinking but I cant figure one thing out

in what follows size is the size of the grid
1x1 has size = 1
2x2 has size = 2 ...
so I figured that every grid has a certain number of general paths (not routes) that can be easily found
1x1 has 2 paths
2x2 has 4 paths
3x3 has 6 paths
4x4 has 8 paths
5x5 has 10 paths and so on...
and in every grid
path 1 = path n
path 2 = path n-1
path 3 = path n-2 and so on...
and path 1 = path n = 1
the summation of all the paths is the number of routes...

take the 3x3 grid
path 1 = 1
path 2 = 3
path 3 = 6
path 4 = 6
path 5 = 3
path 6 = 1

I found out that
path 1 = path n = 1
path 2 = path n-1 = path 1 + (size - path 1) = 1 +(size-1) = size

BUT I cant figure out the general formula of path 3 !!!
how can I get path 3???
in a 3x3 grid, path 2 = 3, path 3 = 6
in a 4v4 grid, path 2 = 4, path 3 = 10
in a 5x5 grid, path 2 = 5, path 3 = 15
path 3 = path 2 + something or * something !!!

I just cant see it !!!
can anyone help now?

Campbell Ritchie
Marshal
Posts: 56536
172
That lot doesn't look right. You have to work out 6 paths from top left to bottom right in a 2X2 grid. {Actually I suspect there aren't 6 paths, but 5.] Work it out. Start from top left, then try how many different paths there are from that node to the next. For each node you land on, if you haven't reached the goal, work out how many paths you now have. You will end up with a formula which is a bit like the factorial formula. Write it down.

Your grid has a leading diagonal (at least that's what you call it in a matrix) top left->bottom right, and the other diagonal bottom left->top right (which I shall call "opposing diagonal"). Work out how many ways there are from top left to the opposing diagonal, then how many ways there are from bottom right to the opposing diagonal.

Garrett Rowe
Ranch Hand
Posts: 1296
Your thinking is right in that this is much more a math problem than a coding problem. Think of it this way: since backtracking is not allowed, to get from the left side of the grid to the right side, you always have to move forward n times (where n is the width of the grid). A similar pattern exists for moving from the top to the bottom of the grid... I'll stop here because I don't want to give away too much.

Campbell Ritchie
Marshal
Posts: 56536
172
It's a kind of Pascal's triangle problem . . .

Rob Spoor
Sheriff
Posts: 21135
87
I just thought about it, and came with the following idea.

At every point on your grid you have two options (right or down), except for the points located at the borders. The total number of paths from that point is then the total number of paths if you go down + the total number of paths if you go right (both if possible). At the bottom-right point there is only 1 path: direct to itself.

So you can calculate this using backtracking:
Here the size is the number of points, not the number of connections between points. So if size == 2, that means just a single square with 2 options.

Please note that I use long here - that's really necessary for 21 points (i.e. a 20x20 grid)

Around 35 you'll need to start using BigInteger.

[ March 25, 2008: Message edited by: Rob Prime ]

[ March 25, 2008: Message edited by: Rob Prime ]
[ March 25, 2008: Message edited by: Rob Prime ]

Campbell Ritchie
Marshal
Posts: 56536
172
You need to look at Project Euler where it explains the problem with a diagram of a 2x2 grid. I have had no end of difficulty working out how you get 6 paths, but seeing the diagram it is obvious. 2 is spelt THREE!

Rob Spoor
Sheriff
Posts: 21135
87
One improvement on my code:

If you switch around the matrix, making (1,1) the point to go to, you can use one single matrix for multiple grid sizes; instead of returning matrix[0][0], you return matrix[size][size] (where size is again the number of points, starting at 1).

Garrett Rowe
Ranch Hand
Posts: 1296
Rob Prime: At every point on your grid you have two options (right or down), except for the points located at the borders. The total number of paths from that point is then the total number of paths if you go down + the total number of paths if you go right (both if possible). At the bottom-right point there is only 1 path: direct to itself.

I haven't tried your code. But I'm surprised you found a backtracking solution that will actually complete for this problem. I ended up solving it with a calculator and a little googling about permutations. More specifically "permutations of indistinguishable elements".

Garrett Rowe
Ranch Hand
Posts: 1296
Rob, I just ran your code, and it is definitely fast, but there's a bug in there somewhere because it returns the wrong result unless of course I'm invoking it incorrectly.

Output =
Result:35345263800

Rob Spoor
Sheriff
Posts: 21135
87
Originally posted by Garrett Rowe:
But I'm surprised you found a backtracking solution that will actually complete for this problem.

I had an exercise in university that was quite similar, and this is how it was solved back then.

Originally posted by Garrett Rowe:
Rob, I just ran your code, and it is definitely fast, but there's a bug in there somewhere because it returns the wrong result unless of course I'm invoking it incorrectly.
...
Output =
Result:35345263800

As I said, my code takes the grid points as size, so you'll have to use 21 for the size, not 20.

Garrett Rowe
Ranch Hand
Posts: 1296
Now that I've taken some time to understand your algorithm, that's a pretty slick solution. I tried to go from the beginning recursively, but I ended up going with another solution altogether.

 Don't get me started about those stupid light bulbs.