aoc/2022/15_beacon.py

#!/usr/bin/env python3
import sys
import re

def ranges(sensors, y):
    intervals = set()

    def pop_overlapping(a, b):
        for other in intervals:
            c, d = other
            if a <= d and c <= b:
                intervals.remove(other)
                return min(a, c), max(b, d)

    for sx, sy, bx, by in sensors:
        dist = abs(sx - bx) + abs(sy - by) - abs(sy - y)
        if dist >= 0:
            interval = sx - dist, sx + dist
            new = pop_overlapping(*interval)
            while new:
                interval = new
                new = pop_overlapping(*interval)
            intervals.add(interval)

    return intervals

def coverage(sensors, y):
    covered = sum(r - l + 1 for l, r in ranges(sensors, y))
    beacons = len(set(bx for _, _, bx, by in sensors if by == y))
    return covered - beacons

def frequency(sensors, ymax):
    for y in range(ymax + 1):
        r = ranges(sensors, y)
        if len(r) == 2:
            (a, _), (b, _) = r
            return (max(a, b) - 1) * 4000000 + y

sensors = [tuple(map(int, re.findall(r'-?\d+', line))) for line in sys.stdin]
print(coverage(sensors, 2000000))
print(frequency(sensors, 4000000))