Monday, 19 May 2008

Google Treasure Hunt

I've just discovered today (rather late I know) that Google have released a treasure hunt which is quite interesting. It's not what you might think. Given the name, I would have guessed it involved using the google search engine to find things on the Internet. However, it's actually a problem solving challenge where they pose questions and you submit your answer. I think question 2 is due out today (they obfuscate when the next question will be released), nobody seems to know how many questions there are, exactly how long this will go on for, etc. But there is a prize for "the first person to answer all the questions correctly" whatever that means.

A word of warning, don't read the rest of this if you want to work out the answer yourself!!!

My question number 1:
Google Treasure Hunt Q1
A robot is located at the top-left corner of a 65 x 61 grid (marked 'Start' in the diagram above)*.

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 (marked 'Finish' in the not to scale diagram below).

How many possible unique paths are there?
(Note: Answer must be an exact, decimal representation of the number.)

The problem here is the vast number of different routes that can be taken, which would overflow 32 bit computers for numbers this size. My (correct) answer was 1426507627253102510231886503468838531 which I calculated using the formula (x+y-2)! / ((x-1)! (y-1)!)

A few simple lines of Perl later and I had the answer:
#!/usr/bin/perl -w
use strict;
use Math::BigInt;
# change these to match your X & Y grid size
my $xgrid = 61;
my $ygrid = 65;
my $x = Math::BigInt->new($xgrid-1)->bfac();
my $y = Math::BigInt->new($ygrid-1)->bfac();
my $z = Math::BigInt->new($xgrid+$ygrid-2)->bfac();
print $z->bdiv($x->bmul($y))."\n";

No comments: