Source code available on GitHub.
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 and the horizontal lines as for an grid. Any route from corner to corner can only go downwards and rightwards, and so there are only two options for which corner came before corner : either corner or corner . Therefore, if is the number of routes possible to arrive at corner , then
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
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 = [*(x+1)]*(y+1)
y+1 entries, each of which is a list itself with
x+1 entries; if you like, an array with
y+1 columns and
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 = 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 , that is, the number of paths to corner , because that’s all we care about:
def PathsToPoint(x,y): # This is using basic dynamic programming paths = [*(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 contains horizontal segments and vertical segments: so, each path will contain 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 of these times. Therefore, the problem is reduced to ‘how many different ways are there of choosing objects out of ?’, a problem with a well-established solution:
which, if and as in the question, reduces to
which is exactly the same answer that our program returns.