// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (23 votes, average: 4.78 out of 5)
Loading...

Project Euler Solutions

Project Euler 15 Solution

Project Euler 15 Solution

Project Euler 15: Find the number of routes from the top left corner to the bottom right corner in a rectangular grid.


Project Euler 15 Problem Description

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

Project Euler 15 Solution

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

Analysis

This question has been posed as: “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 x n grid?”

Another analogy might be: “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 would assume an 8 × 8 grid.

This solution extends to solving n × m grids as well as the n × n grid by using a simple combination calculation. For example, 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 n Rs (rights) and n Ds (downs) the order is not important as long as you start from the top corner you will always end at the bottom corner.

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 can be considered independent and the Ds would be considered dependent because they have to be place into the remaining open slots.

For example, placing the 4 Rs 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 end up with just 8C4 = 70 valid combinations.

It has also be described as how many distinct ways can you shuffle the characters in the string “RRRRDDDD”.

Now, determining 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.
Pascal's Triangle

 {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!}

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank

Project Euler 15 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 15 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|137846528820|

Afterthoughts

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

Project Euler 15 Solution last updated

Discussion

No comments yet.

Post a comment