Project Euler problem 15

Source code available on GitHub.

  Starting in the top left corner of a \(2 \times 2\) grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

 


  How many such routes are there through a \(20 \times 20\) grid?

This looks confusing at first, and it’s easy to get lost combinatorially. However, this type of problem is a typical example of where we can use basic dynamic programming.

Dynamic programming is where, instead of trying to do the whole thing at once, you build up gradually piece by piece. In this case, we want to consider very carefully what it means to go from one corner to the next.

Say we label the vertical lines as i = 0,1,2,\ldots,n and the horizontal lines as j = 0,1,2,\ldots,n for an n \times n grid. Any route from corner (0,0) to corner (n,n) can only go downwards and rightwards, and so there are only two options for which corner came before corner (i,j): either corner (i-1,j) or corner (i,j-1). Therefore, if f(i,j) is the number of routes possible to arrive at corner (i,j), then

(1)   \begin{equation*} f(i,j) = f(i-1,j) + f(i,j-1). \end{equation*}

Take a moment to see that that makes sense (it was a sudden realisation for me). Since we know that fact, we can now very easily start at the top-left corner of any grid and gradually work out the number of routes to every corner, eventually getting to the bottom-right corner which will give us our answer.

We start by setting up a matrix – or, in more programming-like-language, an array – which will eventually hold the number of paths to every corner on an x by y grid, but for now we’ll just fill with ones. To actually do this in Python, we can just initialise a list inside a list:

paths = [[1]*(x+1)]*(y+1)

This means paths has y+1 entries, each of which is a list itself with x+1 entries; if you like, an array with y+1 columns and x+1 rows.

Of course, we already know that there is one possible path to the very first corner: that is, just start there and end there. So, we do paths[0][0] = 1 to set this initial value.

Then, we just want to loop through the array, going through one row at a time, setting each value using the rule in equation (1). Finally, once we’ve got to the end, we just return the value at corner (x,y), that is, the number of paths to corner (x,y), because that’s all we care about:

def PathsToPoint(x,y): # This is using basic dynamic programming
    paths = [[1]*(x+1)]*(y+1) # Matrix containing number of paths to each point
    for i in range(1,x+1):
        for j in range(1,y+1):
            paths[i][j] = paths[i-1][j] + paths[i][j-1]
    print(paths)
    return paths[x][y]

print(PathsToPoint(20, 20))

And that’s the whole program! It’s an elegantly simple approach.

If you start to write out the values of this array, you’ll see that they match the values of Pascal’s triangle, starting at the top-left corner. This makes perfect sense: you write out the values of Pascal’s triangle by adding the two numbers directly above the one you’re trying to find, which is exactly what this code is doing if you rotate the array clockwise by 45 degrees. In fact, this whole program can be replaced by a single combinatorial calculation. Each possible path to (x,y) contains x horizontal segments and y vertical segments: so, each path will contain x+y segments overall. If you imagine starting from the beginning and repeatedly choosing whether the next segment should be horizontal or vertical, it’s easy to see you have to choose a horizontal segment exactly x of these times. Therefore, the problem is reduced to ‘how many different ways are there of choosing x objects out of x+y?’, a problem with a well-established solution:

    \[C(x+y,x) = \frac{(x+y)!}{x![(x+y)-x]!} = \frac{(x+y)!}{x!y!}\]

which, if x = 20 and y = 20 as in the question, reduces to

    \[\frac{(20+20)!}{20! \cdot 20!} = \frac{40!}{(20!)^2} = 137846528820\]

which is exactly the same answer that our program returns.

Leave a Reply

Your email address will not be published. Required fields are marked *