src/day09.lisp

   1 (asdf:load-system :adventofcode2020)
   2 (in-package #:adventofcode2020)
   3 (named-readtables:in-readtable fn-reader)
   4
   5 (defun make-preambled-list (list k i)
   6   (subseq list (- i k) (1+ i)))
   7
   8 (defun check-consistency (list)
   9   (let ((preamble (butlast list))
  10         (checksum (car (last list))))
  11     (block find-sum
  12            (dolist (i preamble)
  13              (dolist (j preamble)
  14                (unless (= i j)
  15                  (when (= (+ i j) checksum)
  16                    (return-from find-sum '(i j)))))))))
  17
  18 (defun test-preambled-lists (list preamble)
  19   (loop for i upfrom preamble below (length list)
  20         unless (check-consistency (make-preambled-list list preamble i))
  21         return (nth i list)))
  22
  23 (defun find-sum-list (list checksum)
  24   (labels ((test-bounds (i j)
  25              (let ((sum (apply #'+ (subseq list i j))))
  26                (cond ((< sum checksum) :lt)
  27                      ((= sum checksum) :eq)
  28                      ((> sum checksum) :gt))))
  29            (find-bounds (i j)
  30              (case (test-bounds i j)
  31                (:lt (find-bounds i (1+ j)))
  32                (:eq (subseq list i j))
  33                (:gt (find-bounds (1+ i) j)))))
  34     (find-bounds 0 1)))
  35
  36 (day 09 input
  37   (let ((numbers (int-list-from input)))
  38     (part1 (test-preambled-lists numbers 25))
  39     (part2 (let ((sum-list (find-sum-list numbers (test-preambled-lists numbers 25))))
  40              (+ (apply #'min sum-list)
  41                 (apply #'max sum-list))))))
  42
  43 (def-suite day09)
  44 (in-suite day09)
  45
  46 (defvar *simple-numbers*
  47   '(35 20 15 25 47 40 62 55
  48     65 95 102 117 150 182
  49     127 219 299 277 309 576))
  50
  51 (test make-preambled-lists
  52   (is (equal
  53         '(35 20 15 25 47 40)
  54         (make-preambled-list *simple-numbers* 5 5)))
  55   (is (equal
  56         '(40 62 55 65 95 102)
  57         (make-preambled-list *simple-numbers* 5 10))))
  58
  59 (test check-list-consistencies
  60   (is-true  (check-consistency '(35 20 15 25 47 40)))
  61   (is-false (check-consistency '(95 102 117 150 182 127))))
  62
  63 (test test-preambled-lists
  64   (is (equal 127 (test-preambled-lists *simple-numbers* 5))))
  65
  66 (test find-sum-lists
  67   (is (equal
  68         '(15 25 47 40)
  69         (find-sum-list *simple-numbers*
  70                        (test-preambled-lists *simple-numbers* 5)))))
  71
  72 (run! 'day09)