19 May 2008

Earlier today, I spotted a tweet from @thomasj about the Google Treasure Hunt. This was followed later in the day by a series of tweets from @graham_alton (warning: spoiler in tweets!) that picqued enough interest that I decided to have a go.

In summary, the challenge is to state how many unqiue paths there are across an arbitrarily sized chessboard from the top-left corner to the bottom-right corner, but only moving down or right at each step. Graham has written up his solution, along with the original question on his blog.

He has gone straight for the proper solution using a simple formula… and some perl to handle the fact the numbers involved are beyond most desk calculators.

I decided to go for a bit more of a brute force approach… and some python to handle the fact I haven’t touched perl in a while.

Here’s my solution:

#!/usr/bin/python
# the dimensions of the board
w=54
h=30
lr = [1]*w
for y in range(1,h):
   lc = 1
      for x in range(1,w):
         lc = lc + lr[x]
         lr[x] = lc
print lc

The secret here is that for any given square on the board, the number of unique paths is equal to the sum of the number of unique paths from the squares immediately to the right and below.

Here’s an attempt to express it slightly more formally:

f(x,y) = f(x+1,y)+f(x,y+1)

where f(w,y) = f(x,h) = 1

The next question of the treasure hunt is due any minute now…

  1. kybMay 19, 2008

    When you can express it like that, a functional programming language is ideal for representing the problem. In haskell, it’s very similar to the maths you’ve written

    paths :: Int -> Int -> Int
    paths _ 1 = 1
    paths 1 _ = 1
    paths w h = (paths (w-1) h) + (paths w (h-1))

    Sadly, this very simple clean result doesn’t run particularly fast because of all the unnecessary recalculations. It’s fine for reasonable sized chess boards, but for 54×30, it just takes too long.

    Fortunately, I can rewite it using infinite list data structures to do calculations for boards up to 700×700 pretty quickly.

    pathlist 1 = 1 : (pathlist 1)
    pathlist w = 1 : zipWith (+) (tail (pathlist (w-1))) (pathlist w)
    lpaths w h = (pathlist w) !! h

    > lpaths 54 30
    34795281102777926433648

    >lpaths 700 700
    294959524837744306828252296100196431889118842418611448310042626887713844240301344669221418924201133834586362108669293514159261183838468398317529191441988702194010301504997962347728460441001014741345267577517951466709716033852841470615296707712692490701757399994671266386683080388904495703431988378768656808247129499221896960761043426375293304777943548918650717879698187751931573856298150842797277067333789380956594922720

    The idea is that (pathlist w) is a function that returns an infinite list of all boards w x h, so the first number is w x 1, the second is the number of paths for w x 2 and so on. The zipWith simply calculates the same way I was doing by hand – it’s the number above plus the number to the left going on for ever.

  2. kybMay 19, 2008

    Garh! I forgot that the !! operator uses 0 indexing, so I’ve actually worked out the paths for 54×31 there, and 700×7001.

    The line should of course have read
    lpaths w h = (pathlist w) !! (h-1)

    Giving the much more reasonable
    12576607627510093891680 as the answer for 54×30. Stupid functional languages make writing code terser, but they don’t make you do unit tests…..

  3. trackback from Graham White: My NotesJune 3, 2008

  4. leave a comment

    You must be logged in to post a comment.