search fail

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)