diff options
| -rw-r--r-- | AoC2023/day20/solver.lisp | 42 |
1 files changed, 40 insertions, 2 deletions
diff --git a/AoC2023/day20/solver.lisp b/AoC2023/day20/solver.lisp index 87597cf..d57af9a 100644 --- a/AoC2023/day20/solver.lisp +++ b/AoC2023/day20/solver.lisp @@ -1,5 +1,7 @@ (ql:quickload '(fiveam str arrows)) -(use-package '(alexandria fiveam)) +(defpackage :day20 + (:use :cl :fiveam :alexandria)) +(in-package :day20) (defstruct module type state outputs) @@ -85,7 +87,43 @@ sum low into n-low finally (return (* n-high n-low)))))) +(defun common-cycle (cycles) + (apply #'lcm (mapcar #'cdr cycles))) + +(defun solver2 () + (let* ((board (prepare-board (parse-input (uiop:read-file-lines "input")))) + ;; feed is a single conjunction that gives to rx by inspecting input + ;; feed has 4 inputs, it needs them all to be on high before it outputs + ;; a low for rx + ;; The main assumption is that each one of those inputs will send a high + ;; periodically, and all will be on high on the least common multiple of + ;; their cycle. + (feed (loop for name being the hash-key of board + using (hash-value module) + when (member 'rx (slot-value module 'outputs)) + return name)) + (cycles (loop for name being the hash-key of board + using (hash-value module) + when (member feed (slot-value module 'outputs)) + collect (cons name 0))) + (presses 1) + (start '((button broadcaster low)))) + + (loop named outer + for signals = (propagate board start) then (propagate board (or signals start)) + when (null signals) + do (incf presses) + ;; until (< 4000 presses) + do + (loop for (from to pulse) in signals do + (when (and (eq to feed) (eq pulse 'high)) + (setf (cdr (assoc from cycles)) presses)) + (when (every (compose #'positive-fixnum-p #'cdr) cycles) + (return-from outer (common-cycle cycles))))))) + + (test solutions (is (= 32000000 (solver1 (uiop:read-file-lines "eg-i1")))) (is (= 11687500 (solver1 (uiop:read-file-lines "eg-i2")))) - (is (= 791120136 (solver1 (uiop:read-file-lines "input"))))) + (is (= 791120136 (solver1 (uiop:read-file-lines "input")))) + (is (= 215252378794009 (solver2)))) |