Tuesday, June 03, 2008

Google Treasure Hunt 2008: Puzzle 4 (primes) solution

This is another one that lends itself to a nice solution in Common Lisp. It helps not to be too worried about efficiency in the beginning - "early optimization is the root of all evil". So I don't use Erastosthenes' sieve to enumerate primes, I just iterate over natural numbers (2, 3, k+2) and check for primality using a trivial PRIMEP. For each cardinality (number of consecutive primes that should be summed up), I maintain a vector of exactly that size, to be used as a ring buffer. Each time I get a complete sum-of-primes which is itself a prime, I note that this sum-prime can be represented as a consecutive-primes-sum of the given cardinality. When a number has as many entries as we have cardinalities, we have won.

;;; Question:
;;; Find the smallest number that can be expressed as
;;; the sum of 23 consecutive prime numbers,
;;; the sum of 33 consecutive prime numbers,
;;; the sum of 403 consecutive prime numbers,
;;; the sum of 1163 consecutive prime numbers,
;;; and is itself a prime number.
;;; For example, 41 is the smallest prime number that can be expressed as
;;; the sum of 3 consecutive primes (11 + 13 + 17 = 41) and
;;; the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).
;;; Your answer: ____________
(in-package :noc)

(defun primep (n)
(let ((sq (truncate (sqrt n))))
(do ((k 2 (1+ k)))
((> k sq) t)
(when (zerop (rem n k))
(return nil)))))

(defun map-primes (fun)
(map-primes-1 fun 2))

(defun map-primes-1 (fun k)
(when (primep k)
(funcall fun k))
(map-primes-1 fun (if (= k 2) 3 (+ k 2))))

(defun make-vector-adder (size sum-fun)
(let ((vec (make-array (list size)))
(count 0)
(fullp nil)
(sum 0))
(let ((fun #'(lambda (k)
(when fullp
(decf sum (aref vec count)))
(setf (aref vec count) k)
(incf sum k)
(incf count)
(when (= count size)
(setq count 0)
(setq fullp t))
(when (and fullp (primep sum))
(when (= sum 5457701)
(format t "Sum of ~D consecutive primes:~% " size)
(dotimes (k size)
(format t " ~D" (aref vec (rem (+ k count) size))))
(funcall sum-fun sum)))))

(defun solve (cardinalities)
(let ((prime-to-card (make-hash-table :test #'equal)))
(let ((adders
(mapcar #'(lambda (k)
#'(lambda (sum)
(let ((cards
(cons k (gethash sum prime-to-card '()))))
(when (= (length cards) (length cardinalities))
(return-from solve sum))
(setf (gethash sum prime-to-card) cards)))))
(let ((iterator #'(lambda (k)
(dolist (adder adders) (funcall adder k)))))
(map-primes iterator)))))

;;; noc(38): (time (solve '(23 33 403 1163)))
;;; ; cpu time (non-gc) 2,480 msec user, 0 msec system
;;; ; cpu time (gc) 80 msec user, 0 msec system
;;; ; cpu time (total) 2,560 msec user, 0 msec system
;;; ; real time 2,747 msec
;;; ; space allocation:
;;; ; 10,128 cons cells, 13,369,008 other bytes, 0 static bytes
;;; 5457701

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 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 => => =>
;;; B => => =>
;;; C => => =>
;;; D => => =>
;;; E => => =>
;;; F => => =>
;;; G => => =>
;;; H => => =>
;;; I => => =>
;;; J => => =>
;;; K => => =>
;;; L => => =>
;;; M => => =>
;;; N => => =>
;;; O => => =>
;;; P => => =>
;;; 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\")
;;; (\"\" \"\\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+
(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*)
(setf (gethash (ipv4-aton ,addr) *addr->node*)
(set ',name 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 ""
("" "")
("" "")
("" "")
("" ""))
(defnode B ""
("" "")
("" "")
("" "")
("" ""))
(defnode C ""
("" "")
("" "")
("" "")
("" ""))
(defnode D ""
("" "")
("" "")
("" "")
("" ""))
(defnode E ""
("" "")
("" "")
("" "")
("" ""))
(defnode F ""
("" "")
("" "")
("" "")
("" ""))
(defnode G ""
("" "")
("" "")
("" "")
("" ""))
(defnode H ""
("" "")
("" "")
("" "")
("" ""))
(defnode I ""
("" "")
("" "")
("" "")
("" ""))
(defnode J ""
("" "")
("" "")
("" "")
("" ""))
(defnode K ""
("" "")
("" "")
("" "")
("" ""))
(defnode L ""
("" "")
("" "")
("" "")
("" ""))
(defnode M ""
("" "")
("" "")
("" "")
("" ""))
(defnode N ""
("" "")
("" "")
("" "")
("" ""))
(defnode O ""
("" "")
("" "")
("" "")
("" ""))
(defnode P ""
("" "")
("" "")
("" "")
("" ""))

(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 ""))
;;; 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";

sub sumup_lines_n_from_files ($$) {
my ($lineno, $re) = @_;
my $sum = 0;
open (FILES, "find $dir -print |")
or die "Cannot start find: $!";
while () {
next unless /$re/x;
#warn "FOUND FILE: $_";
next unless -r $_;
open (FILE, $_) or die "open $_: $!";
my $l = 1;
while () {
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)

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

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

Thursday, March 27, 2008

Rant on DNS and TCP (SwiNOG post reprint)

[Since the "routine" thing didn't work, I'm trying something different... so here's a "reprint" of a missive I just sent to the SwiNOG mailing list - the original article is archived here if you want to look at the context.]

Claudio Jeker writes:
Until recently only AXFR was using tcp,

If you look at the original DNS specs, i.e. RFC 1035, RFC 1123, etc, you will find that the protocol always specified that any DNS queries can be performed over TCP. In particular, this is the normal fallback method when a query over UDP results in a truncated (TC) response.

Actually, in the olden days there were even resolver implementations that *only* supported TCP for DNS queries, cf. this namedroppers post from 1995. (I'm not saying this was a good idea :-)

Then people stopped listening to Jon Postel's (may he rest in peace) advice to "be liberal in what you expect, conservative in what you send". Instead, concerns of "security" and short-term optimization and punishing people with "stupid" (= unexpected) configurations became more important. So IT people and their consultants and ISPs started to block DNS over TCP in many places, often leaving it open only for zone transfers, and felt good about it. Thus the new (you call it old, maybe I'm just an old fart) "rule" was born:

normaly resolver queries had to be udp.

Some people tried to evolve the DNS to carry other information, such as IPv6 addresses, digital signatures (actually meta-information to make DNS information more trustable), mail policy information. And some zones (such as the root) wanted to have many nameservers for robustness.

So suddenly, the 512 byte (yes, 512 bytes!) limit became a real issue, as fallback to TCP would very often just Not Work.

This rule was a bit relaxed because of the increased space needed for IPv6 but many authorative dns servers will only listen to UDP port 53 requests..

I would say, the "new rule" ("if you use TCP for DNS queries other than AXFRs, then you are stupid/up to no good, so I will block you") proved to harm the long-term evolution of the DNS protocol - as is quite often the case with these kinds of "security best practices" that violate transparency and other design principles. But since such rules are/were "best practices", you can never really get rid of them.

So what happened instead is that the DNS protocol was extended to support larger-than-512-byte queries over UDP (EDNS0, RFC 2671). While "dig" doesn't use EDNS0 by default (but see the example below), modern recursive nameservers should normally make use of this, so that fallback to TCP isn't necessary that often.

The fact that EDNS0 was added to the DNS is probably a good thing. But I think it would also be good if DNS over TCP generally worked. Although TCP does have higher overhead than UDP for typical DNS usage, it has some security advantage, e.g. it is much harder to spoof requests.

So to me this is another example of short-sighted and badly thought-out "security" thinking that has harmed progress and brought dubious security improvements at best.

Note that some people consider EDNS0 a security risk, because it facilitates "reflection" attacks with UDP DNS requests from spoofed (victim) source addresses that result in very large responses to be sent to the victim.

$ dig @www.multipop.ch. +edns=0 ptr -x

; <<>> DiG 9.5.0a6 <<>> @www.multipop.ch. +edns=0 ptr -x
; (1 server found)
;; global options: printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 895
;; flags: qr aa rd ra; QUERY: 1, ANSWER: 30, AUTHORITY: 1, ADDITIONAL: 2

; EDNS: version: 0, flags:; udp: 4096

;; ANSWER SECTION: 38400 IN PTR mailhost.spacebbs.ch. 38400 IN PTR mailhost.amigaland.ch. 38400 IN PTR mailhost.augsauger.ch. 38400 IN PTR mailhost.begegnung.ch. 38400 IN PTR mailhost.satvision.ch. 38400 IN PTR mailhost.hackernews.ch.ch. 38400 IN PTR mailhost.natel-news.ch. 38400 IN PTR mailhost.satanlagen.ch. 38400 IN PTR mailhost.satantennen.ch. 38400 IN PTR mailhost.wiso-schoch.ch. 38400 IN PTR mailhost.xariffusion.ch. 38400 IN PTR mailhost.sat-receiver.ch. 38400 IN PTR mailhost.estherundpetr.ch. 38400 IN PTR mailhost.luisenstrasse.ch. 38400 IN PTR mailhost.arthurandersen.ch. 38400 IN PTR mailhost.elektronik-news.ch. 38400 IN PTR mailhost.zuerichsee-gastro.ch. 38400 IN PTR mailhost.pop.ch. 38400 IN PTR mailhost.rtv.ch. 38400 IN PTR mailhost.dsng.ch. 38400 IN PTR mailhost.aa795.ch. 38400 IN PTR mailhost.aerni.net. 38400 IN PTR mailhost.bar16.ch. 38400 IN PTR mailhost.sysop.ch. 38400 IN PTR mailhost.zingg.org. 38400 IN PTR mailhost.satshop.cc. 38400 IN PTR mailhost.aquacare.ch. 38400 IN PTR mailhost.glaettli.cc. 38400 IN PTR mailhost.multipop.ch. 38400 IN PTR mailhost.satshops.ch.

;; AUTHORITY SECTION: 38400 IN NS www.multipop.ch.

www.multipop.ch. 38400 IN A

;; Query time: 119 msec
;; WHEN: Thu Mar 27 21:53:39 2008
;; MSG SIZE rcvd: 1088

Sunday, January 27, 2008

First Routine Post

For some reason I looked at my blog, and I noticed that my last post is from exactly one year ago. Although I'm not superstitious, this rings an alarm bell. So I tell myself I should probably start to force myself to post more regularly to get into some kind of routine. (By the way it's hard for me to type "routine" - for some reason, my fingers always want to write "routing".)

While I have many bloggable subjects in my mind, I don't really have the time to be creative right now, so my first routine blog post is just a "best of the week" list of things I encountered on the Internets, mostly pointed to from other blogs.

Head Tracking for Desktop VR Displays using the WiiRemote

Wonderful demo video on Youtube: A new technique for highly immersive graphics, which is both low-tech and high-tech. By Johnny Lee from CMU.

Steve Blank's Secret History of Silicon Valley

Absolutely fascinating presentation about the origins of today's Silicon Valley in the military-industrial complex of WWII and the cold war. Found on Marc Andreessen's wonderful blog.

There's obviously more but I have to move now.