aoc-2022/15.py

from itertools import combinations

lines = [[chunk.split("=") for chunk in line.split()] for line in open("15.input")]

lines = [(int(line[2][1][:-1]), int(line[3][1][:-1]), int(line[8][1][:-1]), int(line[9][1])) for line in lines]

def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

sensors = set()
beacons = set()
ranges = {}

for sx, sy, bx, by in lines:
    sensors.add((sx, sy))
    beacons.add((bx, by))
    ranges[(sx, sy)] = dist((sx, sy), (bx, by))

def row_coverage(sensor, y):
    dy = abs(sensor[1] - y)
    if ranges[sensor] < dy:
        return None
    dx = abs(ranges[sensor] - dy)
    return (sensor[0] - dx, sensor[0] + dx + 1)

def col_coverage(sensor, x):
    dx = abs(sensor[0] - x)
    if ranges[sensor] < dx:
        return None
    dy = abs(ranges[sensor] - dx)
    return (sensor[1] - dy, sensor[1] + dy + 1)

def join_segments(a):
    b = []
    for begin,end in sorted(a):
        if b and b[-1][1] >= begin:
            b[-1] = (b[-1][0], max(b[-1][1], end))
        else:
            b.append((begin, end))

        # print((begin, end), b)
    return b

def part1(y):
    coverage = [row_coverage(sensor, y) for sensor in sensors]
    coverage = [c for c in coverage if c is not None]
    joined = join_segments(coverage)

    print("Part 1:", sum(max(0, seg[1] - seg[0] - 1) for seg in joined))



#part1(y=10)
part1(y=2000000)

def possible_positions(covered):
    result = []
    current = 0

    for start, end in covered:
        for x in range(current, start):
            result.append(x)
        if end > 4000000:
            break
        current = end

    return result

def part2(max_y):
    # Brute force let's gooooooo
    for y in range(0, max_y):
        # This takes a few minutes, so better log the progress
        if y % (max_y / 100) == 0:
            print(y / max_y * 100, "%")

        y_coverage = [row_coverage(sensor, y) for sensor in sensors]
        y_coverage = [c for c in y_coverage if c is not None]
        y_joined = join_segments(y_coverage)

        # Here we can actually be a bit smart, only check the columns
        # which are not already covered
        for x in possible_positions(y_joined):
            x_coverage = [col_coverage(sensor, x) for sensor in sensors]
            x_coverage = [c for c in x_coverage if c is not None]
            x_joined = join_segments(x_coverage)
            if y in possible_positions(x_joined):
                return (x, y)

#x, y = part2(20)
x, y = part2(4000000 )
print("Part 2:", x * 4000000 + y)