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)))))
That's nice solution, because I had exactly the same idea :). Unfortunately I didn't make it because it was too late for my submission.
Post a Comment