Sunday, May 09, 2010

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

The snapper chain is a simple binary counter modulo 2N. 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))))
Post a Comment