Project Euler – Lattice Path (Part 3)

I use a 2×2 grid trying to explain a recursive solution to problem number 15.

Credit for the algorithm goes to Pim Spelier, who wrote a nice solution on Project Euler, which is downloadable as PDF once you have submitted the correct answer.

The idea is to assign a tuple to each grid point, starting with (0,0) at the upper left corner. First row (0,0), (0,1), (0,2). Second row (1,0), (1,1)…you get the idea. The bottom right corner is (2,2).

Now we turn the grid into Pascal’s triangle.

lattice_path_recursive_1

Looking at the grid this way, it is now more transparent how the grid actually is a Pascal’s triangle. Starting from the top left corner, only one possible route exists to each grid point marked with a “1”. A grid point marked with a “2” can be reached by taking two different routes. Guess how many routes lead to a grid point with a “3”.

The number of lattice paths through the grid is the sum of the paths to (2,1) and (1,2): 3 + 3 = 6.

You can see that for every tuple containing a 0 like (0,0) or (2.0) and so on, we must return 1.

Every other grid point number is the sum of the two numbers directly above it.

This leads to the following recursive algorithm.

LatticePatchRecursive1

The function is called 11 times.

LatticePathRecursiveAlgorithm1Detail

Unfortunately this solution has a “minor” flaw, which is performance. Calculating the lattice path for a 20×20 grid on my iMac G5 takes over 10 minutes.

LatticePathRecursiveAlgorithm1RunningTime

A better performing algorithm will be the topic of an upcoming blog post.

One thought on “Project Euler – Lattice Path (Part 3)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s