#!/usr/bin/env python

# https://adventofcode.com/2025/day/9

# requires Python package "shapely":
#     python -m venv .venv
#     . .venv/bin/activate
#     pip install shapely matplotlib
 
from shapely import *
import matplotlib.pyplot as plt

f = open("day09input.txt", "r")
#f = open("testinput.txt", "r")
data = [l.rstrip("\n").split(",") for l in f.readlines()]
data = list(map(lambda x: (int(x[0]), int(x[1])), data))

def part1(tiles: list[list[int, int]]) -> int:
  l = len(tiles)
  max_area = (0, None, None)

  # loop over tiles
  for i in range(l - 1):
    for j in range(i + 1, l):
      area = abs(tiles[i][0] - tiles[j][0] + 1) * abs(tiles[i][1] - tiles[j][1] + 1)
      if area > max_area[0]:
        max_area = (area, i, j)

  return max_area[0]  


offsets = [(0, 0), (0, 1), (1, 0), (1, 1)]

def offset_polygon(tiles: list[list[int, int]]) -> Polygon:
  polygons = [Polygon(list(map(lambda t: (t[0] + o[0], t[1] + o[1]), tiles))) for o in offsets]
  return union_all(polygons, grid_size=1)


def part2(tiles: list[list[int, int]]) -> int:
  polygon = offset_polygon(tiles)
  prepare(polygon)

#  plt.plot(*polygon.exterior.xy, c="b")
#  plt.show()
  
  l = len(tiles)
  max_area = (0, None, None)

  for i in range(l - 1):
    for j in range(i + 1, l):
      rect = offset_polygon([tiles[i], (tiles[i][0], tiles[j][1]), tiles[j], (tiles[j][0], tiles[i][1])])
      # check if rect is inside polygon (see https://stackoverflow.com/a/56916189) 
      if not rect.difference(polygon).area < 1e-14:
#        print(f"Rectangle {i}, {j} is not inside polygon -> skipping")
        continue
      
#      print(f"Rectangle {i}, {j} has area {rect.area} and current max_area is {max_area[0]}")
      # check if area is larger than current max
      if rect.area > max_area[0]:
        print(f"Rectangle {i}, {j} is the new max with area {rect.area}")
        max_area = (int(rect.area), i, j)

  print(f"Solution: The largest rectangle spans between points {max_area[1]} ({tiles[max_area[1]]}) and {max_area[2]} ({tiles[max_area[2]]}) with an area of {max_area[0]}")

  plt.plot(*polygon.exterior.xy, c="b")
  i, j = max_area[1], max_area[2]
  rect = offset_polygon([tiles[i], (tiles[i][0], tiles[j][1]), tiles[j], (tiles[j][0], tiles[i][1])])
  plt.plot(*rect.exterior.xy, c="r")
  plt.show()
  return max_area[0]


#print(part1(data))
print(part2(data))