// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (13 votes, average: 5.00 out of 5)
Loading...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.


Problem Description

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.

Determining the number of 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!}~.

Any combination using nDowns(D) and mRights(R) would be a valid move.

In the example provided in the problem description there would be (2 + 2)! or 24 possible moves, but many would be indistinguishable, and we would have to divide by (2! × 2!) to eliminate them. So, (2 + 2)! / (2! × 2!) = 24 / 4 = 6. Namely, RRDD, RDRD, RDDR, DRRD, DRDR and DDRR. By indistinguishable we mean DDR1R2 is the same move as DDR2R1.

Project Euler 15 Solution

Runs < 0.001 seconds in Python 2.7.
from Euler import factorial as fact, binomial

n, m = 20, 20
# method 1, n == m, square grid, central number in row 2*n of Pascal's triangle
if n == m:
    print "Project Euler 15 Solution (square grid) =", binomial(2*n, n)

# method 2, n != m or n == m, rectangular grid
print "Project Euler 15 Solution (rectangular grid) =", fact(n+m) / (fact(n)*fact(m))
Use 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|

Comments

  • 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 “which do not pass below the diagonal” to our problem statement, we would use a Catalan number. It is calculated as 2n! / n! / (n+1)!
Project Euler 15 Solution last updated

Discussion

No comments yet.

Post a comment