Advent of Code 2022 - Day 15 - Python

from bisect import insort
from itertools import chain
import re
from typing import Generator, Optional

Coordinate = tuple[int, int]
Beacon = Coordinate
Sensor = Coordinate
Distance = int


def parse_input(filepath) -> Generator[tuple[Sensor, Beacon], None, None]:
    with open(filepath, "r") as f:
        for line in f.readlines():
            x1, y1, x2, y2 = map(int, re.findall(r"-*\d+", line))
            yield (x1, y1), (x2, y2)


def manhattan_distance(x1, y1, x2, y2) -> Distance:
    return abs(x2 - x1) + abs(y2 - y1)


def get_range_at_row(sensor, beacon, row) -> Optional[tuple[int, int]]:
    distance = manhattan_distance(*sensor, *beacon)
    if abs(sensor[1] - row) > distance:
        return None
    else:
        delta_h = abs(distance - abs(sensor[1] - row))
        left, right = sensor[0] - delta_h, sensor[0] + delta_h
        return left, right


def merge_intervals(ranges: list[tuple[int, int]]) -> list[tuple[int, int]]:
    index = 0
    for i in range(1, len(ranges)):
        if ranges[index][1] >= ranges[i][0]:
            ranges[index][1] = max(ranges[index][1], ranges[i][1])
        else:
            index = index + 1
            ranges[index] = ranges[i]
    return ranges[0 : index + 1]


def find_positions_wo_beacon_by_row(beacon_data: list[tuple[Sensor, Beacon]], row: int) -> list[tuple[int, int]]:
    range_at_row = []
    for (sensor, beacon) in beacon_data:
        if rng := get_range_at_row(sensor, beacon, row):
            insort(range_at_row, list(rng))
    merged = merge_intervals(range_at_row)
    return merged


def find_isolated_beacon(beacon_data, search_space) -> tuple[int, int]:
    for i in range(search_space + 1):
        val = find_positions_wo_beacon_by_row(beacon_data, i)
        if len(val) > 1:
            x = (val[1][0] + val[0][1])//2
            return x, i


def part_one(filepath, row) -> int:
    beacon_info = [(sensor, beacon) for sensor, beacon in parse_input(filepath)]
    merged = find_positions_wo_beacon_by_row(beacon_info, row)
    return len(list(chain.from_iterable([range(l, r) for l, r in merged])))


def part_two(filepath, search_space) -> int:
    multiplier = 4000000
    beacon_info = [(sensor, beacon) for sensor, beacon in parse_input(filepath)]
    x, y = find_isolated_beacon(beacon_info, search_space)
    tuning_frequency = multiplier * x + y
    return tuning_frequency