FSharp.it

A couple of days ago Google launched a contest called Treasure Hunt 2008, which will be composed of 4 puzzles.

Only the first of these quizzes is already available at http://treasurehunt.appspot.com/, and the new ones will be posted once per week.

At the end of the four puzzles there will be some prizes, even if nothing has been revealed yet.

Here is the description of the first puzzle:

A robot is located at the top-left corner of a n x k 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 of the grid.
How many possible unique paths are there?
(Note: Answer must be an exact, decimal representation of the number. Image not to scale.)

If the number of rows is r and the number of columns c, the robot can move r-1 steps down and c-1 steps to the right to get to the bottom-right corner of the grid.

The number we want to find is the combination of r1 and c1, and this can be easily computed using the binomial coeficient:

Let’s assume r1 = r-1 and c1 = c-1, and write some F# code to get the solution to our problem:

#light
open Microsoft.FSharp.Math.BigInt

let robot rows columns =
  let r1 = rows - 1I
  let c1 = columns - 1I
  (factorial (r1 + c1)) / ((factorial r1) * (factorial c1))

This first puzzle was very easy to solve, if you go to the Treasure Hunt website now, you’ll find the next exercise.

I’ll give it a try, if you are interested just drop a comment and we’ll discuss it here.