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

3 comments:

Anonymous said...

WHY NOT "P L K G" ?

Simon Leinen said...

> WHY NOT "P L K G" ?

That would be a better path, but you have to use the forwarding table at each hop. Like on the Internet, forwarding is hop-by-hop and may not always result in the optimal path. There could even be loops.

Anonymous said...

Hello Mr Simon,

Mathematically I found exactly 2456 solutions (paths) for your problem. Most optimal is “PONMLKHG” according to the algorithm of DJIKSTRA. I see that I am far from your solution “PONMLKDEIGH”. Can you explain me the technical side of the question in very simple terms. I am a mathematician and the networks are not my field.

I thank you for answering me.