Project Euler Problem #15:

Problem #15 is yet another example of how having a decent background in mathematics can give you a huge edge in tackling Project Euler. The question reads:

Project Euler Problem 15: Lattice paths
Starting in the top left corner of a 2x2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20x20 grid?

This type of problem has appeared so many times on introductory math competitions such as the AMC 10/12 and Mathcounts that most serious math students know its answer by heart. Having this knowledge results in the following solution:

Solution #1 : Basic Combinatorial Approach

The key observation here is that every path can be interpreted as a series of moves to the right and moves down. If we let a move to the right be an “R” and a move down be a “D”, then we can rewrite the paths in the diagram as RRDD, RDRD, RDDR, DRRD, DRDR, and DDRR. Every sequence with 2 R’s and 2D’s is represented in this list. Thus, there is a one-to-one correspondence between paths on an mxn grid and sequences of m R’s and n D’s. The number of such sequences is the same as the number of ways to choose the m spots for the R’s out of the m+n possibilities, as all of the remaining spots will automatically be filled by D’s. The order these positions are chosen does not matter as any two R’s or two D’s are indistinguishable. Thus, for an mxn grid the answer is (m+n) choose m.

At this point this problem is a simple matter of implementing a combinatorial function. Here is an implementation of this function in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Combinatorial Approach to Project Euler Problem #15
 '''

 import time

 def projectEulerProblemFifteen(r, c):
     total = 1
     for i in range(1,(c+1)):
         total*=(r+c+1-i)
         total/=i
     return total

 start = time.time()
 print projectEulerProblemFifteen(20, 20)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints
 137846528820
 --- 1.50203704834e-05 seconds ---
 for input of r = 20, c = 20
 '''

As shown above, understanding combinations is a critical component of solving Project Euler problems. I believe this is the shortest solution in any of my posts so far.

Thanks for reading.