Google Treasure Hunt 2008

Google Treasure Hunt seems to be fairly interesting. There are three puzzles released so far; a fourth one will ensue at 1212448500 (that's new Date(1212448500 * 1000) for you JavaScripters). The first two are dubbed "robot" and "zip" by Google, the former sponsored by the Sydney office, the latter sponsored by the Mountain View headquarters. The latest one, which I call "route" (there is no official name for it yet officially named "network"), is sponsored by the San Francisco office.

The first solution can be easily solved by using an implementation of Common Lisp; I use Jatha. The reason is because the problem requires the calculation of a combination, which easily produces numbers exceeding the 32-bit limit of most machines. The Common Lisp standard requires numbers to be implemented in bignum, in other words, numbers of arbitrary precision and size. Below is a copy of robot.lisp that I wrote:

(defun ! (n)
  (if (<= n 1)
  1
  (* n (! (- n 1)))))

(defun C (n k)
  (/ 
    (! n)
    (* (! k) (! (- n k)))))

(defun unique-paths (x y)
  (C (+ (- x 1) (- y 1)) (- x 1)))

(defun unique-paths-simplified (x y)
  (/ 
    (! (- (+ x y) 2))
    (* (! (- x 1)) (! (- y 1)))))

It defines four functions, the first one is the factorial function, the second is the combination function (which uses factorial), the third one is the formula for calculating the unique paths the robot can take given an x by y grid, and the last is an algebraically simplified version of the third.
The formula is C((x - 1) + (y - 1), x - 1), or, algebraically simplified, (x + y - 2)! / (x - 1)!(y - 1)!. To use robot.lisp, download Jatha, and run the .jar in a terminal with the -nodisplay parameter. A prompt should appear. Then:

Jatha CL-USER> (load "/Users/kourge/robot.lisp")
T
Jatha CL-USER> (! 50)        
30414093201713378043612608166064768844377641568960512000000000000
Jatha CL-USER> (unique-paths 34 35)
14226520737620288370
Jatha CL-USER> (unique-paths-simplified 34 35)
14226520737620288370

The second problem gives you a zip file, which unzips to 255 files scattered in various nested directories. In short, the problem gives two criteria, each consisting of a line number, what should be in the path, and what the filenames should end with. It is easily solved by a simple Python script, although I've seen people solve it with Ruby as well. Here is a copy of zip.py that I wrote:

#!/usr/bin/env python
import os

path = "/Users/kourge/GoogleTreasureHunt08_18186358835933159127/"
conds = [(4, "vwx", ".pdf"), (1, "ghi", ".rtf")]

fs = []
for root, dirs, files in os.walk(path):
  for file in files:
    fs.append(os.path.join(root, file))

sums = []
for cond in conds:
  files = [x for x in fs if cond[1] in x and x[-len(cond[2]):] == cond[2]]
  sum = 0
  for file in files:
    file = open(file); r = file.read().split("\n"); file.close()
    if len(r) < cond[0]: continue
    if r[cond[0] - 1].strip() == "": continue
    sum += int(r[cond[0] - 1])
  sums.append(sum)
  print "sum of line %s for all files having %s in path ending with %s: %s" % \
    (cond[0], cond[1], cond[2], sum)

product = 1
for sum in sums: product *= sum
print "product: %s" % product

It is quite extensible; all it needs is a path, and at least one criterion in a list. Components of a criterion are stored in a tuple in the order of line number, what should be in the path, and what should the filename end with. It then walks the root path, collecting the full paths of all files in a list. Then it goes through the criteria, opening files that match for each of them, and summing the integers on each specified line.

The third problem is simple and can be solved by mentally following through the route table. The solution is a route that begins with a source node, which the problem identifies with a letter, and a destination node, which the problem identifies with an IP address. Each node consists of a letter, an IP address, three routing entries to other nodes, and a default route. The general way to follow is route is thus: starting from the source node, look for the destination address (or destination subnet) in the routing entries. If one of the routing entries maps the destination address or subnet to another address, then that mapped address is the next node. Else, the next node and be found in the default route. The solution route is typically about 11 nodes long, including the source and destination, and it should be inputed as a string of letters.

I will probably follow up on the last question and hopefully be able to provide an answer to it.

so, whats the purpose? I

so, whats the purpose? I mean how is google benefiting from this? perhaps it's their way of finding potential programmers to work at google :)