Claudio Cherubino's blog Life of a Googler

19May/083

Google Treasure Hunt 2008, first puzzle in F#

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.)

Google Treasure Hunt 2008

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:

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.

Comments (3) Trackbacks (1)
  1. the answer is not clear to me.

  2. What exactly is unclear? Maybe I can try to explain it better.

  3. maybe the tricky part is NOT to use factorials (no problem with F# – thanks to BigInt – put even here it’s not very efffective).

    To solve this you just have to think of pascals triangle and you will get a recursive formula for the binominal coefficient that is better suited to calculate those numbers.


Leave a comment

(required)