# Grid paths and permutations

Published on 2011-07-25The big programming challenge for problem 15 was figuring out how to include a new assembly reference in Visual Studio. The problem asks you to figure out the number of paths one can take through a 20x20 grid:

Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20x20 grid?

Getting from the top left to the bottom right requires forty steps, each of must be either right or down. There are 40! possible permutations of a sequence composed of random rights and downs, but we know that, our grid being a square, one must take equal numbers of steps down and right. Given a sequence of forty steps right ward, we must twenty to convert to downward steps: we have forty to pick from the first time, then thirty-nine, then thirty-eight, etc., stopping when we have twenty rightward steps remaining. These are our possible routes down the grid, which number 40*39*38*37*36*35*34*33*32*31*30*29*28*27*26*25*24*23*22*11, more succinctly expressed as 40! / 20!. There are, however, a number of redundancies in our set of 40! / 20! paths, since convert steps 1-20 from rightward to downward in that order yields the same result as doing so in the reverse order. To compensate for potential redundancies, we must divide (40! / 20!) by the number of possible permutations thereof, which, like any other permutation, is expressed as a factorial: in this case, 20!. (A more complete explanation of this last step can be found on a BetterExplained post on the subject.) Therefore, the number of unique routes through the 20x20 grid is (40!/20!)/20!. The tricky part of programming this simple formula is that (40!/20!) is far greater than the largest possible value of an unsigned, 64-bit integer, which would be 2^64, or 18446744073709551615. I'm sure there's a more elegant solution, but I just found out how to include a reference to System.Numerics in my Visual Studio solution file and used a BigInteger to represent my factorials.

using System; using System.Numerics; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem015 { class Program { static void Main(string[] args) { int gridHeight = 20; int gridWidth = 20; BigInteger gridWidthFactorial = new BigInteger(1); BigInteger gridHeightFactorial = new BigInteger(1); BigInteger numerator = new BigInteger(1); BigInteger result = new BigInteger(); for (int i = 1; i <= gridWidth; i++) gridWidthFactorial *= i; for (int i = 1; i <= gridHeight; i++) gridHeightFactorial *= i; for (int i = (gridHeight + gridWidth); i > gridWidth; i--) numerator *= i; result = numerator / gridHeightFactorial; Console.WriteLine("There are {0} paths through a 20x20 grid", result); } } }