diff options
Diffstat (limited to '15.py')
| -rw-r--r-- | 15.py | 59 |
1 files changed, 59 insertions, 0 deletions
@@ -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))) |