summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--15.py59
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)))