15

1 files changed, 59 insertions, 0 deletions

diff --git a/15.py b/15.py
new file mode 100644
index 0000000..f0f8904
--- /dev/null
+++ b/15.py
@@ -0,0 +1,59 @@
+from utils import open_day, Point2D, norm_1, inbounds
+import re
+
+regex = re.compile(r'^Sensor at x=(-?[0-9]+), y=(-?[0-9]+): closest beacon is at x=(-?[0-9]+), y=(-?[0-9]+)$')
+sensors = []
+with open_day(15) as f:
+    for line in f:
+        m = regex.match(line)
+        assert(m)
+        sx, sy, bx, by = map(int, m.group(1, 2, 3, 4))
+        sensors.append((Point2D(sx, sy), Point2D(bx, by)))
+
+def overlaps_at_y(sensors, y=2000000):
+    beacons = sum(1 for b in set(b for _, b in sensors) if b.y == y)
+    sensors = [s for s in ((s[0], norm_1(s[1] - s[0])) for s in sensors) if abs(s[0].y - y) <= s[1]]
+    ranges = []
+    for sensor, rang in sensors:
+        dx = rang - abs(sensor.y - y)
+        ranges.append((sensor.x - dx, sensor.x + dx))
+    ranges.sort()
+    count = 0
+    cstart, cend = ranges.pop(0)
+    for start, end in ranges:
+        if start <= cend:
+            cend = max(cend, end)
+            continue
+        count += cend - cstart + 1
+        cstart, cend = start, end
+    return count + cend - cstart + 1 - beacons
+
+print(overlaps_at_y(sensors))
+
+def edgepoints(sensors):
+    for sp, bp in sensors:
+        dist = norm_1(bp - sp) + 1
+        for x in range(sp.x - dist, sp.x + dist + 1):
+            dy = dist - abs(x - sp.x)
+            yield Point2D(x, sp.y+dy)
+            if dy != 0: yield Point2D(x, sp.y-dy)
+
+def dedup(it):
+    seen = set()
+    for v in it:
+        if v in seen: continue
+        seen.add(v)
+        yield v
+
+def findbeacon(sensors, max_dim=4000000):
+    for p in dedup(edgepoints(sensors)):
+        if not inbounds(p, Point2D(max_dim + 1, max_dim + 1)): continue
+        for sp, bp in sensors:
+            dist = norm_1(bp - sp)
+            if norm_1(p - sp) <= dist: break
+        else:
+            return p
+
+def tuning_freq(p):
+    return p.x * 4000000 + p.y
+print(tuning_freq(findbeacon(sensors)))