beacon exclusion zone

approach

each sensor covers a diamond whose radius is the manhattan distance to its beacon. rather than marking cells, generate_intervals turns that diamond into one column interval per row it touches. every row's intervals are then sorted and merged.

part 1 adds up the lengths of the merged intervals on the target row and subtracts the beacons that sit on it. part 2 scans the rows in range looking for one whose merged intervals leave a gap of exactly one column; that cell is the only uncovered spot, and the answer is built from its row and column.

the rust and go versions are ports of the same interval approach. the rust one still asks for row 20 in part 1, so it gives the example's answer rather than the real one.

the trick

a diamond is a stack of row intervals, so coverage becomes interval merging.

def merge(intervals):
    intervals = sorted(intervals, key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1] = (merged[-1][0], max(merged[-1][1], interval[1]))
    return merged