Wednesday, May 28, 2008

Google Treasure Hunt 2008: Puzzle 3 (network) solution

First I was kind-of proud to turn in the solution about 32 minutes after the puzzle was published, in spite of phone calls and other diversions. Then I noticed that I could hand-check my program's result in about two minutes. So this was mainly a test whether people are stupid enough to write a program instead of doing it manually (the fast way).

I happened to have some longest-prefix matching code ("patricia") lying around from another project. For brevity, this is not included. Feel free to ask me if you want this.

The nice thing about this solution is that it is quite general and pretty close to fully automated. If you have GNU Emacs and a Common Lisp system, you can cut&paste the puzzle from the browser (Firefox), convert it into Lisp form using the GNU Emacs command in the code, and then run the routing code with the given source and destination.

(Maybe I'll add dijkstra to it so that it can compute the routing table by itself, to make it useful as a simulator for traffic engineering experiments. :-)


;;;
;;; Google
;;; Google Treasure Hunt 2008
;;; Hello Simon Leinen
;;; Question
;;;
;;; Below is a diagram of a computer network. The nodes are hosts on
;;; the network, and the lines between them are links. A packet is
;;; sent out from host P with a destination of 179.111.105.159. Which
;;; nodes does the packet pass through on its way to the destination?
;;; (include start and final node in your answer)
;;;
;;; Network
;;; Here is a network routing table you'll need to determine the path taken:
;;; Node Ip address Routing table entry Routing table entry Routing table entry Default route
;;; A 73.109.79.84 8.158.16.5 => 143.130.31.174 30.235.90.120 => 202.180.56.184 111.60.99.0/24 => 192.149.202.205 212.37.231.51
;;; B 143.130.31.174 8.158.16.5 => 124.48.79.11 30.235.90.120 => 192.149.202.205 222.240.122.0/24 => 202.180.56.184 73.109.79.84
;;; C 124.48.79.11 212.37.231.51 => 212.37.231.51 111.60.99.67 => 143.130.31.174 192.149.202.0/24 => 103.163.170.32 190.170.232.73
;;; D 103.163.170.32 179.111.105.159 => 13.250.207.24 30.235.90.120 => 124.48.79.11 143.130.31.0/24 => 179.111.105.159 222.240.122.249
;;; E 13.250.207.24 111.60.99.67 => 247.230.125.27 222.240.122.249 => 103.163.170.32 8.158.16.0/24 => 111.60.99.67 8.158.16.5
;;; F 111.60.99.67 124.48.79.11 => 8.158.16.5 192.149.202.205 => 179.111.105.159 212.37.231.0/24 => 247.230.125.27 13.250.207.24
;;; G 179.111.105.159 111.60.99.67 => 30.235.90.120 103.163.170.32 => 103.163.170.32 190.170.232.0/24 => 250.24.51.219 111.60.99.67
;;; H 250.24.51.219 124.48.79.11 => 103.163.170.32 179.111.105.159 => 179.111.105.159 143.130.31.0/24 => 8.158.16.5 30.235.90.120
;;; I 8.158.16.5 179.111.105.159 => 250.24.51.219 143.130.31.174 => 247.230.125.27 111.60.99.0/24 => 13.250.207.24 111.60.99.67
;;; J 247.230.125.27 103.163.170.32 => 30.235.90.120 111.60.99.67 => 8.158.16.5 179.111.105.0/24 => 111.60.99.67 13.250.207.24
;;; K 30.235.90.120 73.109.79.84 => 124.48.79.11 13.250.207.24 => 179.111.105.159 8.158.16.0/24 => 250.24.51.219 103.163.170.32
;;; L 222.240.122.249 192.149.202.205 => 124.48.79.11 179.111.105.159 => 30.235.90.120 212.37.231.0/24 => 212.37.231.51 192.149.202.205
;;; M 192.149.202.205 222.240.122.249 => 143.130.31.174 179.111.105.159 => 222.240.122.249 212.37.231.0/24 => 202.180.56.184 73.109.79.84
;;; N 202.180.56.184 247.230.125.27 => 190.170.232.73 192.149.202.205 => 143.130.31.174 179.111.105.0/24 => 192.149.202.205 73.109.79.84
;;; O 190.170.232.73 212.37.231.51 => 212.37.231.51 30.235.90.120 => 124.48.79.11 143.130.31.0/24 => 222.240.122.249 202.180.56.184
;;; P 212.37.231.51 179.111.105.159 => 190.170.232.73 73.109.79.84 => 222.240.122.249 103.163.170.0/24 => 124.48.79.11 73.109.79.84
;;;
;;; Enter the nodes the packet passes through below
;;; (Note: Answer must start with P, end with the destination node name, and contain only node names.)
;;;
;;; Your answer:
;;;
;;;
;;; ©2008 Google - Terms of Service - Privacy Policy - Google Home
;;; Powered by Google

;;; Here is GNU Emacs code that convers cut&paste text from the
;;; Treasure Hunt web site (like the above) into the network
;;; definition in the Lisp format for the program in this file:
;;;
;;; (query-replace-regexp "\\(.\\) \\(.+\\) \\(.+\\) => \\(.+\\) \\(.+\\) => \\(.+\\) \\(.+\\) => \\(.+\\) \\(.+\\)" "(defnode \\1
;;; (\"\\2\" \"\\3\")
;;; (\"\\4\" \"\\5\")
;;; (\"\\6\" \"\\7\")
;;; (\"0.0.0.0/0\" \"\\8\")" nil (if (and transient-mark-mode mark-active) (region-beginning)) (if (and transient-mark-mode mark-active) (region-end)))

(in-package :noc)

(defvar *addr->node* (make-hash-table :test #'eql))

(defvar *name->node* (make-hash-table :test #'eq))

(defclass node ()
((address :initarg :address :reader node-addr)
(name :initarg :name :reader node-name)
(routes :initform '() :accessor node-routes)
(tree :accessor node-tree)))

(defun add-route (node route)
(let ((prefix (first route))
(next-hop (ipv4-aton (second route))))
(let ((slashpos (position #\/ prefix)))
(if slashpos
(setq prefix (cons (ipv4-aton (subseq prefix 0 slashpos))
(parse-integer (subseq prefix (1+
slashpos)))))
(setq prefix (cons (ipv4-aton prefix) 32))))
(push (cons prefix next-hop) (node-routes node))))

(defmacro defnode (name addr &rest routes)
`(let ((new-node (make-instance 'node
:name ',name
:address (ipv4-aton ,addr))))
(dolist (route ',routes)
(add-route new-node route))
(init-routing-tree new-node)
(setf (gethash ',name *name->node*)
new-node)
(setf (gethash (ipv4-aton ,addr) *addr->node*)
new-node)
(set ',name new-node)
new-node))

(defun init-routing-tree (node)
(let ((routes (node-routes node)))
(let ((tree (make-patricia-tree '(8 8 8 8))))
(dolist (route routes)
(let ((prefix (car route))
(next-hop (cdr route)))
(patricia-tree-insert tree (car prefix) (- 32 (cdr prefix)) next-hop)))
(finish-patricia-tree tree)
(setf (node-tree node) tree))))

(defnode A "73.109.79.84"
("8.158.16.5" "143.130.31.174")
("30.235.90.120" "202.180.56.184")
("111.60.99.0/24" "192.149.202.205")
("0.0.0.0/0" "212.37.231.51"))
(defnode B "143.130.31.174"
("8.158.16.5" "124.48.79.11")
("30.235.90.120" "192.149.202.205")
("222.240.122.0/24" "202.180.56.184")
("0.0.0.0/0" "73.109.79.84"))
(defnode C "124.48.79.11"
("212.37.231.51" "212.37.231.51")
("111.60.99.67" "143.130.31.174")
("192.149.202.0/24" "103.163.170.32")
("0.0.0.0/0" "190.170.232.73"))
(defnode D "103.163.170.32"
("179.111.105.159" "13.250.207.24")
("30.235.90.120" "124.48.79.11")
("143.130.31.0/24" "179.111.105.159")
("0.0.0.0/0" "222.240.122.249"))
(defnode E "13.250.207.24"
("111.60.99.67" "247.230.125.27")
("222.240.122.249" "103.163.170.32")
("8.158.16.0/24" "111.60.99.67")
("0.0.0.0/0" "8.158.16.5"))
(defnode F "111.60.99.67"
("124.48.79.11" "8.158.16.5")
("192.149.202.205" "179.111.105.159")
("212.37.231.0/24" "247.230.125.27")
("0.0.0.0/0" "13.250.207.24"))
(defnode G "179.111.105.159"
("111.60.99.67" "30.235.90.120")
("103.163.170.32" "103.163.170.32")
("190.170.232.0/24" "250.24.51.219")
("0.0.0.0/0" "111.60.99.67"))
(defnode H "250.24.51.219"
("124.48.79.11" "103.163.170.32")
("179.111.105.159" "179.111.105.159")
("143.130.31.0/24" "8.158.16.5")
("0.0.0.0/0" "30.235.90.120"))
(defnode I "8.158.16.5"
("179.111.105.159" "250.24.51.219")
("143.130.31.174" "247.230.125.27")
("111.60.99.0/24" "13.250.207.24")
("0.0.0.0/0" "111.60.99.67"))
(defnode J "247.230.125.27"
("103.163.170.32" "30.235.90.120")
("111.60.99.67" "8.158.16.5")
("179.111.105.0/24" "111.60.99.67")
("0.0.0.0/0" "13.250.207.24"))
(defnode K "30.235.90.120"
("73.109.79.84" "124.48.79.11")
("13.250.207.24" "179.111.105.159")
("8.158.16.0/24" "250.24.51.219")
("0.0.0.0/0" "103.163.170.32"))
(defnode L "222.240.122.249"
("192.149.202.205" "124.48.79.11")
("179.111.105.159" "30.235.90.120")
("212.37.231.0/24" "212.37.231.51")
("0.0.0.0/0" "192.149.202.205"))
(defnode M "192.149.202.205"
("222.240.122.249" "143.130.31.174")
("179.111.105.159" "222.240.122.249")
("212.37.231.0/24" "202.180.56.184")
("0.0.0.0/0" "73.109.79.84"))
(defnode N "202.180.56.184"
("247.230.125.27" "190.170.232.73")
("192.149.202.205" "143.130.31.174")
("179.111.105.0/24" "192.149.202.205")
("0.0.0.0/0" "73.109.79.84"))
(defnode O "190.170.232.73"
("212.37.231.51" "212.37.231.51")
("30.235.90.120" "124.48.79.11")
("143.130.31.0/24" "222.240.122.249")
("0.0.0.0/0" "202.180.56.184"))
(defnode P "212.37.231.51"
("179.111.105.159" "190.170.232.73")
("73.109.79.84" "222.240.122.249")
("103.163.170.0/24" "124.48.79.11")
("0.0.0.0/0" "73.109.79.84"))

(defun print-path (node dest-addr)
(format t "~S" (node-name node))
(if (equal (node-addr node) dest-addr)
(format t "~%")
(let ((next-hop (patricia-tree-lookup (node-tree node) dest-addr)))
(print-path (gethash next-hop *addr->node*) dest-addr))))

;;; noc(57): (print-path P (ipv4-aton "179.111.105.159"))
;;; PONMLKDEIHG
;;; nil

Google Treasure Hunt 2008: Puzzle 2 (zip) solution

Many have published one-liners for this. Just shows you how dense I am. Also, I was confused about the fact that the whole pathname, rather than just the filename (sans directory) should be matched. Whatever.


#!/usr/bin/perl -w

## Unzip the archive, then process the resulting files to obtain a
## numeric result. You'll be taking the sum of lines from files
## matching a certain description, and multiplying those sums together
## to obtain a final result. Note that files have many different
## extensions, like '.pdf' and '.js', but all are plain text files
## containing a small number of lines of text.
##
## Sum of line 5 for all files with path or name containing bar and ending in .pdf
## Sum of line 5 for all files with path or name containing def and ending in .rtf
## Hint: If the requested line does not exist, do not increment the sum.
##
## Multiply all the above sums together and enter the product below.
## (Note: Answer must be an exact, decimal representation of the number.)

use strict;

sub sumup_lines_n_from_files ($$);

my $dir = 'GoogleTreasureHunt08_8189817998309559603';

my $result = sumup_lines_n_from_files (1, '.*EFG.*\.js$')
* sumup_lines_n_from_files (4, '.*def.*\.js$');

print $result,"\n";
1;

sub sumup_lines_n_from_files ($$) {
my ($lineno, $re) = @_;
my $sum = 0;
open (FILES, "find $dir -print |")
or die "Cannot start find: $!";
while () {
chomp;
next unless /$re/x;
#warn "FOUND FILE: $_";
next unless -r $_;
open (FILE, $_) or die "open $_: $!";
my $l = 1;
while () {
chomp;
if ($l++ == $lineno) {
warn "line $lineno: $_";
$sum += $_;
}
}
close FILE or die "close $_: $!";
}
close FILES
or die "find $dir -name '$result': $!";
return $sum;
}

Google Treasure Hunt 2008: Puzzle 1 (robot) solution

Google Treasure Hunt is a sequence of (four?) nice puzzles, three of which have been published so far. Since everybody blogs how they solved them, here are my solutions (so far).


;;; "Robot" puzzle
;;;
;;; Author: Simon Leinen
;;; Date created: 18-May-2008
;;;
;;; There's an NxM (N cases wide and M cases high) grid with the robot
;;; in the upper left corner and a treasure in the lower right. The
;;; robot can only go RIGHT or DOWN. How many possible distinct paths
;;; are there for the robot to reach the treasure?
;;;
;;; Solution:
;;;
;;; If the grid is 1xM or Nx1, there is only one possibility. This is
;;; our stop condition: Npaths(1,M) = 1, Npaths(N,1) = 1.
;;;
;;; Otherwise, M>1 and N>1. So the robot can go right and take one of
;;; Npaths(N-1,M) paths to the destination, or go down and take one of
;;; Npaths(N,M-1) paths.
;;;
;;; It is trivial to write a recursive function according to this
;;; definition, but the function will be very inefficient, because it
;;; generates an exponential explosion of recursive calls - most
;;; invocations will generate two new invocations -> chain reaction.
;;;
;;; This is the same as a certain definition of the Fibonacci series
;;; (which I personally don't find that natural), and a standard way
;;; to solve this is through "memoization", i.e. remembering the
;;; results for all calls that have terminated. There are many
;;; standard libraries for this, but I don't know where to find one
;;; and how to use it, so I'll roll my own.
;;;
;;; Thankfully, Lisp has "bignums", so we don't have to worry too much
;;; about how large the result may get.
;;;
;;; I could have improved efficiency somewhat by ordering width and
;;; height, but the code is Good Enough as is.

(in-package :cl-user)

(defvar +memo-npaths+
(make-hash-table :test #'equal))

(defmacro with-memoization ((&rest arglist) memo-form form)
(let ((result-var (gensym "result"))
(memo-var (gensym "memo")))
`(let* ((,memo-var ,memo-form)
(,result-var (gethash (list ,@arglist) ,memo-var)))
(or ,result-var
(setf (gethash (list ,@arglist) ,memo-var)
,form)))))

(defun npaths (width height)
(with-memoization (width height)
+memo-npaths+
(npaths-internal width height)))

(defun npaths-internal (width height)
(if (or (zerop width) (zerop height))
1
(+ (npaths (1- width) height)
(npaths width (1- height)))))