Treasure hunting robots

Created 21st October, 2008 09:58 (UTC), last edited 21st October, 2008 10:28 (UTC)

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!


Categories: