David Poblador Garcia

It’s been 2 months since a nice girl at Google told me I won the Google Treasure Hunt 2008. One week ago, I got my present: a T-shirt and an engraved iPod Nano stating “Google Treasure Hunt ‘08 Winner”. I must admit I’m really surprised. I could have never imagined I had a single chance to be one of the winners. I can’t figure out how many people took part in the contest.

It’s particularly suprising given the fact that I’m not that good at maths and my prime number “skills” are scarce nowadays. It’s time now to try to explain how I managed to solve out the “games”.

The robot

A robot is located at the top-left corner of a X x Y grid (marked ‘Start’ in the diagram below).

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

How many possible unique paths are there?

Quick facts:

• 2×2 grid: 2 possible ways
• 3×2 grid: 3 possible ways

So far, so good… What about a 30×40 grid?

I bet I was not the only naive guy who tried to get it by using a bruteforce 4 line Python script… OK… it took me less than a minute to realise that it wouldn’t work out (before 2040).

So…

What the heck? Let’s make use of some combinatorics.

In a 4×4 grid, the robot must move exactly 3 times to the right and 3 times downwards… So…

DDDRRR
DRDRDR
…

So… <hint>how many ways you can permute 3 R and 3 D in an 6 move set?</hint> I expanded that to the big grid, et voilà!

Simplicity is prerequisite for reliability.
Edsger Dijkstra

Tags: brute force, google, google treasure hunt, ipod, python, tshirt

This entry was posted on Monday, October 6th, 2008 at 2:53 am and is filed under Just for fun. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.