aoc2020 day13

aoc2020-day13.lisp

;;;; +----------------------------------------------------------------+
;;;; | Advent of Code 2020                                            |
;;;; +----------------------------------------------------------------+

(defpackage #:snippets/aoc2020/day13
  (:use #:cl)
  (:import-from
   #:split-sequence
   #:split-sequence)
  (:import-from
   #:snippets/egcd
   #:chinese)
  (:export
   #:day13))

(in-package #:snippets/aoc2020/day13)

(defun parse (input)
  (values (parse-integer (first input))
          (mapcar (lambda (string)
                    (parse-integer string :junk-allowed t))
                  (split-sequence #\, (second input)))))

(defun product (sequence)
  (reduce #'* sequence))

(defun in-service (buses)
  (remove-if-not #'numberp buses))

(defun time-to-wait (bus arrival)
  (- (nth-value 1 (ceiling arrival bus))))

(defun earlier (best bus arrival)
  (let ((w (time-to-wait bus arrival)))
    (if (or (null best)
            (< w (second best)))
        (list bus w)
        best)))

(defun earliest (buses arrival)
  (reduce (lambda (best bus)
            (earlier best bus arrival))
          (in-service buses)
          :initial-value nil))

(defun contest (buses)
  (chinese (in-service buses)
           (loop for bus in buses
                 for i downfrom 0
                 when bus
                 collect i)))

(defun day13 (input)
  (multiple-value-bind (arrival buses)
      (parse input)
    (list (product (earliest buses arrival))
          (contest buses))))

egcd.lisp

(defpackage #:snippets/egcd
  (:use #:cl)
  (:export
   #:egcd
   #:chinese))

(in-package #:snippets/egcd)

;; Following TAOCP chapter 1

(defun egcd (m n)
  "Extended gcd.  Returns d, a, and b such that am+bn=d."
  (let ((ap 1) (b 1)
        (a 0) (bp 0)
        (c m) (d n))
    (loop
     (multiple-value-bind (q r) (floor c d)
       (if (zerop r)
           (return-from egcd (values d a b))
           (psetf c d
                  d r
                  ap a
                  a (- ap (* q a))
                  bp b
                  b (- bp (* q b))))))))

;; Algorithm from
;; https://www.omnicalculator.com/math/chinese-remainder

(defun chinese (ns as)
  "Return a number that satisfies each of the congruences defined by
coprime moduli ns and remainders as."
  (let* ((N (reduce #'* ns))
         (ms (mapcar (lambda (x) (/ N x)) ns))
         (vs (mapcar (lambda (n m)
                       (multiple-value-bind (d u v)
                           (egcd n m)
                         (declare (ignore u))
                         (assert (= d 1))
                         v))
                     ns
                     ms))
         (es (mapcar #'* vs ms)))
    (mod (reduce #'+ (mapcar #'* es as)) N)))