Project Euler Problem 15: City Grids and Pascal's Triangle

Problem 15 in the Project Euler series asks us to count the number of routes through a 20x20 grid starting from the top left and travelling to bottom right, always moving either rightwards or downwards, never backtracking. I can give you the solution in one line of code; explaining why it is the solution will take me many more lines of prose. The solution is:

return PascalsTriangle.GetEntry(2*20, 20);

(OK, you caught me: PascalsTriangle isn't a C# primitive type, so I guess I'll have to give some code for that as well. But all in good time.)

So what does Pascal's triangle have to do with City Grids? This is one of the things that I love about mathematics: seemingly unrelated problems often have subtle and beautiful connections. The connections are completely hidden on the surface, but once you uncover them, link at a time, you wonder that you never spotted them immediately.

How should we go about counting the number of routes through the grid? Here, try with this smaller grid - take my copy and scribble on it all you like:

My first insight was to start counting, not at the start of the grid, but at the end. Rather than try to work out all the possible routes from the starting point, let's count how many routes there are from points near the end, then work backwards.

Let me show you.

How many routes are there from the point F6 (marked "End") to the same point, F6? Stupid question, obvious answer: one - just follow the complicated directions: "Stand Still". From F5 to F6 there's one route: "Go South one block". From E6 to F6, one route: "Go East one block". But if I'm stood at E5 and want to get to End I have two choices, I can either go "East one block, then south one block" or "South one block, then East one block".

In fact, from anywhere along column F there's only one route to the end ("Go South x blocks"), because we're not allowed to turn back west; and from anywhere along row 6 there's only one route ("Go East x blocks") because we're not allowed to turn up north. On the diagram I've drawn what we've got so far - blue shows the number of routes from each point:

Now lets consider how to find the number of routes from other spots on the grid. Take E4, for example. If we go east to F4 then we already know that there's only one way we can go on from there. If, however, we go south one block to E5 then we know that there are two routes we can take from there. So this makes a total of three possible routes from E4. By the same argument, we can see that there are 3 possible routes from D5. Then we can apply the same reasoning to cell D4: three possible routes if we go east to E4 plus three possible routes if we go south to D5 make for a total of 6 ways to get from D4 to the end. Another diagram to summarise:

You see the way this is going now, don't you? To work out the total number of routes from each intersection we add up the total number of routes from the intersections one block to the east, and one block to the south.

Now lets spin the grid about its centre to put the point marked End at the top, drop the gridlines, and write out the numbers by themselves. Like this:

What have we got? Pascal's Triangle - a fascinating mathematical object d'art that has been rediscovered many times throughout history in many different contexts. (Wikipedia will be delighted to tell you more about it- there's more to it than meets the eye). You construct it by writing 1s down the diagonal edges of the triangle, then forming each cell by summing the two neighbours in the row above.

I've highlighted the cells in red, because they are the ones that particularly concern us. Imagine spinning the triangle back so that it aligns with the grid. Then you see that "2" is the number of routes through a 1x1 grid, and "6" is the number of routes through a 2x2 grid.

Let's label the cells of the grid. Call the apex of the triangle row 0, and call the first "1" on each row column 0. Thus the number of routes through a 1x1 grid appears in row 2, column 1; the number of routes through a 2x2 grid appears at row 4 column 2. From there we can take a flying un-mathematical leap to a conclusion and say that the number of routes through an n x n grid will appear in row 2n, column n of Pascal's Triangle. That explains my solution: obvious now?

But how to calculate the number in that cell? My first thought was to write code that builds the triangle row by row. But there's a quicker way. Using Proof by Wikipedia, we can show that P(r,c) = ((r + 1 - c) / c) * P(r, c - 1), where P(r, c) is the value of Pascal's triangle at row r, column c. In other words, to calculate the value of a cell at column, c, in a particular row, r, we multiply the value of the cell to the left by the fraction (r + 1 - c) / c.

A sequence defined recursively like that makes me think of the Unfold method for generating it. Remember that after you have given it a seed value, Unfold generates a sequence for you by applying the lambda you give it to the previous term in the sequence. So our mathematical definition becomes:

public class PascalsTriangle
{
    public static long GetEntry(int row, int column)
    {
        // the L suffix on "Entry = 1L" is to force Entry to have a long type
        return Functional.Unfold(new {Entry = 1L, Column = 1},
                                 previous =>
                                 new
                                     {
                                         Entry = (previous.Entry*(row + 1 - previous.Column))/previous.Column,
                                         Column = previous.Column + 1
                                     })
            .SkipWhile(item => item.Column <= column)
            .First()
            .Entry;
    }
}

Note the use of the anonymous type to pass an additional piece of information through to the next iteration: Entry holds the cell value, and Column holds an incrementing count of the number of columns that we've calculated.

For reference, here's equivalent code that uses looping rather than functional concepts:

public static long GetEntry(int row, int column)
{
    long current = 1;

    for (int i = 1; i <= column; i++ )
    {
        current = (current * (row + 1 - i)) / i;
    }

    return current;
}

The complete code is shown below, and can also be downloaded from my Project Euler on the MSDN Code Gallery.

[EulerProblem(15, Title = "Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?")]
public class Problem15
{
    public long Solve()
    {
        return PascalsTriangle.GetEntry(2*20, 20);
    }
}

public class PascalsTriangle
{

    public static long GetEntry(int row, int column)
    {
        // the L suffix on "Entry = 1L" is to force Entry to have a long type
        return Functional.Unfold(new { Entry = 1L, Column = 1 },
                                 previous =>
                                 new
                                     {
                                         Entry = (previous.Entry * (row + 1 - previous.Column)) / previous.Column,
                                         Column = previous.Column + 1
                                     })
            .SkipWhile(item => item.Column <= column)
            .First()
            .Entry;
    }
}

public static class Functional
{
    public static IEnumerable<T> Unfold<T>(this T seed, Func<T, T> generator)
    {
        // include seed in the sequence
        yield return seed;

        T current = seed;

        // now continue the sequence
        while (true)
        {
            current = generator(current);
            yield return current;
        }
    }
}