AoC y2023 d5

from collections.abc import Sequence


def get_seeds(line: str, as_ranges: bool) -> list[tuple[int, int]]:
    seeds = line.removeprefix("seeds:").split()

    if as_ranges:
        return [
            (s := int(start), s + int(length))
            for start, length in zip(seeds[::2], seeds[1::2])
        ]
    else:
        return [(s := int(x), s + 1) for x in seeds]


def impl(data: Sequence[str], as_ranges: bool) -> int:
    it = iter(data)

    src_list = get_seeds(next(it), as_ranges)
    dst_list = []

    for line in it:
        if not line:
            src_list += dst_list
            dst_list = []
            next(it)  # Skip "XXX-to-YYY map:" line
            continue

        dst, src, len_ = map(int, line.split())

        new_src_list = []

        while src_list:
            start, end = src_list.pop()

            lo = max(start, src)
            hi = min(end, src + len_)

            if lo >= hi:
                new_src_list.append((start, end))
                continue

            offset = dst - src
            dst_list.append((lo + offset, hi + offset))

            if lo > start:
                new_src_list.append((start, lo))

            if hi < end:
                new_src_list.append((hi, end))

        src_list = new_src_list

    return min(s for s, _ in src_list + dst_list)


def part1(data: Sequence[str]) -> int:
    return impl(data, False)


def part2(data: Sequence[str]) -> int:
    return impl(data, True)