Add day 09

[adventofcode2020.git] / src / day09.lisp

diff --git a/src/day09.lisp b/src/day09.lisp
new file mode 100644 (file)
index 0000000..7d5aab8
--- /dev/null
+++ b/src/day09.lisp
@@ -0,0 +1,72 @@
+(asdf:load-system :adventofcode2020)
+(in-package #:adventofcode2020)
+(named-readtables:in-readtable fn-reader)
+
+(defun make-preambled-list (list k i)
+  (subseq list (- i k) (1+ i)))
+
+(defun check-consistency (list)
+  (let ((preamble (butlast list))
+        (checksum (car (last list))))
+    (block find-sum
+           (dolist (i preamble)
+             (dolist (j preamble)
+               (unless (= i j)
+                 (when (= (+ i j) checksum)
+                   (return-from find-sum '(i j)))))))))
+
+(defun test-preambled-lists (list preamble)
+  (loop for i upfrom preamble below (length list)
+        unless (check-consistency (make-preambled-list list preamble i))
+        return (nth i list)))
+
+(defun find-sum-list (list checksum)
+  (labels ((test-bounds (i j)
+             (let ((sum (apply #'+ (subseq list i j))))
+               (cond ((< sum checksum) :lt)
+                     ((= sum checksum) :eq)
+                     ((> sum checksum) :gt))))
+           (find-bounds (i j)
+             (case (test-bounds i j)
+               (:lt (find-bounds i (1+ j)))
+               (:eq (subseq list i j))
+               (:gt (find-bounds (1+ i) j)))))
+    (find-bounds 0 1)))
+
+(day 09 input
+  (let ((numbers (int-list-from input)))
+    (part1 (test-preambled-lists numbers 25))
+    (part2 (let ((sum-list (find-sum-list numbers (test-preambled-lists numbers 25))))
+             (+ (apply #'min sum-list)
+                (apply #'max sum-list))))))
+
+(def-suite day09)
+(in-suite day09)
+
+(defvar *simple-numbers* 
+  '(35 20 15 25 47 40 62 55
+    65 95 102 117 150 182 
+    127 219 299 277 309 576))
+
+(test make-preambled-lists
+  (is (equal
+        '(35 20 15 25 47 40)
+        (make-preambled-list *simple-numbers* 5 5)))
+  (is (equal
+        '(40 62 55 65 95 102)
+        (make-preambled-list *simple-numbers* 5 10))))
+
+(test check-list-consistencies
+  (is-true  (check-consistency '(35 20 15 25 47 40)))
+  (is-false (check-consistency '(95 102 117 150 182 127))))
+
+(test test-preambled-lists
+  (is (equal 127 (test-preambled-lists *simple-numbers* 5))))
+
+(test find-sum-lists
+  (is (equal
+        '(15 25 47 40)
+        (find-sum-list *simple-numbers* 
+                       (test-preambled-lists *simple-numbers* 5)))))
+
+(run! 'day09)