GCJ 2010: Fair Warning in Common Lisp (Qualification Round)

The maximum possible factor is determined by the GCD between the Great Events in the past. Sorry for the unclear explanation. Anyway, the way I solved this is: I first sort the sequence of ages of past events in descending order. Then I normalize them with respect to the most recent of these events, by subtracting the smallest of these ages. I take the GCD of the other (non-smallest) event ages. This GCD defines a kind of cycle. The apocalypse (or party) will happen at the next possible cycle boundary after OR AT the current time.

Thankfully, Common Lisp has a variadic GCD function and efficient bignum implementations.

(defun solve (file)
  (with-open-file (in file)
    (let ((ncases (read in)))
      (dotimes (caseno ncases)
 (solve-case in caseno)))))

(defun solve-case (in caseno)
  (let ((nevents (read in)))
    (let ((events (make-array (list nevents))))
      (dotimes (k nevents)
 (setf (aref events k)
   (read in)))
      ;; We would like these to be in canonical order, let's say decreasing
      (setq events (sort events #'>))
      (let ((solution (time-to-apocalypse events)))
 (format t "Case #~D: ~D~%" (1+ caseno) solution)))))

(defun time-to-apocalypse (events)
  (let ((reckon (aref events (1- (length events))))) ;time since last event
    (dotimes (k (length events))
      (decf (aref events k) reckon))
    (let ((gcd (apply #'gcd (coerce (subseq events 0 (1- (length events))) 'list))))
      (if (= gcd 1)
   0
 (rem (- gcd (rem reckon gcd)) gcd)))))

GCJ 2010: Snapper Chain in Common Lisp (Qualification Round)

The snapper chain is a simple binary counter modulo 2^N. The light bulb is on iff the value of the counter is all-ones. So all we have to do is check for that counter value.

(defun solve (file)
  (with-open-file (in file)
    (let ((ncases (read in)))
      (dotimes (caseno ncases)
 (solve-case caseno in)))))

(defun solve-case (caseno in)
  (let ((n (read in))
 (k (read in)))
    (let ((solution (light-on-p n k)))
      (format t "Case #~D: ~A~%" (1+ caseno) (if solution "ON" "OFF")))))

(defun light-on-p (n k)
  (let ((cycle (ash 1 n)))
    (= (rem k cycle) (1- cycle))))

Mapping IXP access links

IXPs (Internet Exchange Points) are facilities where ISPs (Internet Service Providers) meet and can set up interconnection (peering) and exchange traffic between their mutual customers directly.

There was an interesting paper at IMC'09 called "IXPs: Mapped?", which fused data from various sources to get a more complete picture of peering at IXPs.

Here is one phenomenon that I think would be worth further research:

In the original model, the IXPs is at a colocation facility, where ISPs put their equipment (routers) and connect a router port to the exchange point switch via in-house cabling. But there's another option, where the ISP doesn't put a router up at the physical IXP facility, but instead connects an existing backbone router to the IXP by means of a leased line - could be a leased wavelength, or an Ethernet-over-{MPLS,SDH} service. Looking around me, I see this happening very frequently, e.g. quite a few medium-size Swiss ISPs lease bandwidth to Amsterdam, Frankfurt or London to connect to the large IXPs there (AMS-IX, DECIX, and LINX, respectively).

It is important to understand such non-local peering, because the impact of the access links can be quite large in terms of speed-of-light delay, and some transport media - e.g. Ethernet over MPLS - might be subject to unnoticed congestion. Also, long access links might be more difficult to upgrade in a timely manner when needed.

As an illustration, here's a traceroute between the ISP I work for (SWITCH, AS559) and an ISP in Gibraltar.

$ traceroute www.broadband.gi
traceroute to www.broadband.gi (85.115.130.100), 64 hops max, 52 byte packets
1  swiws1-v4 (130.59.4.2)  2.652 ms  0.271 ms  0.259 ms
2  swics5-10ge-1-4 (130.59.15.181)  0.334 ms  0.308 ms  0.317 ms
3  swics3-10ge-1-3 (130.59.15.189)  0.412 ms  0.336 ms  0.340 ms
4  swiez2-10ge-5-2 (130.59.36.18)  0.358 ms  0.347 ms  0.356 ms
5  swils2-10ge-1-1 (130.59.36.205)  4.001 ms  3.916 ms  3.983 ms
6  swiel2-10ge-1-2 (130.59.36.70)  4.081 ms  4.036 ms  4.069 ms
7  swice3-10ge-1-3 (130.59.37.65)  4.826 ms  4.843 ms  4.879 ms
8  ge-0-1-8-1.madrid.sapphire.gi (195.69.144.163)  58.489 ms  58.552 ms  58.530 ms
9  ge0-1-0-0.jcore2.gibraltar.sapphire.gi (85.115.128.63)  75.874 ms
ge0-0-5-0.jcore2.gibraltar.sapphire.gi (85.115.128.49)  78.614 ms  78.640 ms
10  85.115.128.18 (85.115.128.18)  76.205 ms  76.101 ms  76.203 ms
11  *  C-c C-c

Can you guess in which city we interconnect?

Google Code Jam 2009 - solutions in Common Lisp

Last year I had a lot of fun with the small puzzles of Google Treasure Hunt.  This year, there was no treasure hunt, so I decided to participate in Google Code Jam.  Code Jam seems to be quite a bit more competitive, with multiple rounds where only the top N scorers pass.  So far, I have passed the qualification round and the first online round.  I will almost certainly fail to pass the next round, because there will be only 250 participants to advance (and receive a T-shirt).  My natural rank seems to be in the high triple digits or low quadruple digits.  But maybe there will be a miracle!

Someone wrote a kind of mashup that walks the Google Code Jam submission/score database, and which allows queries e.g. per programming language.  Here's the statistics for Lisp:
http://www.go-hero.net/jam/09/lang/Lisp

I registered as "insertsomethingwitty" (I have never been good with pseudonyms), and you can find my submissions here: http://www.go-hero.net/jam/09/name/insertsomethingwitty

Bribe the Prisoners

In the two rounds I participated in ("Qualifier" and 1C), I managed to submit correct solutions for all problem sets except for the very last one, namely the "large input" for "Bribe the prisoners".  I took a bad approach to that one, and was lucky to even finish the small input set before the end of the round (2h30 for three problems).

After a nice walk, I found a simpler approach.  I had to apply memoization to make it efficient, and then I was able to run the large input set in about two minutes on my netbook - the limit is eight minutes.  Here is the new code.

(defun solve (file &optional (dest t))
  (with-open-file (s file)
    (let ((nsamples (parse-integer (read-line s))))
      (dotimes (k nsamples)
 (solve-case k s dest)))))

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

(defun solve-case (caseno s dest)
  (clrhash *memo*)
  (let ((line (mapcar #'parse-integer (split-at-spaces (read-line s)))))
    (multiple-value-bind (p q)
 (values (first line) (second line))
      (let ((rel (mapcar #'parse-integer (split-at-spaces (read-line s)))))
 (assert (= (length rel) q))
 (format dest "Case #~D: ~D~%" (1+ caseno) (minbribe p rel))))))

(defun minbribe (p rel &aux entry)
  (cond ((endp rel) 0)
 ((endp (rest rel)) (1- p))
 ((setq entry (gethash (cons p rel) *memo*)) entry)
 (t (setf (gethash (cons p rel) *memo*)
      (reduce #'min (mapcar
       #'(lambda (prisoner)
    (minbribe-1 prisoner p rel))
       rel))))))

(defun minbribe-1 (prisoner p rel)
  (cond ((<= p 1) 0)
 (t (+ (- p 1)
       (multiple-value-bind (p1 rel1 p2 rel2)
    (split-cells prisoner p rel)
  (+ (minbribe p1 rel1)
     (minbribe p2 rel2)))))))

(defun split-cells (prisoner p rel)
  (do ((rel rel (rest rel))
       (seq1 '() (cons (first rel) seq1)))
      ((= (first rel) prisoner)
       (do ((rel (rest rel) (rest rel))
     (seq2 '() (cons (- (first rel) prisoner) seq2)))
    ((endp rel)
     (values (1- prisoner) (nreverse seq1) (- p prisoner) (nreverse seq2)))))))

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))
      #+VERIFY
      (when (= sum 5457701)
        (format t "Sum of ~D consecutive primes:~%  " size)
        (dotimes (k size)
   (format t " ~D" (aref vec (rem (+ k count) size))))
        (terpri))
      (funcall sum-fun sum)))))
     fun)))

(defun solve (cardinalities)
 (let ((prime-to-card (make-hash-table :test #'equal)))
   (let ((adders
   (mapcar #'(lambda (k)
        (make-vector-adder
  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)))))
    cardinalities)))
     (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