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