Every now and then i have the need to solve some programming related puzzles. There are many in the web, my current favourites are Project Euler, Ponder this and the security/hacking related exercises at Bright Shadowns. Today i tried one of the Google Treasure Hunt questions and documented my solution along the path. Off we go!

A robot is located at the top-left corner (S) of a 36 x 55 grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner (F) of the grid. How many possible unique paths are there?

First i manually tried it to grasp the idea of calculating the number of paths automatically. Because the robot can only move down or right, there is one possible path for all rightmost and bottommost cells. For an inner cell (not rightmost and not bottommost) the robot can advance by using the bottom or right neighbor cell, i.e. path count for a cell is simply the sum of the bottom neighbor cell and the right neighbor cell. Doing this step manually for a 4x4 grid i got the following matrix.

 S ? 4 1
 ? ? 3 1
 4 3 2 1
 1 1 1 F

And then it hit me. If you rotate the matrix, there is a mathematical structure that looks exactly the same.

     F
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

Yes, it's Pascal's triangle. So the right solution for a grid is somewhere in the triangle.

Writing Pascal's triangle in Haskell is a straightfoward task. Thanks to Haskell's laziness and higher-order functions the implementation is a simple one-liner:

pascal :: [[Integer]]
pascal = iterate (\x -> zipWith (+) (0:x) (x++[0])) [1]

The function generates a list of lists of ''Integer'', where the ith element is the ith row in the triangle. Taking the first 7 elements (read rows):

$ take 7 pascal
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1],[1,6,15,20,15,6,1]]

The missing part is the selection of the right element of the triangle. I mapped a grid to the triangle for calculating the row and element index. In the following triangle with 5 rows and 4 columns the row index is shown:

        F
       2 1
      3 2 1
     4 3 2 1
    5 4 3 2 _
   _ 5 4 3 _ _
  _ _ 5 4 _ _ _
 _ _ _ S S _ _ _

For a XxY grid the row index in the triangle is calculated by rows + columns - 1 and the element index by either selecting the Xth or Yth element (they both have the same distance from the vertical axis).

solution :: Int -> Int -> Integer
solution x y = pascal !! (x + y - 2) !! (x - 1)

The solutions for the 4x4 and 36x55 grid above:

$ solution 4 4
20

$ solution 36 55
6920581868511832633307448

Seems quite right and 10 minutes later Google Treasure Hunt confirmed my solution.