From the Fiber Trenches to the Clouds: May 2008

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 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)))))

From the Fiber Trenches to the Clouds

Wednesday, May 28, 2008

Google Treasure Hunt 2008: Puzzle 3 (network) solution

Google Treasure Hunt 2008: Puzzle 2 (zip) solution

Google Treasure Hunt 2008: Puzzle 1 (robot) solution

Blog Archive