diff options
| -rw-r--r-- | AoC2022/15/solver.lisp | 71 |
1 files changed, 49 insertions, 22 deletions
diff --git a/AoC2022/15/solver.lisp b/AoC2022/15/solver.lisp index 584141f..9a93e1f 100644 --- a/AoC2022/15/solver.lisp +++ b/AoC2022/15/solver.lisp @@ -75,33 +75,60 @@ (destructuring-bind ((xmin xmax) (ymin ymax)) bounds (let ((stride (- xmax xmin -1))) - ;; (princ (draw-grid grid stride)) + (princ (draw-grid grid stride)) (loop repeat stride for l from (* (+ 10 ymin) stride) when (= 3 (aref grid l)) count it)))) +(defun count-cover (markers target-row) + (let ((bounds (bounds markers)) + (max-distance (loop for (sensor beacon) on markers by #'cddr + maximize (manhattan-dist sensor beacon)))) + + (destructuring-bind ((xmin xmax) ys) bounds + (declare (ignore ys)) + (let* ((stride (- (+ (* 2 max-distance) xmax 1) xmin)) + (row-min (- xmin max-distance)) + (row (make-array stride :element-type '(unsigned-byte 1) :initial-element 0))) + (loop for (sensor beacon) on markers by #'cddr + for distance = (manhattan-dist sensor beacon) + when (= target-row (cdr sensor)) + do (setf (aref row (- (car sensor) row-min)) 1) + when (= target-row (cdr beacon)) + do (setf (aref row (- (car beacon) row-min)) 1) + + sum (loop + for x from (- xmin distance) to (+ xmax distance) + when (and (<= (manhattan-dist sensor (cons x target-row)) distance) + (< -1 (- x row-min) stride) + (= 0 (aref row (- x row-min)))) + count it and do (setf (aref row (- x row-min)) 1))))))) + +(count-cover (markers (uiop:read-file-lines "eg-in")) 10) +(count-cover (markers (uiop:read-file-lines "input")) 2000000) + +;; fail coverage +(defun fail-freq (markers bound) + (loop :for y from 0 to bound + :for col = (loop :for x from 0 to bound + :when (loop :for (sensor beacon) on markers by #'cddr + :never (<= (manhattan-dist sensor (cons x y)) + (manhattan-dist sensor beacon))) + :return x) + :when col + :return (+ (* 4000000 col) y))) + +(fail-freq (markers (uiop:read-file-lines "eg-in")) 20) +(fail-freq (markers (uiop:read-file-lines "input")) 4000000) + +(let* ((markers ) + (bound 20))) + + (let* ((lines (uiop:read-file-lines "input")) (markers (markers lines)) - (bounds (bounds markers)) - (max-distance (loop for (sensor beacon) on markers by #'cddr - maximize (manhattan-dist sensor beacon)))) + (bounds (bounds markers))) + bounds) - (destructuring-bind ((xmin xmax) (ymin ymax)) bounds - (let* ((stride (- (+ (* 2 max-distance) xmax 1) xmin)) - (row-min (- xmin max-distance)) - (target-row 2000000) - (row (make-array stride :element-type '(unsigned-byte 1) :initial-element 0))) - (loop for (sensor beacon) on markers by #'cddr - for distance = (manhattan-dist sensor beacon) - when (= target-row (cdr sensor)) - do (setf (aref row (- (car sensor) row-min)) 1) - when (= target-row (cdr beacon)) - do (setf (aref row (- (car beacon) row-min)) 1) - - sum (loop - for x from (- xmin distance) to (+ xmax distance) - when (and (<= (manhattan-dist sensor (cons x target-row)) distance) - (< -1 (- x row-min) stride) - (= 0 (aref row (- x row-min)))) - count it and do (setf (aref row (- x row-min)) 1)))))) +(make-array (* 4000000 4000000) :element-type '(unsigned-byte 1) :initial-element 0) |