src/day10.lisp

   1 (asdf:load-system :adventofcode2020)
   2 (in-package #:adventofcode2020)
   3 (named-readtables:in-readtable fn-reader)
   4
   5 (defun joltage-distribution (ratings)
   6   (let* ((extended (append '(0) ratings (mapcar λ(+ 3 _) (last ratings)))))
   7     (loop for a in extended
   8           for b in (cdr extended)
   9           counting (= 3 (- b a)) into threes
  10           counting (= 1 (- b a)) into ones
  11           finally (return (list ones threes)))))
  12
  13 (defun partition-ratings (ratings)
  14   (let ((groups nil) (g nil))
  15     (loop for a in ratings
  16           for b in (cdr (append ratings (mapcar λ(+ 3 _) (last ratings))))
  17           do (push a g)
  18           when (= 3 (- b a))
  19           do (progn
  20                (push (nreverse g) groups)
  21                (setf g nil)))
  22     (nreverse groups)))
  23
  24 ; turns out you don't need the fancy memoized one
  25 ; (defparameter *count-deletions-table*
  26 ;   (alist-hash-table '((1 . 0) (2 . 0) (3 . 1) (4 . 3))))
  27 ; (defun count-deletions (len)
  28 ;   (let ((val (gethash len *count-deletions-table*)))
  29 ;     (if val val
  30 ;         (let ((new-val (* 2 (count-deletions (1- len)))))
  31 ;           (setf (gethash len *count-deletions-table*) new-val)
  32 ;           new-val))))
  33 (defun count-deletions (len)
  34   (case len
  35     (1 0) (2 0) (3 1) (4 3)
  36     (t (* 2 (count-deletions (1- len))))))
  37
  38 (defun count-adapter-arrangements (ratings)
  39   (reduce #'* (mapcar (compose #'1+ #'count-deletions #'length)
  40                       (partition-ratings (cons 0 ratings)))))
  41
  42 (day 10 input
  43   (let ((ratings (sort (int-list-from input) #'<)))
  44     (part1 (apply #'* (joltage-distribution ratings)))
  45     (part2 (count-adapter-arrangements ratings))))
  46
  47 (def-suite day10)
  48 (in-suite day10)
  49
  50 (defvar *simple-ratings*
  51   (sort '(16 10 15 5 1 11 7 19 6 12 4) #'<))
  52
  53 (defvar *more-ratings*
  54   (sort '(28 33 18 42 31 14 46 20 48 47
  55           24 23 49 45 19 38 39 11 1 32
  56           25 35 8 17 7 9 4 2 34 10 3) #'<))
  57
  58 (test joltage-distributions
  59   (is (equal '(7 5) (joltage-distribution *simple-ratings*)))
  60   (is (equal '(22 10) (joltage-distribution *more-ratings*))))
  61
  62 (test partition-ratings
  63   (is (equal
  64         '((1) (4 5 6 7) (10 11 12) (15 16) (19))
  65         (partition-ratings *simple-ratings*)))
  66   (is (equal
  67         '((1 2 3 4) (7 8 9 10 11) (14) (17 18 19 20) (23 24 25)
  68                     (28) (31 32 33 34 35) (38 39) (42) (45 46 47 48 49))
  69         (partition-ratings *more-ratings*))))
  70
  71 (test count-deletions
  72   (is (equal
  73         '(0 3 1 0 0)
  74         (mapcar (compose #'count-deletions #'length)
  75                 '((0 1) (4 5 6 7) (10 11 12) (15 16) (19)))))
  76   (is (equal
  77         '(6 6 0 3 1 0 6 0 0 6)
  78         (mapcar (compose #'count-deletions #'length)
  79                 '((0 1 2 3 4) (7 8 9 10 11) (14) (17 18 19 20) (23 24 25)
  80                     (28) (31 32 33 34 35) (38 39) (42) (45 46 47 48 49))))))
  81
  82 (test count-adapter-arrangements
  83   (is (equal 8 (count-adapter-arrangements *simple-ratings*)))
  84   (is (equal 19208 (count-adapter-arrangements *more-ratings*))))
  85
  86 (run! 'day10)