Hey everyone,
Last night I was trying to solve challenge #15 from Project Euler:
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?
I figured this shouldn't be so hard, so I wrote a basic recursive function:
const int gridSize = 20;
// call with progress(0, 0)
static int progress(int x, int y)
{
int i = 0;
if (x < gridSize)
i += progress(x + 1, y);
if (y < gridSize)
i += progress(x, y + 1);
if (x == gridSize && y == gridSize)
return 1;
return i;
}
I verified that it worked for a smaller grids such as 2×2 or 3×3, and then set it to run for a 20×20 grid. Imagine my surprise when, 5 hours later, the program was still happily crunching the numbers, and only about 80% done (based on examining its current position/route
in the grid).
Clearly I'm going about this the wrong way. How would you solve this problem? I'm thinking it should be solved using an equation rather than a method like mine, but that's unfortunately not a strong side of mine.
Update:
I now have a working version. Basically it caches results obtained before when a n×m block still remains to be traversed. Here is the code along with some comments:
// the size of our grid
static int gridSize = 20;
// the amount of paths available for a "NxM" block, e.g. "2x2" => 4
static Dictionary<string, long> pathsByBlock = new Dictionary<string, long>();
// calculate the surface of the block to the finish line
static long calcsurface(long x, long y)
{
return (gridSize - x) * (gridSize - y);
}
// call using progress (0, 0)
static long progress(long x, long y)
{
// first calculate the surface of the block remaining
long surface = calcsurface(x, y);
long i = 0;
// zero surface means only 1 path remains
// (we either go only right, or only down)
if (surface == 0)
return 1;
// create a textual representation of the remaining
// block, for use
in the dictionary
string block = (gridSize - x) + "x" + (gridSize - y);
// if a same block has not been processed before
if (!pathsByBlock.ContainsKey(block))
{
// calculate it
in the right direction
if (x < gridSize)
i += progress(x + 1, y);
// and
in the down direction
if (y < gridSize)
i += progress(x, y + 1);
// and cache the result!
pathsByBlock[block] = i;
}
// self-explanatory :)
return pathsByBlock[block];
}
Calling it 20 times, for grids with size 1×1 through 20×20 produces the following output:
There are 2 paths
in a 1 sized grid
0,0110006 seconds
There are 6 paths
in a 2 sized grid
0,0030002 seconds
There are 20 paths
in a 3 sized grid
0 seconds
There are 70 paths
in a 4 sized grid
0 seconds
There are 252 paths
in a 5 sized grid
0 seconds
There are 924 paths
in a 6 sized grid
0 seconds
There are 3432 paths
in a 7 sized grid
0 seconds
There are 12870 paths
in a 8 sized grid
0,001 seconds
There are 48620 paths
in a 9 sized grid
0,0010001 seconds
There are 184756 paths
in a 10 sized grid
0,001 seconds
There are 705432 paths
in a 11 sized grid
0 seconds
There are 2704156 paths
in a 12 sized grid
0 seconds
There are 10400600 paths
in a 13 sized grid
0,001 seconds
There are 40116600 paths
in a 14 sized grid
0 seconds
There are 155117520 paths
in a 15 sized grid
0 seconds
There are 601080390 paths
in a 16 sized grid
0,0010001 seconds
There are 2333606220 paths
in a 17 sized grid
0,001 seconds
There are 9075135300 paths
in a 18 sized grid
0,001 seconds
There are 35345263800 paths
in a 19 sized grid
0,001 seconds
There are 137846528820 paths
in a 20 sized grid
0,0010001 seconds
0,0390022 seconds
in total
I'm accepting danben's answer, because his helped me find this solution the most. But upvotes also to Tim Goodman and Agos :)
Bonus update:
After reading Eric Lippert's answer, I took another look and rewrote it somewhat. The basic idea is still the same but the caching part has been taken out and put
in a separate function, like
in Eric's example. The result is some much more elegant looking code.
// the size of our grid
const int gridSize = 20;
// magic.
static Func<A1,
A2, R> Memoize<A1,
A2, R>(this Func<A1,
A2, R> f)
{
// Return a function which is f with caching.
var dictionary = new Dictionary<string, R>();
return (A1 a1,
A2 a2) =>
{
R r;
string key = a1 + "x" + a2;
if (!dictionary.TryGetValue(key, out r))
{
// not
in cache yet
r = f(a1, a2);
dictionary.Add(key, r);
}
return r;
};
}
// calculate the surface of the block to the finish line
static long calcsurface(long x, long y)
{
return (gridSize - x) * (gridSize - y);
}
// call using progress (0, 0)
static Func<long, long, long> progress = ((Func<long, long, long>)((long x, long y) =>
{
// first calculate the surface of the block remaining
long surface = calcsurface(x, y);
long i = 0;
// zero surface means only 1 path remains
// (we either go only right, or only down)
if (surface == 0)
return 1;
// calculate it
in the right direction
if (x < gridSize)
i += progress(x + 1, y);
// and
in the down direction
if (y < gridSize)
i += progress(x, y + 1);
// self-explanatory :)
return i;
})).Memoize();
By the way, I couldn't think of a better way to use the two arguments as a key for the dictionary. I googled around a bit, and it seems this is a common solution. Oh well.
