aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--AoC2023/day20/solver.lisp42
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))))