# combinations helps us get all pairs of red tiles
# pairwise helps us get all adjacent pairs of red tiles
from itertools import combinations, pairwise
from collections import deque

def get_area(p1, p2):
    x1, y1 = p1
    x2, y2 = p2
    return (abs(x2 - x1) + 1) * (abs(y2 - y1) + 1)

@timer()
def part1(data: str):
    red_tiles = [tuple(map(int, line.split(','))) for line in data.splitlines()]

    max_area = 0
    for r1, r2 in combinations(red_tiles, 2):
        max_area = max(max_area, get_area(r1, r2))
    return max_area

def compress_coordinates(coords: list[tuple[int, int]]):
    i_of_interest_set = set()
    j_of_interest_set = set()

    for i, j in coords:
        i_of_interest_set.update([i-1, i, i+1])
        j_of_interest_set.update([j-1, j, j+1])
    
    sorted_is = sorted(list(i_of_interest_set))
    sorted_js = sorted(list(j_of_interest_set))
    m = len(sorted_is)
    n = len(sorted_js)

    compress_i_map = {val: id for id, val in enumerate(sorted_is)}
    compress_j_map = {val: id for id, val in enumerate(sorted_js)}
    return m, n, compress_i_map, compress_j_map


@timer()
def part2(data: str):
    red_tiles = [tuple(map(int, line.split(','))) for line in data.splitlines()]
    m, n, compress_i_map, compress_j_map = compress_coordinates(red_tiles)

    def get_compressed_coords(og_coords: tuple[int, int]):
        return compress_i_map[og_coords[0]], compress_j_map[og_coords[1]]

    # make the grid
    grid = [['.']*n for _ in range(m)]
    for i, j in red_tiles:
        ci, cj = get_compressed_coords((i, j))
        grid[ci][cj] = '#'

    # make the walls of the polygon enclosed by the red tiles
    def make_line(r1, r2):
        r1_i, r1_j = get_compressed_coords(r1)
        r2_i, r2_j = get_compressed_coords(r2)

        wall_char = '#'
        if r1_i == r2_i:
            # same row
            row = r1_i
            for col in range(min(r1_j, r2_j) + 1, max(r1_j, r2_j)):
                grid[row][col] = wall_char
        elif r1_j == r2_j:
            # same col
            col = r1_j
            for row in range(min(r1_i, r2_i) + 1, max(r1_i, r2_i)):
                grid[row][col] = wall_char

    for r1, r2 in pairwise(red_tiles):
        make_line(r1, r2)
    make_line(red_tiles[-1], red_tiles[0])

    # whiteout the exterior
    DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    queue = deque([(0, 0)])
    while queue:
        i, j = queue.popleft()
        if grid[i][j] == ' ':
            continue
        grid[i][j] = ' '

        for di, dj in DIRECTIONS:
            ni, nj = i+di, j+dj
            if not (0 <= ni < m) or not (0 <= nj < n):
                continue
            if grid[ni][nj] != '.':
                continue
            queue.append((ni, nj))
    
    # DEBUG: print the grid
    # print()
    # for row in grid:
    #     print(''.join(row))
    
    # check if the rectangle formed by the corners r1, r2 is contained within the red-green polygon
    def check_contained(r1, r2):
        r1_i, r1_j = get_compressed_coords(r1)
        r2_i, r2_j = get_compressed_coords(r2)
        
        min_i, max_i = min(r1_i, r2_i), max(r1_i, r2_i)
        min_j, max_j = min(r1_j, r2_j), max(r1_j, r2_j)

        for i in range(min_i, max_i+1):
            for j in range(min_j, max_j+1):
                if grid[i][j] == ' ':
                    return False
        return True

    # get the max area of a rectangle that is contained within the red-green polygon
    #   and has red tiles at two of its corners
    max_area = 0
    for r1, r2 in combinations(red_tiles, 2):
        area = get_area(r1, r2)
        if area <= max_area:
            # dont bother
            continue
        if not check_contained(r1, r2):
            continue
        max_area = area

    return max_area

sample = """7,1
11,1
11,7
9,7
9,5
2,5
2,3
7,3"""
assert part1(sample) == 50
assert part2(sample) == 24