Select Page

Project Euler 15 Problem Statement

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?

Solution

To add some context to this problem a similar question would be: “Starting at the top left corner, how many ways through town are possible using only one-way streets and ending at the bottom right corner of a n×n grid?”

Another analogy is: “Place a single rook on the top left corner of an empty chess board and count the number of tours to the bottom right corner moving only left and down.”  This assumes an 8 × 8 grid.

The valid paths for a 2×2 grid shown in the example are the discreet (unique) permutations of {R, R, D, D}.  We can list these as: {R, R, D, D}, {R, D, R, D}, {R, D, D, R}, {D, R, R, D}, {D, R, D, R} and {D, D, R, R}.  You must have 2 Rs (rights) and 2 Ds (downs) the order not being important and as long as you start from the top-left corner you will always end at the bottom-right corner.

A 4×4 grid example

For a 4×4 grid it would be the discreet permutations of {R, R, R, R, D, D, D, D} where any combination or 4 Rs and 4 Ds will always be a valid path. If the Rs are place randomly in 4 of the 8 slots first they are considered independent and the Ds are considered dependent because they have to be placed into the remaining open slots.

For example, placing the 4 Rs randomly in any of the available 8 slots as {R, _, R, R, _, R, _, _} will dictate where the Ds get placed as {R, D, R, R, D, R, D, D}.  You will have 8C4 = 70 valid combinations, i.e., how many distinct ways can you shuffle the characters in the string “RRRRDDDD”.

Using the binomial coefficient

The number of contiguous routes for a square grid (n×n) is the central binomial coefficient or the center number in the 2nth row of Pascal’s triangle .  The rows start their numbering at 0.

 {2n \choose n} = \frac{(2n)!}{n!~\times~n!}

The formula in general for any rectangular grid (n×m) using the notation for the binomial coefficient is:

 {n+m \choose n} = \frac{(n~+~m)!}{n!~\times~m!}

HackerRank version

HackerRank includes rectangular grids in addition to square grids, increases the size to 500×500 and runs 1,000 trials.  This solution is fast enough to handle these parameters.

Python 2.7 Source

Last Word

  • Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A000984: Central binomial coefficients: C(2*n,n) = (2*n)!/(n!)^2.
  • Changing the condition “contiguous paths which do not pass below the diagonal on an n×n grid” to our problem statement, we would use a Catalan number. It is calculated as:
     \frac{(2n)!}{n!(n+1)!}