aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2022
diff options
context:
space:
mode:
authorOscar Najera <hi@oscarnajera.com>2022-12-17 14:13:47 +0100
committerOscar Najera <hi@oscarnajera.com>2022-12-17 14:13:47 +0100
commitba0be37eb3716228bbdbc3158146ceeeb9c389a9 (patch)
tree84c48264f7715579b316238545c0ba27cbd93b8f /AoC2022
parent3241a9f65f227f8bcbe53409b9138baa238fcace (diff)
downloadscratch-ba0be37eb3716228bbdbc3158146ceeeb9c389a9.tar.gz
scratch-ba0be37eb3716228bbdbc3158146ceeeb9c389a9.tar.bz2
scratch-ba0be37eb3716228bbdbc3158146ceeeb9c389a9.zip
search fail
Diffstat (limited to 'AoC2022')
-rw-r--r--AoC2022/15/solver.lisp71
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)