AoC 2022 Day 15

# aoc202215.py

import pathlib
import re
import sys

from typing import Generator, TypeAlias

# Typing aliases
Coordinate: TypeAlias = tuple[int, int]
Edges: TypeAlias = Generator[Coordinate, None, None]
Report: TypeAlias = tuple[Coordinate, Coordinate, int]


def manhattan(x1: int, y1: int, x2: int, y2: int) -> int:
    """ Return 'Manhattan distance' between two points """
    return abs(x1 - x2) + abs(y1 - y2)


def parse(puzzle_input: str) -> list[Report]:
    """ Parse input """
    pattern = re.compile(r'-?\d+')
    reports: list[Report] = []
    for line in puzzle_input.splitlines():
        sx, sy, bx, by = re.findall(pattern, line)
        sensor: Coordinate = (int(sx), int(sy))
        beacon: Coordinate = (int(bx), int(by))
        manhattan_distance: int = manhattan(*sensor, *beacon)
        reports.append((sensor, beacon, manhattan_distance))
    return reports


def points_on_line(x: int, y: int, radius: int, y_value: int) -> range:
    """ Return leftmost and rightmost edges of sensor on given line """
    # Assumes y_value is within radius
    dist_from_point: int = abs(y - y_value)
    leftmost: int = x - (radius - dist_from_point)
    rightmost: int = x + (radius - dist_from_point)
    return range(leftmost, rightmost + 1)


def valid_reports(reports: list[Report], y_value: int) -> set[Report]:
    """ Return reports whose radius falls inside y_row """
    matching_reports: set[Report] = set()
    for report in reports:
        sensor, _, dist = report
        min_y: int = sensor[1] - dist
        max_y: int = sensor[1] + dist
        if min_y <= y_value <= max_y:
            matching_reports.add(report)
    return matching_reports


def part1(reports: list[Report], y_row: int) -> int:
    """ Solve part 1 """
    no_beacons: set[int] = set()
    beacons_on_y: set[int] = set()
    for report in valid_reports(reports, y_row):
        sensor, beacon, dist = report
        if beacon[1] == y_row:
            beacons_on_y.add(beacon[0])
        for x_values in points_on_line(*sensor, dist, y_row):
            no_beacons.add(x_values)

    return len(no_beacons - beacons_on_y)


def manhattan_edges(x: int, y: int, dist: int, limit: int) -> Edges:
    """ Return coordinates on edge of manhattan distance from a point """
    for offset in range(dist):
        inv_offset: int = dist - offset
        if any([x + offset < 0, x + offset > limit,
                x - offset < 0, x - offset > limit,
                x + inv_offset < 0, x + inv_offset > limit,
                x - inv_offset < 0, x - inv_offset > limit,
                y + offset < 0, y + offset > limit,
                y - offset < 0, y - offset > limit,
                y + inv_offset < 0, y + inv_offset > limit,
                y - inv_offset < 0, y - inv_offset > limit]):
            continue
        yield (x + offset, y + inv_offset)
        yield (x + inv_offset, y - offset)
        yield (x - offset, y - inv_offset)
        yield (x - inv_offset, y + offset)
    yield (-1, -1)


def part2(reports: list[Report], dimensions: int) -> int:
    """ Solve part 2 """

    # My solution is chou sloooow for input (~ 5 minutes!)
    def in_range(point: Coordinate) -> bool:
        """ See if point is in range of a sensor """
        for report in reports:
            sensor, _, dist = report
            if manhattan(*sensor, *point) <= dist:
                return True
        return False

    for report in reports:
        sensor, _, dist = report
        outsiders: Edges = manhattan_edges(*sensor, dist + 1, dimensions)
        beacon_found: bool = False
        for _ in range(dist * 4):
            test_coord = next(outsiders)
            if test_coord == (-1, -1):
                break
            if not(in_range(test_coord)):
                beacon_found = True
                distress_beacon: Coordinate = test_coord
                break
        if beacon_found:
            break
    return (distress_beacon[0] * 4_000_000) + distress_beacon[1]


def solve(puzzle_input: str) -> tuple[int, int]:
    """ Solve the puzzle for the given input """
    data: list[Report] = parse(puzzle_input)
    solution1: int = part1(data, 2_000_000)  # Correct answer was 6425133 (with my data)
    solution2: int = part2(data, 4_000_000)  # Correct answer was 10996191429555 (with my data)

    return solution1, solution2


if __name__ == "__main__":
    for path in sys.argv[1:]:
        print(f"{path}:")
        puzzle_input = pathlib.Path(path).read_text().strip()
        solutions = solve(puzzle_input)
        print('\n'.join(str(solution) for solution in solutions))