]> localhost Git - adventofcode2020.git/blob - day09.lisp
c1a8a590bceb11cdce10c3b9c5fd609e733cc3c9
[adventofcode2020.git] / day09.lisp
1 (asdf:load-system :adventofcode2020)
2 (in-package #:adventofcode2020)
3 (named-readtables:in-readtable :adventofcode2020)
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)