The 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 40393837363534333231302928272625242322*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);
        }
    }
}