The Problem
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
A Note Before We Begin
I have seen several, more clever solutions to this problem. I've seen one that starts at the bottom and works up, and another that manages to reduce the problem to a simple equation (the math of which is beyond me). So this isn't the best solution by any stretch, but it's the one that works for me.
The Solution
This is another problem where pure bute force doesn't do the trick. But let's look at that approach first.
[<Literal>]
let GridSize = 20
let countRoutesTo sourceX sourceY destX destY =
let rec count sx sy =
if sx = destX && sy = destY then
1L
elif sx < GridSize && sy < GridSize then
(count (sx+1) sy) + (count sx (sy+1))
elif sx < GridSize then
(count (sx+1) sy)
else
(count sx (sy+1))
let result = count 0 0
result
#time
countRoutesTo 0 0 GridSize GridSize
#time
The internal count
function is a recursive function that computes all of the routes to destX,destY
. It works like this:
 If we've hit the bottom right corner, the result is always 1 since we had to have made it there from one of the points adjacent to the bottom corner.

If we're somewhere in the interior of the grid, we return
count
for a move right plus acount
for a move down.  If we're at the bottom edge, we return
count
for a move right.  Otherwise, we must be at the right edge, so we return
count
for a move down.
The problem with this function is that it takes way too long to execute. I stopped it running
after 20 minutes. I know it works in principle because if I reduce GridSize
to 10, it executes
in under a second. The problem is that the number of calls to count
is a factorial of the
GridSize. In fact, you can get the answer to the problem by computing (2n)!/n!^{2},
but I didn't know that when I was writing this :)
My (ahem!) genius solution to the problem was to cache the answers for the lower right 100 squares of the grid, and then apply my brute force algorithm. If the algorithm hits a cached position, it doesn't have to do any more work and just returns the value it's currently computed plus the value from the cache.
This algorithm finds the answer in 22 seconds on my machine.
let countRoutesToCached sourceX sourceY destX destY =
let cachePos = GridSize / 2
let cache = System.Collections.Generic.Dictionary<int*int,int64>()
let rec count sx sy =
match cache.TryGetValue((sx,sy)) with
 true,v > v
 _ >
if sx = destX && sy = destY then
1L
elif sx < GridSize && sy < GridSize then
(count (sx+1) sy) + (count sx (sy+1))
elif sx < GridSize then
(count (sx+1) sy)
else
(count sx (sy+1))
for x in cachePos..GridSize do
for y in cachePos..GridSize do
cache.Add((x,y),(count x y)) > ignore
let result = count 0 0
result
#time
countRoutesToCached 0 0 GridSize GridSize
#time
Other Posts in This Series