fast enough

2 files changed, 99 insertions, 0 deletions

diff --git a/2022/15/input b/2022/15/input
new file mode 100644
index 0000000..1999197
--- /dev/null
+++ b/2022/15/input
@@ -0,0 +1,34 @@
+Sensor at x=3842919, y=126080: closest beacon is at x=3943893, y=1918172
+Sensor at x=406527, y=2094318: closest beacon is at x=-1066, y=1333278
+Sensor at x=2208821, y=3683408: closest beacon is at x=2914373, y=3062268
+Sensor at x=39441, y=1251806: closest beacon is at x=-1066, y=1333278
+Sensor at x=3093352, y=2404566: closest beacon is at x=2810772, y=2699609
+Sensor at x=3645473, y=2234498: closest beacon is at x=3943893, y=1918172
+Sensor at x=3645012, y=2995540: closest beacon is at x=4001806, y=2787325
+Sensor at x=18039, y=3083937: closest beacon is at x=103421, y=3007511
+Sensor at x=2375680, y=551123: closest beacon is at x=2761373, y=2000000
+Sensor at x=776553, y=123250: closest beacon is at x=-1066, y=1333278
+Sensor at x=2884996, y=2022644: closest beacon is at x=2761373, y=2000000
+Sensor at x=1886537, y=2659379: closest beacon is at x=2810772, y=2699609
+Sensor at x=3980015, y=3987237: closest beacon is at x=3844688, y=3570059
+Sensor at x=3426483, y=3353349: closest beacon is at x=3844688, y=3570059
+Sensor at x=999596, y=1165648: closest beacon is at x=-1066, y=1333278
+Sensor at x=2518209, y=2287271: closest beacon is at x=2761373, y=2000000
+Sensor at x=3982110, y=3262128: closest beacon is at x=3844688, y=3570059
+Sensor at x=3412896, y=3999288: closest beacon is at x=3844688, y=3570059
+Sensor at x=2716180, y=2798731: closest beacon is at x=2810772, y=2699609
+Sensor at x=3575486, y=1273265: closest beacon is at x=3943893, y=1918172
+Sensor at x=7606, y=2926795: closest beacon is at x=103421, y=3007511
+Sensor at x=2719370, y=2062251: closest beacon is at x=2761373, y=2000000
+Sensor at x=1603268, y=1771299: closest beacon is at x=2761373, y=2000000
+Sensor at x=3999678, y=1864727: closest beacon is at x=3943893, y=1918172
+Sensor at x=3157947, y=2833781: closest beacon is at x=2914373, y=3062268
+Sensor at x=3904662, y=2601010: closest beacon is at x=4001806, y=2787325
+Sensor at x=3846359, y=1608423: closest beacon is at x=3943893, y=1918172
+Sensor at x=2831842, y=3562642: closest beacon is at x=2914373, y=3062268
+Sensor at x=3157592, y=1874755: closest beacon is at x=2761373, y=2000000
+Sensor at x=934300, y=2824967: closest beacon is at x=103421, y=3007511
+Sensor at x=3986911, y=1907590: closest beacon is at x=3943893, y=1918172
+Sensor at x=200888, y=3579976: closest beacon is at x=103421, y=3007511
+Sensor at x=967209, y=3837958: closest beacon is at x=103421, y=3007511
+Sensor at x=3998480, y=1972726: closest beacon is at x=3943893, y=1918172
diff --git a/2022/15/solve.py b/2022/15/solve.py
new file mode 100644
index 0000000..1482248
--- /dev/null
+++ b/2022/15/solve.py
@@ -0,0 +1,65 @@
+import re
+import os
+import concurrent.futures
+
+data = [
+    [int(s) for s in re.findall(r"-?\d+", dat)]
+    for dat in open("input").readlines()
+    if dat != ""
+]
+
+dists = [
+    abs(sensor_x - beacon_x) + abs(sensor_y - beacon_y)
+    for sensor_x, sensor_y, beacon_x, beacon_y in data
+]
+
+P1 = 2000000
+P2 = 4000000
+
+
+def part1():
+    noped = set()
+    already = set()
+    for i, (sensor_x, sensor_y, beacon_x, beacon_y) in enumerate(data):
+        dist = dists[i] - abs(sensor_y - P1)
+        if beacon_y == P1:
+            already.add(beacon_x)
+        if dist >= 0:
+            noped.add(range(sensor_x - dist, sensor_x + dist + 1))
+    return len(set.union(*[set(x) for x in noped]) - already)
+
+
+def valid(x, y):
+    for i, (sensor_x, sensor_y, _, _) in enumerate(data):
+        dist = abs(sensor_x - x) + abs(sensor_y - y)
+        if dist < dists[i]:
+            return False
+    return True
+
+
+def aah(i):
+    sensor_x, sensor_y, _, _ = data[i]
+    for mult_x, mult_y in (-1, 1), (-1, 1):
+        for dist_x in range(dists[i] + 2):
+            x = sensor_x + dist_x * mult_x
+            dist_y = dists[i] + 1 - dist_x
+            y = sensor_y + dist_y * mult_y
+            if x in range(0, P2 + 1) and y in range(0, P2 + 1) and valid(x, y):
+                res = x * P2 + y
+                return res
+    return False
+
+
+def part2():
+    executor = concurrent.futures.ProcessPoolExecutor(10)
+    futures = [executor.submit(aah, i) for i in range(len(data))]
+    for f in concurrent.futures.as_completed(futures):
+        res = f.result()
+        if res:
+            return res
+    return 0
+
+
+print(f"Part 1: {part1()}")
+print(f"Part 2: {part2()}")
+os.kill(os.getpid(), 9)  # nice way to kill workers