The problem description in Problem 15 of Project Euler contains a figure, which I wont copy, so go ahead an read the full description at the Project Euler site. The problem can be understood without it though. The problem reads

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

How many routes are there through a 20×20 grid?

My first question for many of the problems has been – Can it be brute forced? And my best answer to that is “probably”, but I cannot figure out how to generate all the routes. So instead I will give you two other approaches, which are both efficient. One is inspired by dynamic programming and the other gives an analytic solution using combinatorics.

## Dynamic Programming

Dynamic programming is an optimization technique where you can minimize or maximize some function. Dynamic programming relies on an important property; the problem must have an optimal substructure . What it means is that you need to be generate a solution based on solving smaller problems. One example, if you want to find the shortest route , you can use dynamic programming, if you can find the shortest route of a part of the problem independent of how you got to the start point of the shorter distance you are trying to find.

Confused? Don’t worry too much, we will cover it all again in a later problem and you will hopefully get the hang of what I mean through this problem. The problem we are currently trying to solve is not about optimization, but rather counting. However, the solution is still heavily inspired by the techniques in dynamic programming.

Instead of solving the whole problem, lets solve the problem for the scenario where we stand in the point just to the left or above the end point as marked in the figure to the right, no matter how we got to that point, we only have only one possible path to follow to reach the goal.

Now that we have solved one subproblem, we can expand that by solving the problem where we stand two grid points to the left. That point gives us one option to continue, no matter how we got to that grid point. From there we only have one option to get to the goal. Using that argument we can solve the problem for all bottom and all the rightmost points in the grid.

So far it has been rather trivial with only one path to follow, but it gives a nice boundary condition for the algorithm as we shall see later on. But let us move inside the grid. If we stand in the green grid point on the figure below, we can move right – from where we already know that we have 1 option to complete the path, or we can move down where we also have 1 option to complete the path. So that gives us a total of 2 different paths to take from the green point.

Now that we know we can make 2 paths from the green point, we can figure out how many paths we can make from the blue grid point. If we move down, we have 1 path, and if we move right we have 2 options to complete the path. So in total we can choose between 3 paths to get from the blue grid point to the end.

Iteratively we can solve larger and larger sub problems once we have solve a smaller sub problem, since we can calculate the number of paths by adding the number of paths from the point below with the number of paths from the point to the right. Under the assumptions that we know the number of paths in these points. The deducted boundary conditions ensures us that we can always find such a point, and by going through the whole grid, we can calculate routes all the way until we reach the top most point.

If we continue these calculations until we have filled the 2×2 grid as I have done in the figure to the left, we end up with 6 paths, just as the example in the problem formulation.

That should be rather easy to make an algorithm that does this for us. There is only one little note I want to make, even if it is a 20×20 grid, we have 21×21 grid points, so the algorithm looks like

const int gridSize = 20; long[,] grid = new long[gridSize+1, gridSize+1]; //Initialise the grid with boundary conditions for (int i = 0; i < gridSize; i++) { grid[i, gridSize] = 1; grid[gridSize,i] = 1; } for (int i = gridSize - 1; i >= 0; i--) { for (int j = gridSize - 1; j >= 0; j--) { grid[i, j] = grid[i+1, j] + grid[i, j+1]; } }

And the execution gives us

In a 20x20 grid there are 137846528820 possible paths. Solution took 0 ms

It scales squared with side length of the grid, so it scales really well, however the number of paths explodes with large grids, so we will rather quickly face problems with using longs for storage. However that is another problem which can be circumvented using BigInteger as described in the answer to Problem 13.

## Combinatorics

The kind of problem we solve here is treated in this book Notes on Introductory Combinatorics by George Polya et al. I haven’t read it but it has been recommended to me by a friend, when I said I wanted to know a bit more about combinatorics.

In order to pose the question as a combinatorics question, we must realise a few things. I have generalised the observations to an NxN grid.

- All paths can be described as a series of directions. And since we can only go down and right, we could describe the paths as a series of Ds and Rs. In a 2×2 grid all paths are 1) DDRR 2) DRDR 3) DRRD 4) RDRD 5) RDDR 6) RRDD.
- Based on the example we can see that all paths have exactly size 2N of which there are N Rs and N Ds.
- If we have 2N empty spaces and place all Rs, then the placement of the Ds are given

Once we have made these realisations, we can repose the question as

In how many ways can we choose N out of 2N possible places if the order does not matter?

And combinatorics gives us an easy answer to that. The Binomial Coefficient gives us exactly the tool we need to answer the above question. The question is usually posed as

And using the multiplicative formula we can express it as

We could also express it as a factorial expression, but that usually gives problems with very large numbers when we try to make the calculations.

Wikipedia has a suggested implementation for the multiplicative formula that I have used to get the result so the code looks like

const int gridSize = 20; long paths = 1; for (int i = 0; i < gridSize; i++) { paths *= (2 * gridSize) - i; paths /= i + 1; }

and the result is

In a 20x20 grid there are 137846528820 possible paths. Solution took 0 ms

This solution has a smaller implementation and will be significantly smaller in memory usage than the first approach. However both works really fast.

## Wrapping up

I gave you two different possible solutions which aren’t really related at first view. However, Samual Jack over at Functional Fun, more or less connects the two approaches. From the grid, he deducts pascal’s triangle, and from there it is fairly easy to take it the last step to binomial coefficient and the multiplicative formula.

As usually the source code is available.

I’v been doing these problems in order, and this one definitely stands out as the toughest. It’s very hard to wrap your head around how to find the paths. I’m still not quite sure how this works, but I will keep reviewing your solution until I do.

Thanks again for a great blog!

Thanks again. I think both of these solutions are pretty good, but they require some fundamental insights into dynamic programming and combinatorics. But don’t be shy to ask questions if there are things that aren’t explained well enough.

Hi! I am not able to get my head around this part!

//Initialise the grid with boundary conditions

for (int i = 0; i < gridSize; i++) {

grid[i, gridSize] = 1;

grid[gridSize,i] = 1;

}

I could identify that the problem needed dynamic programming but failed to recognize this init step. Can you please explain what that for loop means? Does it mean there is atleast one path from the destination to all other points in the lattice?

It means that then you are on the lower or the right boundary, there is exactly one path to the goal. You can only continue along the border you are on.

this is the best explanation , i agree this is the most difficult to understand if you start sequentially . i solved this recursively – https://gist.github.com/dekajp/5227749

I managed to solve this problem instantly and without the need for any programming. This little pattern helped me: https://en.wikipedia.org/wiki/Pascal's_triangle#Overall_patterns_and_properties

heh, kind of cheating, but you cant argue with the efficiency 😉

Nope, not cheating. It is called thinking, and that prvides the best solution.

Is it possible to solve this using binary trees?

I honestly have no idea 🙂

When considering the possible paths (tracing them out with your finger), you might whisper “Up, right, up, right…”.

Why not write those thoughts down? Using “u” and “r” we can write out a path:

r r r r r r r u u u u

Well I was writing it down but with D and R instead?

Kristian,

I was wondering how to scale this. If I was wanting to do a 27X27 grid how would that change the code?

Thanks,

Andrew

All you needed to change is the gridsize constant. The last method wont change very much. You might run into problems with integer overflow, I am a bit uncertain of that.

The first method will get a bit longer run time, but not much.

The brute force solution of this problem is by using recursion.

My code (in Python):

def find_route(n,route):

global nroute

(x,y) = route[len(route)-1]

p1 = (x+1,y)

p2 = (x,y+1)

route1 = route + [p1]

route2 = route + [p2]

if (p1 == (n,n)):

nroute = nroute + 1

elif (p2 == (n,n)):

nroute = nroute + 1

else:

if (x+1 <= n): find_route(n,route1)

if (y+1 <= n): find_route(n,route2)

def problem_15(n):

global nroute

bt = time.time()

route = [(0,0)]

nroute = 0

find_route(n,route)

print "In a "+str(n)+"*"+str(n)+" grid there are "+str(nroute)+" paths."

et = time.time()

print "Solutions took "+str(et-bt)+" sec."

On my computer it works up to around n = 12, thereafter it takes far to long.

Thank you for your very interesting blog!

What is the point of the “gridSize+1” under “initializing”? You start counting from 0. Also, you never seem to go over the value of gridSize in the loops. Thanks for the awesome help! Keep it up!

That is because a 2×2 grid has 3 nodes in each dimension. That is why I do it this way. I then initialise the grid in the “gridSize” point, and since I am starting to count from 0, this is the 21st point in the array.

Hi Kristian, first of all, i love your posts about the project euler problems as these provide an alternative thinking to the approaches i choose to use myself, secondly wonder if you have any tips on how to reach the effecient solutions that you have reached in many of your posts.

Btw here is my “brute force” solution which is to slow to solve the problem within any reasonable amount of time(you simply set the arguments to 0)

Great solution, it works very fast. How did you get this idea? Thanks.

long[,] grid = new long[gridSize+1, gridSize+1];

i dont understand the format [gridSize+1,gridSize+1].

plss explain…

int gridSize = 20;

long paths = 1;

for (int i = 1; i <= gridSize; i++)

{

paths = paths * (gridSize + i) / i;

}

Table 1

Routes through a n×n grid, (1 =< n <= 30)

Re: Project Euler – Problem 15

Lattice paths

http://img11.hostingpics.net/pics/734285pe15tab1lattice.jpg

Results in Table 1 were obtained with Central binomial coefficient method (1)and Kristian's algorithm (2).

Central binomial coefficient method: overflow with Excel (4) at n=30.

It would have been interesting to get the results in nanoseconds.

("System.Diagnostics.Stopwatch" does not contain a definition for "ElapsedNanoseconds").

___

Sources:

1) Central binomial coefficients: C(2*n,n) = (2*n)!/(n!)^2.

A000984 – OEIS

https://oeis.org/A000984

and references cited therein.

2) Project Euler – Problem 15

Kristian's Algorithm

http://www.mathblog.dk/files/euler/Problem15.cs

3) Microsoft Visual C# 2010 Express

4) Microsoft Office Excel (2007)

Thanks. I wanted to know how to solve this kind of problem. Thanks for th e explanation.

Here is my solution. It is recursive but uses a cache for storing positions, that have already been reached.

This can be solved with a single calculator, no program needed. As you said, in all paths there are exactly 40 steps, half of them down, and half of them right. So, if we write it just as a string with characters D and R and find all distinct permutations of it we find the answer we want. We must find the permutations of 40 elements, in which we have 20 D and 20 R. So a simple answer is 40!/(20!*20!). Therefore the answer for any grid of this problem is (2N)!/(N!*N!). The (!) mark is for factorial.

Right now, i’m bruteforcing it (of course i made sure that the algorithm works before). Took 10 minutes so far. I’m starting to doubt that it can be bruteforced in reasonable time.

I’m doing it in java with a neat little recursive method:

x and y are the current position (should be 0,0 on the first call). maxXY obviously is the size of the grid (2 for 2×2).

I had to increase the default stack-size of the JVM in order to get so far, otherwise you’d get stackoverflow errors.

Now that i think of it, i probably should use longs instead of ints.

Just in case anyone is interested, i’m measuring the time for my naive recursive approach above (or below, don’t know which gets approved first).

Interestingly, the time it takes seems to be increasing precisely exponentially (base 4).

I’ve got to size = 19×19 so far, looking at the those number it will take another 30 minutes to calculate it for 20×20.

Number of Routes for 1×1 : 2 operation took: 0.006409ms

Number of Routes for 2×2 : 6 operation took: 0.004701ms

Number of Routes for 3×3 : 20 operation took: 0.008973ms

Number of Routes for 4×4 : 70 operation took: 0.067083ms

Number of Routes for 5×5 : 252 operation took: 0.399937ms

Number of Routes for 6×6 : 924 operation took: 0.240988ms

Number of Routes for 7×7 : 3432 operation took: 2.775634ms

Number of Routes for 8×8 : 12870 operation took: 0.636226ms

Number of Routes for 9×9 : 48620 operation took: 1.375854ms

Number of Routes for 10×10 : 184756 operation took: 4.415121ms

Number of Routes for 11×11 : 705432 operation took: 11.925912ms

Number of Routes for 12×12 : 2704156 operation took: 50.631397ms

Number of Routes for 13×13 : 10400600 operation took: 143.994571ms

Number of Routes for 14×14 : 40116600 operation took: 509.769413ms

Number of Routes for 15×15 : 155117520 operation took: 1965.275944ms

Number of Routes for 16×16 : 601080390 operation took: 7600.615459ms

Number of Routes for 17×17 : 2333606220 operation took: 29105.920613ms

Number of Routes for 18×18 : 9075135300 operation took: 113906.535986ms

Number of Routes for 19×19 : 35345263800 operation took: 443625.226567ms

So yes, it can be bruteforced. In a reasonable (“less than a lifetime”) time.

I’m going to carefully read through this article now (i didn’t want to spoil it for me before knowing that my approach works) because i don’t think i’m going to have too much luck with Project Euler, doing only naive brute-force approaches 🙂

def permutation(n, r){

if(n <= r) return 1

else return (BigInteger)(n * permutation(n - 1, r))

}

`def countRoutes(d){`

return permutation(d*2, d) / permutation(d, 1)

}

`println( countRoutes(20))`

Thanks Kristian for your analysis of DDRR DRDR DRRD etc etc, it came to me that the solution is simply nCr where n=4, r=2, or in the problem’s case, n=20, r=10

I did permutation instead of combination to optimize since combination would require factorial(20) which is quite big.

`def c(n, k){ f(n) / (f(n - k) * f(k)) }`

`@Memoized`

def f(n) { if(n <= 1) 1 else n * (BigInteger)f(n - 1) }

`def countRoutes(int d){ c(d*2, d) }`

`println(countRoutes(20))`

Are you sure its not 35 345 263 800?

Because 137 846 528 820 came from 21×21 grid for me, maybe I count the grid starting from 0 or something, oh well…

22×22 : 538 257 874 440

23×23 : 2 104 098 963 720

24×24 : 8 233 430 727 600

25×25 : 32 247 603 683 100

The number of routes possible on each node of the grid is a number on pascals triangle. Here you can specify a width and height for the grid.

If n = width and r = width+height for r <= n, then the path count is (n r) or n!/(r!*(n – r)!)

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

long pascals_triangle(unsigned row, unsigned col)

{

// Triangle row number can be no bigger than the col number

long i;

if(col > row) {

col = i;

col = row;

row = i;

}

// Create an array to hold the bottom triangle row

long* array = malloc((row+1) * sizeof(long));

if(array == NULL) exit(1);

// Start with a 1.

memset(array, 0, row*sizeof(array[0]));

array[row] = 1;

// Array will be filled as so

// 0 0 0 0 1 row 0

// 0 0 0 1 1 row 1

// 0 0 1 2 1 row 2

// 0 1 3 3 1 row 3

// 1 4 6 4 1 row 4

while(array[0] == 0) {

for(i = 0; i < row; ++i)

array[i] += array[i+1];

}

i = array[col];

free(array);

return i;

}

int main(void)

{

int width, height, n, r;

printf("Enter grid width and height : ");

scanf("%d %d", &width, &height);

n = width + height;

r = height;

printf("A %d * %d grid has a total of %lu paths\n",

width, height, pascals_triangle(n, r));

return 0;