Sunday, May 23, 2010

GCJ 2010: Rope Intranet in Common Lisp (Online Round 1C)

I failed at online round 1 this year, although I tried twice in sub-rounds 1B and 1C. The first puzzle in sub-round 1C, Rope Intranet was easy, and I handed in the correct solutions for both the small and the large input in less than ten minutes. Here is the straightforward code:

(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)))
    (let ((wires (make-array (list n))))
      (dotimes (i n)
        (setf (aref wires i)
          (cons (read in) (read in))))
      (let ((sol (intersections wires)))
        (format t "Case #~D: ~D~%" (1+ caseno) sol)))))

(defun intersections (wires)
  (let ((result 0))
    (do ((i 0 (1+ i)))
        ((>= i (length wires))
      (do ((j (1+ i) (1+ j)))
          ((>= j (length wires)))
        (when (intersectsp (aref wires i) (aref wires j))
          (incf result))))))

(defun intersectsp (w1 w2)
  (if (< (car w1) (car w2))
      (> (cdr w1) (cdr w2))
    (< (cdr w1) (cdr w2))))
Post a Comment