AoC2023/day08/solver.lisp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

(ql:quickload '(fiveam str arrows))

(defparameter eg-input "LLR

AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)")

(defun parse-input (lines)
  (let ((graph (make-hash-table :test #'equal)))
    (destructuring-bind (instructions blank . nodes) lines
      (declare (ignorable blank))
      (dolist (line nodes)
        (destructuring-bind (node . leaves)
            (remove-if #'str:emptyp
                       (cl-ppcre:split "[=,() ]" line))
          (setf (gethash node graph) leaves)))
      (values instructions graph))))

(defun traverse (instructions graph location terminatep)
  (loop
    for i from 0
    do (arrows:-<>
        (ecase (aref instructions (mod i (length instructions)))
          (#\L #'first)
          (#\R #'second))
        (funcall <> (gethash location graph))
        (setf location <>))
    count i until (funcall terminatep location)))

(defun solver1 (lines)
  (multiple-value-bind (instructions graph)
      (parse-input lines)
    (traverse instructions graph "AAA" (lambda (p) (equal "ZZZ" p)))))

(defparameter eg-input2 "LR

11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)")

(defun solver2 (lines)
  (multiple-value-bind (instructions graph)
      (parse-input lines)
    (arrows:->>
     (remove-if-not (lambda (s) (str:ends-with-p "A" s))
                    (alexandria:hash-table-keys graph))
     (mapcar (lambda (start)
               (traverse instructions graph start (lambda (p) (str:ends-with-p "Z" p)))))
     (apply #'lcm))))

(fiveam:test solutions
  (fiveam:is (= 6 (solver1 (uiop:split-string eg-input :separator '(#\Newline)))))
  (fiveam:is (= 6 (solver2 (uiop:split-string eg-input2 :separator '(#\Newline)))))
  (fiveam:is (= 19199 (solver1 (uiop:read-file-lines "input"))))
  (fiveam:is (= 13663968099527(solver2 (uiop:read-file-lines "input")))))