« Blog » 2008-10-21

Treasure hunting robots

Created 2008-10-21T09:58:58.965Z, last edited 2008-10-21T10:28:49.697Z

This question is stolen from Google, and is one that I went through in a short session at BarCamp 2. Firstly you'll want to head over to http://treasurehunt.appspot.com/historic/robot/ and get yourself your own personal question. Mine was:

A robot is located at the top-left corner of a 54 x 42 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?

When we discussed this one at BarCamp there were two general approaches:

  1. Use some clever maths to work out it — the numbers are quite big and involves factorials of some big numbers though.
  2. Brute force it by searching.

I have a C++ program that brute forces it. Although it checks hundreds of millions of paths per second it's still taking quite some time to complete and I'm worried that a 64 bit unsigned integer isn't going to be large enough to hold the result.

What I hope will happen is that some bright spark will be able to solve it using method 1 before my brute force program completes — you'd best all get cracking!