commit 93b38604c87e4ecd583d53887f3e73dee5e86c57
parent 4b9bec073ee5a0bcf5402cf2c1a2092cb125ddac
Author: Lukas Henkel <lh@entf.net>
Date: Thu, 15 Dec 2022 19:30:49 +0100
Day 15
Diffstat:
4 files changed, 169 insertions(+), 2 deletions(-)
diff --git a/adventofcode2022.asd b/adventofcode2022.asd
@@ -24,7 +24,8 @@
(:file "day11")
(:file "day12")
(:file "day13")
- (:file "day14")))
+ (:file "day14")
+ (:file "day15")))
(defsystem "adventofcode2022/test"
:description "My solutions to the advent of code 2022"
@@ -48,4 +49,5 @@
(:file "day11")
(:file "day12")
(:file "day13")
- (:file "day14")))
+ (:file "day14")
+ (:file "day15")))
diff --git a/input/day15.txt b/input/day15.txt
@@ -0,0 +1,27 @@
+Sensor at x=2288642, y=2282562: closest beacon is at x=1581951, y=2271709
+Sensor at x=2215505, y=2975419: closest beacon is at x=2229474, y=3709584
+Sensor at x=275497, y=3166843: closest beacon is at x=-626874, y=3143870
+Sensor at x=1189444, y=2115305: closest beacon is at x=1581951, y=2271709
+Sensor at x=172215, y=2327851: closest beacon is at x=-101830, y=2000000
+Sensor at x=3953907, y=1957660: closest beacon is at x=2882446, y=1934422
+Sensor at x=685737, y=2465261: closest beacon is at x=1581951, y=2271709
+Sensor at x=1458348, y=2739442: closest beacon is at x=1581951, y=2271709
+Sensor at x=3742876, y=2811554: closest beacon is at x=3133845, y=3162635
+Sensor at x=437819, y=638526: closest beacon is at x=-101830, y=2000000
+Sensor at x=2537979, y=1762726: closest beacon is at x=2882446, y=1934422
+Sensor at x=1368739, y=2222863: closest beacon is at x=1581951, y=2271709
+Sensor at x=2743572, y=3976937: closest beacon is at x=2229474, y=3709584
+Sensor at x=2180640, y=105414: closest beacon is at x=3011118, y=-101788
+Sensor at x=3845753, y=474814: closest beacon is at x=3011118, y=-101788
+Sensor at x=2493694, y=3828087: closest beacon is at x=2229474, y=3709584
+Sensor at x=2786014, y=3388077: closest beacon is at x=3133845, y=3162635
+Sensor at x=3593418, y=3761871: closest beacon is at x=3133845, y=3162635
+Sensor at x=856288, y=3880566: closest beacon is at x=2229474, y=3709584
+Sensor at x=1757086, y=2518373: closest beacon is at x=1581951, y=2271709
+Sensor at x=2853518, y=2939097: closest beacon is at x=3133845, y=3162635
+Sensor at x=1682023, y=1449902: closest beacon is at x=1581951, y=2271709
+Sensor at x=3360575, y=1739100: closest beacon is at x=2882446, y=1934422
+Sensor at x=2904259, y=1465606: closest beacon is at x=2882446, y=1934422
+Sensor at x=3078500, y=3564862: closest beacon is at x=3133845, y=3162635
+Sensor at x=2835288, y=1011055: closest beacon is at x=2882446, y=1934422
+Sensor at x=2998762, y=2414323: closest beacon is at x=2882446, y=1934422
diff --git a/src/day15.lisp b/src/day15.lisp
@@ -0,0 +1,110 @@
+(defpackage #:adventofcode2022/day15
+ (:use #:cl #:adventofcode2022))
+(in-package #:adventofcode2022/day15)
+
+(defun make-min-or-max-coordinate (test)
+ (let ((x)
+ (y))
+ (lambda (cmd &optional check-value)
+ (cond
+ ((eq cmd :set)
+ (when (or (null x) (funcall test (car check-value) x))
+ (setf x (car check-value)))
+ (when (or (null y) (funcall test (cadr check-value) y))
+ (setf y (cadr check-value))))
+ ((eq cmd :get)
+ (list x y))))))
+
+(defun manhattan-distance (p-1 p-2)
+ (+ (abs (- (car p-1) (car p-2)))
+ (abs (- (cadr p-1) (cadr p-2)))))
+
+(defun coord-x-y+ (coord value)
+ (list (+ (car coord) value)
+ (+ (cadr coord) value)))
+
+(defun coord-x-y- (coord value)
+ (list (- (car coord) value)
+ (- (cadr coord) value)))
+
+(defun get-sensor-distances (inputs)
+ (let ((distances (make-hash-table :test 'equal))
+ (min-pos (make-min-or-max-coordinate #'<))
+ (max-pos (make-min-or-max-coordinate #'>)))
+ (loop for input in inputs
+ for sensor = (car input)
+ for beacon = (cadr input)
+ for distance = (manhattan-distance sensor beacon)
+ do (funcall min-pos :set (coord-x-y- sensor distance))
+ do (funcall max-pos :set (coord-x-y+ sensor distance))
+ do (setf (gethash sensor distances) distance))
+ (values distances (funcall min-pos :get) (funcall max-pos :get))))
+
+(defun get-scan-ranges (sensors y)
+ (loop for sensor being the hash-key of sensors
+ for range = (gethash sensor sensors)
+ when (and (>= y (- (cadr sensor) range))
+ (<= y (+ (cadr sensor) range)))
+ collect (list (+ (- (car sensor) range)
+ (abs (- (cadr sensor) y)))
+ (- (+ (car sensor) range)
+ (abs (- (cadr sensor) y))))))
+
+(defun task1 (inputs)
+ (multiple-value-bind (distances min-pos max-pos)
+ (get-sensor-distances inputs)
+ (let* ((check-y 2000000)
+ (check-y (if (< (cadr max-pos) check-y)
+ 10 ;; Test case
+ check-y))
+ (beacons (loop with ht = (make-hash-table :test 'equal)
+ for (sensor beacon) in inputs
+ do (setf (gethash beacon ht) t)
+ finally (return ht))))
+ (loop with scan-ranges = (get-scan-ranges distances check-y)
+ for x from (car min-pos) to (car max-pos)
+ when (and (not (gethash (list x check-y) beacons))
+ (loop for range in scan-ranges
+ thereis (and (>= x (car range))
+ (<= x (cadr range)))))
+ sum 1))))
+
+(defun task2 (inputs)
+ (multiple-value-bind (distances min-pos max-pos)
+ (get-sensor-distances inputs)
+ (declare (ignore min-pos))
+ (let* ((search-area-min 0)
+ (search-area-max 4000000)
+ (search-area-max (if (< (cadr max-pos) search-area-max)
+ 20 ;; Test case
+ search-area-max)))
+ (loop named outer
+ for y from search-area-min to search-area-max
+ for scan-ranges = (get-scan-ranges distances y)
+ do (loop for range in scan-ranges
+ for left-edge = (1- (car range))
+ for right-edge = (1+ (cadr range))
+ do (loop for x in (list left-edge right-edge)
+ when (and (>= x search-area-min)
+ (<= x search-area-max))
+ unless (loop for range in scan-ranges
+ thereis (and (>= x (car range))
+ (<= x (cadr range))))
+ do (return-from outer (+ (* x 4000000) y))))))))
+
+(define-day 15
+ (:translate-input (lambda (line)
+ (let* ((parts (str:split " " line))
+ (sx (nth 2 parts))
+ (sx (subseq sx 2 (1- (length sx))))
+ (sy (nth 3 parts))
+ (sy (subseq sy 2 (1- (length sy))))
+ (bx (nth 8 parts))
+ (bx (subseq bx 2 (1- (length bx))))
+ (by (subseq (nth 9 parts) 2)))
+ (list (list (parse-integer sx)
+ (parse-integer sy))
+ (list (parse-integer bx)
+ (parse-integer by))))))
+ #'task1
+ #'task2)
diff --git a/t/day15.lisp b/t/day15.lisp
@@ -0,0 +1,28 @@
+(in-package #:adventofcode2022/test)
+
+(defconstant +testdata-day15+ "Sensor at x=2, y=18: closest beacon is at x=-2, y=15
+Sensor at x=9, y=16: closest beacon is at x=10, y=16
+Sensor at x=13, y=2: closest beacon is at x=15, y=3
+Sensor at x=12, y=14: closest beacon is at x=10, y=16
+Sensor at x=10, y=20: closest beacon is at x=10, y=16
+Sensor at x=14, y=17: closest beacon is at x=10, y=16
+Sensor at x=8, y=7: closest beacon is at x=2, y=10
+Sensor at x=2, y=0: closest beacon is at x=2, y=10
+Sensor at x=0, y=11: closest beacon is at x=2, y=10
+Sensor at x=20, y=14: closest beacon is at x=25, y=17
+Sensor at x=17, y=20: closest beacon is at x=21, y=22
+Sensor at x=16, y=7: closest beacon is at x=15, y=3
+Sensor at x=14, y=3: closest beacon is at x=15, y=3
+Sensor at x=20, y=1: closest beacon is at x=15, y=3")
+
+(def-test day15-task1 ()
+ (is-true
+ (= 26
+ (run-task 15 1
+ (make-string-input-stream +testdata-day15+)))))
+
+(def-test day15-task2 ()
+ (is-true
+ (= 56000011
+ (run-task 15 2
+ (make-string-input-stream +testdata-day15+)))))
