Solving Lattice Path

SPOILER: if you want to or are working on the exercises from Project Euler, you should stop reading now!

According to Wikipedia, Project Euler is a website dedicated to a series of computational problems intended to be solved with computer programs [1].

[1] http://en.wikipedia.org/wiki/Project_Euler

The problems are mostly math related and one main characteristic of most problems is that they are usually hard to solve through brute force because they usually have polynomial/exponential complexity and questions always ask for very large input or number of inputs.

Problem 15, Lattice Paths, is one that I found really interesting because it's a geometric problem and with an intuitive solution. Let me copy here the text from the problem.

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
/images/lattice_path.png
How many such routes are there through a 20×20 grid?

So my first reaction was: I'll just do a brute force algorithm and see what happens!

I wrote an algorithm that uses recursion to find all possible paths. This is how it ended up:

 class LatticePath
   def initialize(size)
     @size = size
   end

   def total
     moves(0, 0)
   end

   private

   def moves(rows, cols)
     return 1 if rows == @size && cols == @size
     return 0 if rows > @size || cols > @size
     return moves(rows + 1, cols) + moves(rows, cols + 1)
   end
 end

 sides = (ARGV[0] && ARGV[0].to_i) || 20 # default value if none specified
 lattice_path = LatticePath.new(sides)
 puts lattice_path.total

Well, how bad could it be? Turn outs very bad.

Running this for less than 13 sides was OK. Running this for 14 sides was enough to take quite some time. Running for more than 14, it just takes too long. I suppose it would take years for 20 sides. It obviously explodes in complexity very quickly.

Looking up for ways to solve this or similar problems, I ended up watching this video from Khan Academy where Salman basically gives it away!

Path Counting Brain Teaser

I will not try to re-explain what's in the video so you should watch it first. I'll follow from where the video ends, and will develop an algorithm that only requires an array of size equal to one _side_ of the matrix to solve this problem.

Basically after filling in values for each cell, what we get is an matrix like this:

/images/full_grid.png

And looking more carefully, we can see that this matrix is symmetric. The coloring I used on the pictures should make that clear. We are interested in the value on the main diagonal so we can remove everything below it.

/images/half_grid.png

The next step was to recognize that each cell depends only on the cell to the left and above it. The element in the diagonal is always the element above it multiplied by 2 and the other elements in that row are the sum of the element in the cell to the left with the element in the cell above them. The picture below should make it clearer.

/images/grid_formula.png

Now even more interesting is observing that every element only depends on the elements exactly above them and once a new row is calculated from the row above it, the former is not necessary anymore. So in the end the whole problem can be solved by a simple array of size equal to the number of cell on one side of the square matrix!

And here's my optimized solution to the problem:

 #!/usr/bin/env ruby

 def lattice_path(sides)
   a = Array.new(sides) { 1 }

   1.upto(sides - 1) do |col|
     a[col] *= 2
     (col + 1).upto(sides - 1) do |n|
       a[n] = a[n-1] + a[n]
     end
   end

   a[sides - 1]
 end

 sides = (ARGV[0] && ARGV[0].to_i) || 20 # default value if none specified
 puts lattice_path(sides + 1)

Have fun!

Comments

Comments powered by Disqus