Search code examples
c#math

Project Euler #15

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.

alt text
(source: projecteuler.net)

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.

Solution

  • This can be done much faster if you use dynamic programming (storing the results of subproblems rather than recomputing them). Dynamic programming can be applied to problems that exhibit optimal substructure - this means that an optimal solution can be constructed from optimal solutions to subproblems (credit Wikipedia).

    I'd rather not give away the answer, but consider how the number of paths to the lower right corner may be related to the number of paths to adjacent squares.

    Also - if you were going to work this out by hand, how would you do it?