aoc25-9-2.py

from typing import List, TypeAlias

Point: TypeAlias = tuple[int, int]

def solve(input_path: str):
    with open(input_path) as file:
        input = file.read().strip()
        points = parse_input(input)
        index = index_points(points)
        segments = normalize_segments(points)
        convexity = get_convexity(points)
        candidates = sorted_candidates(points)
        for a, i0, i1 in candidates:
            if is_good_candidate(i0, i1, points, index, segments, convexity):
                print(a)
                return

def parse_input(input: str) -> List[Point]:
    tiles: List[Point] = []
    for line in input.split("\n"):
        x, y = line.split(",")
        x = int(x)
        y = int(y)
        tiles.append((x, y))
    return tiles

def index_points(points: List[Point]) -> dict[Point, int]:
    return {p: i for i, p in enumerate(points)}

def normalize_segments(points: List[Point]) -> list[tuple[Point, Point]]:
    return [normalize(p, points[(i + 1) % len(points)]) for i, p in enumerate(points)]

def sorted_candidates(points: List[Point]) -> List[tuple[int, int, int]]:
    candidates: List[tuple[int, int, int]] = []
    for i0, p0 in enumerate(points):
        for i1 in range(i0):
            p1 = points[i1]
            candidates.append((area(p0, p1), i0, i1))
    candidates.sort(key=lambda t: t[0], reverse=True)
    return candidates

def area(p0: Point, p1: Point) -> int:
    x0, y0 = p0
    x1, y1 = p1
    return (abs(x0 - x1) + 1) * (abs(y0 - y1) + 1)

def is_good_candidate(
    i0: int, i1: int,
    points: List[Point],
    index: dict[Point, int],
    segments: list[tuple[Point, Point]],
    convexity: List[bool]
) -> bool:
    r0, r1 = normalize(points[i0], points[i1])

    for p0, p1 in segments:
        if does_line_cross_rect(p0, p1, r0, r1):
            return False

    i2 = index.get((points[i0][0], points[i1][1]))
    i3 = index.get((points[i1][0], points[i0][1]))

    for i in (i0, i1, i2, i3):
        if i is not None:
            if convexity[i] == is_point_inside_rect(inner_point(points, i), r0, r1):
                return True

    return False

def normalize(r0: Point, r1: Point) -> tuple[Point, Point]:
    x0, y0 = r0
    x1, y1 = r1
    return (min(x0, x1), min(y0, y1)), (max(x0, x1), max(y0, y1))

def does_line_cross_rect(p0: Point, p1: Point, r0: Point, r1: Point) -> bool:
    x0, y0 = p0
    x1, y1 = p1
    rx0, ry0 = r0
    rx1, ry1 = r1
    if x0 == x1:
        return rx0 < x0 < rx1 and y1 > ry0 and y0 < ry1
    else:
        return ry0 < y0 < ry1 and x1 > rx0 and x0 < rx1

def get_convexity(points: List[Point]) -> List[bool]:
    assert_clockwise(points)
    convex: List[bool] = [False] * len(points)
    for i, (curr_x, curr_y) in enumerate(points):
        next_x, next_y = points[(i + 1) % len(points)]
        prev_x, prev_y = points[(i - 1) % len(points)]
        assert prev_x == curr_x or prev_y == curr_y
        convex[i] = (prev_x == curr_x and (next_x > curr_x) ^ (prev_y < curr_y)
                     or (next_y > curr_y) ^ (prev_x > curr_x))
    return convex

def assert_clockwise(points: List[Point]):
    m, (mx, my) = min(enumerate(points), key=lambda t: t[1])
    nx, ny = points[(m + 1) % len(points)]
    assert my == ny
    assert mx < nx

def is_point_inside_rect(p: Point, r0: Point, r1: Point) -> bool:
    px, py = p
    rx0, ry0 = r0
    rx1, ry1 = r1
    return (rx0 < px < rx1 or rx1 < px < rx0) and (ry0 < py < ry1 or ry1 < py < ry0)

def inner_point(points: List[Point], i: int) -> Point:
    px, py = points[i]
    next_x, next_y = points[(i + 1) % len(points)]
    prev_x, prev_y = points[(i - 1) % len(points)]
    if px == next_x:
        return px + sign(prev_x - px), py + sign(next_y - py)
    else:
        return px + sign(next_x - px), py + sign(prev_y - py)

def sign(x: int) -> int:
    return 1 if x > 0 else -1 if x < 0 else 0

solve("input1.txt")