Google Treasure Hunt 2008: the bot in the checkerboard problem

I have the solution to the bot in the pseudocheckerboard problem for the Google Treasure Hunt 2008 .

(I have munged some of the key points here, so don't feel sorry if you can't replicate it.)

It took me moments to figure out that it was not a series problem. It was immediately obvious to me that I needed to count the paths.

It took me an hour to devise a solution in Python with a random bot that traced all possible paths (computationally intractable for 8x8 and bigger checkerboards), and put them into a Set. The only way to interrupt this program was with Ctrl+C (skip to the end of this article for program listings).

It took me thirty minutes to devise a much faster, deterministic recursive solution in Python which essentially acts as a lazy tree lookup, which is also computationally intractable for 12x12 and bigger checkerboards.

It took me twenty minutes to reduce this solution to a two-variable recursive by-parts function that I couldn't simplify to a sum or a product or any other computationally tractable form. It's not impossible to do, because there IS a way to do it, but my limited math skills didn't allow me. In essence, my program is just this:

f(0,0) = 0
f(m,0) = 1
f(1,n) = 1
f(m,n) = [not gonna tell you]

It took me another thirty minutes to dabble in freshly installed Haskell and Scilab, but Scilab was impossible to use and Haskell (while letting me declare a function by parts) was just ten times slower than Python. So much for functional languages.

However, my last Python solution allowed me to generate a permutation of tables with OO.o and discover that there IS a progression embedded in the tables, and that said progression needs to be folded unto itself several times (the length of the progression and the number of folds are equal to the dimensions of the checkerboard). I reverse-engineered the progression using OO.o formulas. This is how one of the tables looks.

./googlebotproblem 7 4
[1, 1, 1, 1]
[1, 2, 3, 4]
[...snipped...]
84

Once I figured it out, I wrote a ten-liner Python script that replayed the OO.o formulas onto a row of data. Lo and behold, in less than a second I had the answer.

Other people just coded the exact same algorithm I devised for trees, but with a twist: they used a cache to speed up computation. Never occurred to me -- it should have. However, I have yet to see someone who actually folded the problem into a formula, nor have I seen anyone who figured out the series trick.

I still don't know how to fold that formula into a computationally feasible one. Dear Lazyweb, care to enlighten me?

Source code

This is the source code of the three problems, in one file:

#!/usr/bin/env python

import sys

from random import choice
from sets import Set

rows = int(sys.argv[1])
columns = int(sys.argv[2])

class OutOfBounds(Exception): pass
paths = Set()
def generate_path():
    cols = columns
    row = 1
    col = 1
    path = []
    while not ( row == rows and col == cols ):
        if row == rows: movement = "right"
        elif col == cols: movement = "down"
        else: movement = choice(["down","right"])
        if movement == "down":  row = row + 1
        else:               col = col + 1
        path.append(movement)
    return path

def stumble():
    try:
        while True:
            try:
                path = generate_path()
                paths.add(" ".join(path))
                print len(paths)
            except OutOfBounds, e: pass
                #print "killed:",e
    except KeyboardInterrupt:
        paths = [ p for p in paths ]
        paths.sort()
        for p in paths:
            print p


# recursive solution
def rec(row,column):
    # breakaway condition
    if row == 1 and column == 1: return 0
    # options where there is only one possible path
    if row == 1 or column == 1: return 1
    recs = [...munged...]
    return sum(recs)

# table solution
def rowize(row):
    newrow = [1]
    for n in [...munged...]
        [...munged...]
    return newrow

def calculate(rows,columns):
    row = [1] * columns
    for n in [...munged...]
        row = rowize(row)
    return row[-1]

#print stumble(rows,columns)
#print rec(rows,columns)
print calculate(rows,columns)


# a solution with memoize to not explore alternative routes
cache = {}
# Removed, sorry!

print count(rows,columns)