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)))