Project Euler #15

Question

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.

_{(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.

Answer 1

Quick No Programming Solution (based on combinatorics)

I take it "no backtracking" means we always either increase x or increase y.

If so, we know that in total we will have 40 steps to reach the finish -- 20 increases in x, 20 increases in y.

The only question is which of the 40 are the 20 increases in x. The problem amounts to: how many different ways can you choose 20 elements out of a set of 40 elements. (The elements are: step 1, step 2, etc. and we're choosing, say, the ones that are increases in x).

There's a formula for this: it's the binomial coefficient with 40 on top and 20 on the bottom. The formula is 40!/((20!)(40-20)!), in other words 40!/(20!)^2. Here ! represents factorial. (e.g., 5! = 5*4*3*2*1)

Canceling out one of the 20! and part of the 40!, this becomes: (40*39*38*37*36*35*34*33*32*31*30*29*28*27*26*25*24*23*22*21)/(20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1). The problem is thus reduced to simple arithmatic. The answer is 137,846,528,820.

For comparison, note that (4*3)/(2*1) gives the answer from their example, 6.