const input = require('fs').readFileSync('input-day9.txt', 'utf-8');

/** @type {Array<[number, number]} */
const points = input.split("\n").map(r => r.split(',').map(v => parseInt(v, 10)));

let largest = 0;
let largestInside = 0;
for (const [startX, startY] of points) {
    for (const [nextX, nextY] of points) {
        if (startX === nextX && startY === nextY) continue;

        const minX = Math.min(startX, nextX);
        const maxX = Math.max(startX, nextX);
        const minY = Math.min(startY, nextY);
        const maxY = Math.max(startY, nextY);

        const area = (maxX - minX + 1) * (maxY - minY + 1);
        if (area > largest) {
            largest = area;
        }

        if (area <= largestInside) continue;

        // center point check, ala https://en.wikipedia.org/wiki/Even%E2%80%93odd_rule
        const centerX = (minX + maxX) / 2;
        const centerY = (minY + maxY) / 2;
        let inside = false;
        for (const [i, [aX, aY]] of points.entries()) {
            const [bX, bY] = points[i - 1] ?? points[points.length - 1];
            if (centerX === aX && centerY === aY) {
                inside = true;
                break;
            }
            if ((aY > centerY) !== (bY > centerY)) {
                const slope = (centerX - aX) * (bY - aY) - (bX - aX) * (centerY - aY);
                if (slope === 0) {
                    inside = true;
                    break;
                }
                if ((slope < 0) !== (bY < aY)) {
                    inside = !inside;
                }
            }
        }

        if (!inside) continue;

        // check for edge intersections, ala https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
        let intersects = false;
        for (const [i, [aX, aY]] of points.entries()) {
            const [bX, bY] = points[i - 1] ?? points[points.length - 1];

            if (aX === bX) {
                if (aX > minX && aX < maxX) {
                    const wallMinY = Math.min(aY, bY);
                    const wallMaxY = Math.max(aY, bY);

                    if (Math.max(minY, wallMinY) < Math.min(maxY, wallMaxY)) {
                        intersects = true;
                        break;
                    }
                }
            } else if (aY === bY) {
                if (aY > minY && aY < maxY) {
                    const wallMinX = Math.min(aX, bX);
                    const wallMaxX = Math.max(aX, bX);

                    if (Math.max(minX, wallMinX) < Math.min(maxX, wallMaxX)) {
                        intersects = true;
                        break;
                    }
                }
            }
        }

        if (intersects) continue;

        if (area > largestInside) {
            largestInside = area;
        }
    }
}

console.log(`Part 1 Answer: ${largest}`);
console.log(`Part 2 Answer: ${largestInside}`);

package main

import (
	"aoc/utils"
	"math"
	"slices"
	"strconv"
	"strings"
	"sync"
)

type point struct {
	x, y int
}

func (p point) areaUntil(other point) int {
	dx := other.x - p.x
	if dx < 0 {
		dx = -dx
	}
	dy := other.y - p.y
	if dy < 0 {
		dy = -dy
	}

	return (dx + 1) * (dy + 1)
}

func parsePoint(line string) point {
	parts := strings.Split(line, ",")
	x, _ := strconv.Atoi(parts[0])
	y, _ := strconv.Atoi(parts[1])
	return point{x, y}
}

func getPointChannel(input chan string) chan point {
	ch := make(chan point, cap(input))

	go func() {
		for line := range input {
			ch <- parsePoint(line)
		}
		close(ch)
	}()

	return ch
}

func stepOne(input chan string) (int, error) {
	points := []point{}
	maxArea := math.MinInt

	for p := range getPointChannel(input) {
		points = append(points, p)

		if len(points) == 1 {
			continue
		}

		areas := make([]int, len(points))
		for idx, p2 := range points {
			areas[idx] = p.areaUntil(p2)
		}

		max := slices.Max(areas)
		if max > maxArea {
			maxArea = max
		}
	}

	return maxArea, nil
}

type color int8

const (
	white color = iota
	green
	red
)

type matrix struct {
	tiles  [][]color
	points []point
}

func min(x, y int) int {
	if x < y {
		return x
	} else {
		return y
	}
}

func max(x, y int) int {
	if x > y {
		return x
	} else {
		return y
	}
}

func (m *matrix) squareContainsWhiteTiles(sq segment) bool {
	xMin := min(sq[0].x, sq[1].x)
	yMin := min(sq[0].y, sq[1].y)
	xMax := max(sq[0].x, sq[1].x)
	yMax := max(sq[0].y, sq[1].y)

	for y := yMin; y < yMax; y++ {
		if m.tiles[y][xMin] == white || m.tiles[y][xMax] == white {
			return true
		}
	}

	for x := xMin; x < xMax; x++ {
		if m.tiles[yMin][x] == white || m.tiles[yMax][x] == white {
			return true
		}
	}

	return false
}

func (m *matrix) addReds() {
	for _, p := range m.points {
		m.addRed(p)
	}
}

func newMatrix(points []point) (m matrix) {
	coords := getMatrixSize(points)
	rows := coords[1] + 1
	cols := coords[0] + 1
	array := make([][]color, rows)
	for idx := range array {
		array[idx] = make([]color, cols)
	}
	m = matrix{
		tiles:  array,
		points: points,
	}

	return m
}

func (m *matrix) addRed(p point) {
	m.tiles[p.y][p.x] = red
}

func (m *matrix) makeBorders() {
	for i := 0; i < len(m.points)-1; i++ {
		m.makeBorder(m.points[i], m.points[i+1])
	}
	m.makeBorder(m.points[len(m.points)-1], m.points[0])
}

func (m *matrix) makeBorder(p1 point, p2 point) {
	if p1.x == p2.x {
		m.makeVerticalBorder(p1.x, p1.y, p2.y)
	} else {
		m.makeHorizontalBorder(p1.x, p2.x, p1.y)
	}
}

func (m *matrix) makeHorizontalBorder(x1, x2, y int) {
	if x1 > x2 {
		tmp := x1
		x1 = x2
		x2 = tmp
	}

	for i := x1; i <= x2; i++ {
		if m.tiles[y][i] == white {
			m.tiles[y][i] = green
		}
	}
}

func (m *matrix) makeVerticalBorder(x, y1, y2 int) {
	if y1 > y2 {
		tmp := y1
		y1 = y2
		y2 = tmp
	}

	for i := y1; i <= y2; i++ {
		if m.tiles[i][x] == white {
			m.tiles[i][x] = green
		}
	}
}

func (m *matrix) makeGreens() {
	m.makeBorders()

	iterCount := len(m.tiles) / MagicThreadCount

	parallel(func(thrId int) {
		for i := range iterCount {
			row := m.tiles[iterCount*thrId+i]
			inside := false
			lastWasWhite := false

			for idx, cell := range row {
				switch cell {
				case white:
					if inside {
						row[idx] = green
					}
				default:
					if lastWasWhite {
						inside = !inside
					}
				}
				lastWasWhite = cell == white
			}
		}
	})
}

func getMatrixSize(points []point) [2]int {
	var x, y int
	for _, p := range points {
		if p.x > x {
			x = p.x
		}
		if p.y > y {
			y = p.y
		}
	}
	return [2]int{x, y}
}

func (m *matrix) String() string {
	iterCount := len(m.points) / MagicThreadCount
	lines := make([]string, len(m.tiles))

	parallel(func(thrId int) {
		for i := range iterCount {
			row := m.tiles[iterCount*thrId+i]
			runes := make([]rune, len(row))
			for idx, col := range row {
				switch col {
				case white:
					runes[idx] = '.'
				case green:
					runes[idx] = 'X'
				case red:
					runes[idx] = '#'
				}
			}
			lines[iterCount*thrId+i] = string(runes)
		}
	})

	return strings.Join(lines, "\n")
}

type segment [2]point

func newSegment(p1, p2 point) segment {
	seg := [2]point{p1, p2}
	return seg
}

func (m *matrix) allValidSquaresWith(p1 point) chan segment {
	ch := make(chan segment)

	go func() {
		for _, p2 := range m.points {
			seg := newSegment(p1, p2)
			if p2 != p1 {
				ch <- seg
			}
		}
		close(ch)
	}()

	return ch
}

// 495 == 55 * 9
// 495 == 99 * 5
// 495 == 165 * 3
var MagicThreadCount = 9

func parallel(f func(int)) {
	var wg sync.WaitGroup
	for thrId := range MagicThreadCount {
		wg.Go(func() {
			f(thrId)
		})
	}

	wg.Wait()
}

func stepTwo(input chan string) (int, error) {
	points := []point{}
	for p := range getPointChannel(input) {
		points = append(points, p)
	}
	m := newMatrix(points)
	m.addReds()
	m.makeGreens()

	iterCount := len(m.points) / MagicThreadCount
	boys := make([]int, MagicThreadCount)

	parallel(func(thrId int) {
		largestBoy := math.MinInt
		for i := range iterCount {
			p := m.points[iterCount*thrId+i]

			squareCh := m.allValidSquaresWith(p)
			for sq := range squareCh {
				area := sq[0].areaUntil(sq[1])
				if area > largestBoy && !m.squareContainsWhiteTiles(sq) {
					largestBoy = area
				}
			}
		}
		boys[thrId] = largestBoy
	})

	return slices.Max(boys), nil
}

func main() {
	input := utils.FilePath("day09.txt")
	utils.RunStep(utils.ONE, input, stepOne)
	utils.RunStep(utils.TWO, input, stepTwo)
}

1i [
1,$ {
	s/^/[/
	s/$/], /
}
$i ]
$d

import "lib/github.com/diku-dk/sorts/radix_sort"

def (&&&) 'a 'b 'c (f: a -> b) (g: a -> c) (x: a): (b, c) = (f x, g x)
def odd (x: i64): bool = x % 2 == 1

def count 'a (f: a -> bool) (xs: []a): i64
  = map (f >-> i64.bool) xs |> reduce_comm (+) 0

def coordinateFromArray (as: [2]i64): (i64, i64)
  = (as[0], as[1])

def maximum = reduce_comm i64.max i64.lowest
def minimum = reduce_comm i64.min i64.highest

def concatMap [n] 'a 'b (f: a -> ?[l].[l]b) (placeholder: b) (xs: [n]a): *[]b
  = let totalLength = reduce (+) 0 <| map (\ x -> length (f x)) xs in
    ( loop (results, offset) = (replicate totalLength placeholder, 0)
      for x in xs
      do
        let bs = f x in
        let scatterIndices = indices bs |> map (+offset) in
        (scatter results scatterIndices bs, offset + length bs)
    ).0

def rectSize (a: (i64, i64)) (b: (i64, i64)) = 
  let dx = i64.max a.0 b.0 - i64.min a.0 b.0 in
  let dy = i64.max a.1 b.1 - i64.min a.1 b.1 in
  (dx + 1) * (dy + 1)

def pair_iota (n: i64): [n](i64, i64)
  = map (\ j -> (n, j)) (iota n)

def pairs 'a (xs: []a): [](a, a)
  = concatMap pair_iota (i64.highest, i64.highest) (indices xs)
    |> map (\ (i, j) -> (xs[i], xs[j]))

def findFirst 'a (f: a -> bool) (xs: []a): a
  = ( loop (i, x) = (0, xs[0])
      while not (f x)
      do (i + 1, xs[i+1])
    ) |> (.1)

def orderedPair (p: (i64, i64)): (i64, i64) = (i64.min p.0 p.1, i64.max p.0 p.1)

def overlapsWith (a: (i64, i64)) (b: (i64, i64)): bool 
  = a.0 < b.1 && b.0 < a.1

def anyInside (points: [](i64, i64)) (rectangle: (((i64, i64), (i64, i64)), i64))
  = let (lowerX, upperX) = orderedPair (rectangle.0.0.0, rectangle.0.1.0) in
    let (lowerY, upperY) = orderedPair (rectangle.0.0.1, rectangle.0.1.1) in
    map (\ (x, y) -> lowerX < x && x < upperX && lowerY < y && y < upperY) points
    |> or

def anyIntersects (edges: []((i64, i64), (i64, i64))) (rectangle: (((i64, i64), (i64, i64)), i64)): bool
  = let rectRangeX = orderedPair (rectangle.0.0.0, rectangle.0.1.0) in
    let rectRangeY = orderedPair (rectangle.0.0.1, rectangle.0.1.1) in
    map (\ e -> 
      let edgeRangeX = orderedPair (e.0.0, e.1.0) in
      let edgeRangeY = orderedPair (e.0.1, e.1.1) in
      (edgeRangeX `overlapsWith` rectRangeX) && (edgeRangeY `overlapsWith` rectRangeY)
    ) edges
    |> or

def part2 (sortedRectangles: [](((i64, i64), (i64, i64)), i64)) (points: [](i64, i64))
  = let edges = zip points (rotate 1 points) in
    let filled = \ r -> not (anyInside points r || anyIntersects edges r) in
    findFirst filled sortedRectangles
    |> (.1)

-- benchmark
-- ==
-- input @fut-input
-- auto output

def main (coordinateArrays: [][2]i64)
  = let coordinates = map coordinateFromArray coordinateArrays in
    let rectangleCorners = pairs coordinates in
    let rectangleSizes = map (id &&& uncurry rectSize) rectangleCorners in
    let sortedRectangles = radix_sort_by_key (.1) i64.num_bits i64.get_bit rectangleSizes |> reverse in
  (sortedRectangles[0].1, part2 sortedRectangles coordinates)

pub fn day09(input: &str) -> (u64, u64) {
    let mut part1 = 0;
    let mut part2 = 0;
    let mut squares = Vec::new();
    for line in input.trim().lines() {
        let (x, y) = line.split_once(',').unwrap();
        squares.push([x.parse::<u64>().unwrap(), y.parse::<u64>().unwrap()]);
    }

    let mut chunks = squares.chunks_exact(2).peekable();
    let mut lines = Vec::new();
    let peek = chunks.peek().unwrap();
    // dir is true if scanning vertically, false if horizontally
    let dir = peek[0][1] == peek[1][1];
    if !dir {
        debug_assert_eq!(peek[0][0], peek[1][0]);
    }

    // Each line is a tuple where .0 is the index in the scan direction and .1 is the pair of end
    // points for a line perpendicular to the scan direction
    for line in chunks {
        lines.push((
            line[0][dir as usize],
            [line[0][!dir as usize], line[1][!dir as usize]],
        ));
    }
    lines.sort();

    // rot is true if field 0 being less than field 1 enters the shape, false for exiting
    let rot = lines[0].1[0] < lines[0].1[1];

    for idx_1 in 0..squares.len() - 1 {
        'o: for idx_2 in (idx_1 + 1)..squares.len() {
            let s1 = squares[idx_1];
            let s2 = squares[idx_2];
            let area = (s1[0].abs_diff(s2[0]) + 1) * (s1[1].abs_diff(s2[1]) + 1);
            part1 = std::cmp::max(part1, area);

            if area <= part2 {
                continue;
            }
            // Think of "up" as the direction the scan line travels
            let floor = std::cmp::max(s1[dir as usize], s2[dir as usize]);
            let ceil = std::cmp::min(s1[dir as usize], s2[dir as usize]);
            let left_wall = std::cmp::min(s1[!dir as usize], s2[!dir as usize]);
            let right_wall = std::cmp::max(s1[!dir as usize], s2[!dir as usize]);
            let floor_idx = lines.binary_search_by_key(&floor, |(l, _)| *l).unwrap();
            let ceil_idx = lines.binary_search_by_key(&ceil, |(l, _)| *l).unwrap();
  
            // If a line contracts the valid range, check if that contraction intersects the walls,
            // since that necessitates uncolored tiles in the bounding box
            let skip = |line: [u64; 2]| {
                if rot != (line[0] < line[1]) {
                    return (left_wall..right_wall).contains(&line[0])
                        || (left_wall..right_wall).contains(&line[1]);
                }
                false
            };

            for line in &lines[ceil_idx..floor_idx] {
                if skip(line.1) {
                    continue 'o;
                }
            }
            let mut combo_ranges = Vec::new();
            // This `rev` is needed for correctness, although the full input does not seem to care
            // It actually hurts performance a lot :(
            for line in lines[0..=ceil_idx].iter().rev() {
                if skip(line.1) {
                    continue 'o;
                }
                if rot {
                    combo_ranges.push(line.1);
                } else {
                    combo_ranges.push([line.1[1], line.1[0]]);
                }
                combo_ranges = combine_ranges(combo_ranges);
                // If overlapping the target range results in no change of range, then the target
                // range is fully covered and this rectangle is valid
                let mut test_range = combo_ranges.clone();
                test_range.push([left_wall, right_wall]);
                if combo_ranges == combine_ranges(test_range) {
                    part2 = area;
                    continue 'o;
                }
            }
        }
    }
    (part1, part2)
}

# 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

use std::ops::{Range, RangeInclusive};

fn parse_input(input: &str) -> Vec<(u32, u32)> {
    input
        .lines()
        .map(|l| {
            let (a, b) = l.split_once(',').unwrap();
            (a.parse::<u32>().unwrap(), b.parse::<u32>().unwrap())
        })
        .collect()
}

#[inline]
fn area(a: (u32, u32), b: (u32, u32)) -> u64 {
    (a.0.abs_diff(b.0) as u64 + 1) * (a.1.abs_diff(b.1) as u64 + 1)
}

fn part1(input: String) {
    let tiles = parse_input(&input);
    let mut largest = 0;
    for t1 in &tiles {
        for t2 in &tiles {
            let a = area(*t1, *t2);
            if a > largest {
                largest = a;
            }
        }
    }
    println!("{largest}");
}

// Returns true only if t is not inside of the rectangle
#[inline]
fn red_allowed(t: (u32, u32), x_range: Range<u32>, y_range: Range<u32>) -> bool {
    !(t.0 > x_range.start && t.0 + 1 < x_range.end && t.1 > y_range.start && t.1 + 1 < y_range.end)
}

fn is_contained(
    a: (u32, u32),
    b: (u32, u32),
    tiles_x: &[(u32, u32)],
    tiles_y: &[(u32, u32)],
    vert_lines: &[(u32, RangeInclusive<u32>)],
    hori_lines: &[(u32, RangeInclusive<u32>)],
) -> bool {
    let x_range = a.0.min(b.0)..(a.0.max(b.0) + 1);
    let y_range = a.1.min(b.1)..(a.1.max(b.1) + 1);

    // Check that no corners (red tiles) are inside the rectangle
    let corners_ok = if x_range.end - x_range.start <= y_range.end - y_range.start {
        // Use tiles_x
        let start = match tiles_x.binary_search(&(x_range.start, 0)) {
            Ok(e) => e,
            Err(e) => e,
        };
        tiles_x
            .iter()
            .skip(start)
            .take_while(|t| t.0 < x_range.end)
            .filter(|&&t| t != a && t != b)
            .all(|t| red_allowed(*t, x_range.clone(), y_range.clone()))
    } else {
        // Use tiles_y
        let start = match tiles_y.binary_search_by_key(&(y_range.start, 0), |(x, y)| (*y, *x)) {
            Ok(e) => e,
            Err(e) => e,
        };
        tiles_y
            .iter()
            .skip(start)
            .take_while(|t| t.1 < y_range.end)
            .filter(|&&t| t != a && t != b)
            .all(|t| red_allowed(*t, x_range.clone(), y_range.clone()))
    };
    if !corners_ok {
        return false;
    }

    // Check that no line intersects the inside of the rectangle
    let start = match vert_lines.binary_search_by_key(&x_range.start, |(x, _)| *x) {
        Ok(e) => e,
        Err(e) => e,
    };
    for (x, line) in vert_lines
        .iter()
        .skip(start)
        .take_while(|(x, _)| *x < x_range.end)
    {
        if x_range.start < *x
            && x_range.end > *x + 1
            && (y_range.start + 1).max(*line.start()) < (y_range.end - 1).min(line.end() + 1)
        {
            return false;
        }
    }
    let start = match hori_lines.binary_search_by_key(&y_range.start, |(y, _)| *y) {
        Ok(e) => e,
        Err(e) => e,
    };
    for (y, line) in hori_lines
        .iter()
        .skip(start)
        .take_while(|(y, _)| *y < y_range.end)
    {
        if y_range.start < *y
            && y_range.end > *y + 1
            && (x_range.start + 1).max(*line.start()) < (x_range.end - 1).min(line.end() + 1)
        {
            return false;
        }
    }
    true
}

fn part2(input: String) {
    let tiles = parse_input(&input);

    let mut vert_lines = Vec::new();
    let mut hori_lines = Vec::new();
    let mut prev = *tiles.last().unwrap();
    for &t in &tiles {
        if t.0 == prev.0 {
            vert_lines.push((t.0, t.1.min(prev.1)..=t.1.max(prev.1)));
        } else {
            debug_assert_eq!(t.1, prev.1);
            hori_lines.push((t.1, t.0.min(prev.0)..=t.0.max(prev.0)));
        }
        prev = t;
    }
    vert_lines.sort_by_key(|(x, _)| *x);
    hori_lines.sort_by_key(|(y, _)| *y);

    let mut tiles_x = tiles.clone();
    tiles_x.sort();
    let mut tiles_y = tiles.clone();
    tiles_y.sort_by_key(|(x, y)| (*y, *x));
    let mut largest = 0;
    for (idx, t1) in tiles.iter().enumerate() {
        for t2 in tiles.iter().take(idx) {
            let a = area(*t1, *t2);
            if a > largest && is_contained(*t1, *t2, &tiles_x, &tiles_y, &vert_lines, &hori_lines) {
                largest = a;
            }
        }
    }
    println!("{largest}");
}

util::aoc_main!();

   fn check_wall_outside(
        c: &(&Coord, &Coord),
        top: usize,
        bottom: usize,
        left: usize,
        right: usize,
    ) -> bool {
        if (c.0.x <= left && c.1.x <= left) || (c.0.x >= right && c.1.x >= right) {
            return true;
        }
        if (c.0.y <= top && c.1.y <= top) || (c.0.y >= bottom && c.1.y >= bottom) {
            return true;
        }
        false
    }

   #[test]
    fn test_y2025_day9_part2_mine1() {
        let input = include_str!("../../input/2025/day_9.txt");
        let coords = input
            .lines()
            .map(|l| {
                let halfs = l.split_once(',').unwrap();
                Coord {
                    x: halfs.0.parse::<usize>().unwrap(),
                    y: halfs.1.parse::<usize>().unwrap(),
                }
            })
            .collect::<Vec<Coord>>();

        let mut walls = vec![];

        for i in 0..coords.len() {
            let first = &coords[i];
            let second = coords.get(i + 1).unwrap_or(coords.first().unwrap());

            walls.push((first, second));
        }

        let mut max_area = 0;
        for i in 0..coords.len() {
            let first = &coords[i];
            'next_rect: for j in i..coords.len() {
                let second = &coords[j];
                if first == second {
                    continue 'next_rect;
                }
                let area = (first.x.abs_diff(second.x) + 1) * (first.y.abs_diff(second.y) + 1);
                if area < max_area {
                    continue 'next_rect;
                }

                let (top, bottom) = if first.y > second.y {
                    (second.y, first.y)
                } else {
                    (first.y, second.y)
                };

                let (left, right) = if first.x > second.x {
                    (second.x, first.x)
                } else {
                    (first.x, second.x)
                };

                for wall in &walls {
                    if !check_wall_outside(wall, top, bottom, left, right) {
                        continue 'next_rect;
                    }
                }

                max_area = area;
            }
        }
        assert_eq!(max_area, 1542119040);
        println!("Part 2: {}", max_area);
    }

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <inttypes.h>
#include <assert.h>

#define MIN(a,b)	((a)<(b)?(a):(b))
#define MAX(a,b)	((a)>(b)?(a):(b))
#define LEN(a)		(sizeof(a)/sizeof(*(a)))

#define MAXP	512

/*
 * There are two main problems with part 2:
 *  1. Deciding what is inside and what is outside of the polyline
 *  2. The points being _tiles_, not zero-width coordinates
 *
 * This solution walks the outline and calculates "normals" for each
 * point, which are angles pointing _out_ of the shape. Those are used
 * to derrive the outside boundary of the shape, the lines that go
 * around, not through, the corner tiles. Witth that we can do
 * more-or-less normal intersection checks.
 *
 * Angles are stored as 1/8ths of a circle.
 */

struct point { int x,y; };
struct edge { int off, lo,hi; };

static struct point pts[MAXP];
static struct edge hedges[MAXP/2];
static struct edge vedges[MAXP/2];
static int norms[MAXP];
static int np, nhe, nve;

static int wrapa(int a) { return (a+8)%8; }

static int
cmp_edges(const void *a, const void *b)
{
	return ((const struct edge *)a)->off -
	       ((const struct edge *)b)->off;
}

static int
line_dir(struct point a, struct point b)
{
	return 4*(a.x>b.x || a.y<b.y) + 2*(a.x!=b.x);
}

static void
calculate_normals(void)
{
	int i, dir1,dir2, angle;
	int normal; /* relative to the current line  */

	dir1 = line_dir(pts[np-1], pts[0]);
	normal = wrapa(dir1 - 2); /* start left, assuming CCW order */

	for (i=0; i<np; i++) {
		dir2 = line_dir(pts[i], pts[i==np-1 ? 0 : i+1]);
		angle = dir2 == dir1-2 || dir2 == dir1+6 ? -2 : 2;

		/* the point's normal is diagonal, halfway turned */
		norms[i] = wrapa(normal + angle/2);

		dir1 = dir2;
		normal = wrapa(normal + angle);
	}
}

static void
generate_edges(void)
{
	struct point a,b;
	int i,j;

	for (i=0; i<np; i++) {
		a = pts[i];
		b = pts[(j = i==np-1 ? 0 : i+1)];

		/* shift the line to be _around_ point */
		a.x += norms[i]<4; a.y += norms[i]>2 && norms[i]<6;
		b.x += norms[j]<4; b.y += norms[j]>2 && norms[j]<6;

		if (a.x == b.x) {
			assert(nve < (int)LEN(vedges));
			vedges[nve].off = a.x;
			vedges[nve].lo = MIN(a.y, b.y);
			vedges[nve].hi = MAX(a.y, b.y);
			nve++;
		} else if (a.y == b.y) {
			assert(nhe < (int)LEN(hedges));
			hedges[nhe].off = a.y;
			hedges[nhe].lo = MIN(a.x, b.x);
			hedges[nhe].hi = MAX(a.x, b.x);
			nhe++;
		} else
			assert(!"diagonal line");
	}

	qsort(hedges, nhe, sizeof(*hedges), cmp_edges);
	qsort(vedges, nve, sizeof(*vedges), cmp_edges);
}

static bool
rect_inside(struct point a, struct point b)
{
	struct edge *e;
	int x0,y0,x1,y1;

	/*
	 * Line intersection of the four rectangle edges against all
	 * the polyline edges, with a caveat: the outline is 1 unit
	 * thick, not zero-width! This is why some of the comparisons
	 * are or-equals.
	 */

	x0 = MIN(a.x, b.x); y0 = MIN(a.y, b.y);
	x1 = MAX(a.x, b.x); y1 = MAX(a.y, b.y);

	for (e = vedges; e < vedges+nve; e++) {
		if (e->off <= x0) continue;
		if (e->off > x1) break;
		if (y0 >= e->lo && y0 < e->hi) return false;
		if (y1 >= e->lo && y1 < e->hi) return false;
	}

	for (e = hedges; e < hedges+nhe; e++) {
		if (e->off <= y0) continue;
		if (e->off > y1) break;
		if (x0 >= e->lo && x0 < e->hi) return false;
		if (x1 >= e->lo && x1 < e->hi) return false;
	}

	return true;
}

int
main()
{
	int64_t p1=0,p2=0, area, i,j;

	for (; scanf(" %d,%d", &pts[np].x, &pts[np].y)==2; np++)
		assert(np+1 < MAXP);
	
	assert(np >= 4);

	calculate_normals();
	generate_edges();

	for (i=0; i<np-1; i++)
	for (j=i+1; j<np; j++) {
		area = (int64_t)(abs(pts[i].x - pts[j].x) + 1) *
		       (int64_t)(abs(pts[i].y - pts[j].y) + 1);
		if (area > p1)
			p1 = area;
		if (area > p2 && rect_inside(pts[i], pts[j]))
			p2 = area;
	}

	printf("09: %"PRIi64" %"PRIi64"\n", p1, p2);
}

class Day09 : AOCSolution {
    override val year = 2025
    override val day = 9

    override fun part1(inputFile: String): String {
        val corners = readCorners(inputFile)

        var largestRectangle = -1L
        for (i in 0 until corners.lastIndex) {
            val firstCorner = corners[i]
            for (j in i + 1 until corners.size) {
                largestRectangle = maxOf(largestRectangle, outsideArea(firstCorner, corners[j]))
            }
        }

        return largestRectangle.toString()
    }

    override fun part2(inputFile: String): String {
        val corners = readCorners(inputFile)

        val (horizontal, vertical) = buildAndPartitionLines(corners)
        // Sort the lines along their orthogonal axis
        // Horizontal lines are sorted top to bottom
        horizontal.sortBy { (from) -> from.y }
        // Vertical lines are sorted left to right
        vertical.sortBy { (from) -> from.x }

        var largestRectangleArea = -1L
        for (i in 0 until corners.lastIndex) {
            val first = corners[i]
            for (j in i + 1 until corners.size) {
                val second = corners[j]
                val area = outsideArea(first, second)
                if (area > largestRectangleArea) {
                    val topLeft = Point(minOf(first.x, second.x), minOf(first.y, second.y))
                    val bottomRight = Point(maxOf(first.x, second.x), maxOf(first.y, second.y))
                    if (intersectsNone(horizontal, vertical, topLeft, bottomRight)) {
                        largestRectangleArea = maxOf(largestRectangleArea, area)
                    }
                }
            }
        }

        return largestRectangleArea.toString()
    }

    private companion object {
        private fun readCorners(inputFile: String): List<Point> {
            val corners = readResourceLines(inputFile).map { line ->
                val splitIndex = line.indexOf(',')
                val x = JavaLong.parseLong(line, 0, splitIndex, 10)
                val y = JavaLong.parseLong(line, splitIndex + 1, line.length, 10)
                Point(x, y)
            }
            return corners
        }

        /**
         * Builds two lists of lines from connected corners in [corners].
         * The corners are required to construct lines that are orthogonal to their
         * predecessors and successors.
         *
         * @return two lists, the first one containing the horizontal lines and
         * the second one containing the vertical lines.
         */
        private fun buildAndPartitionLines(corners: List<Point>): Pair<Array<Line>, Array<Line>> {
            require(corners.size >= 2)

            // Origin point of the next line
            var from = corners.last()
            val lines = buildList {
                corners.forEach { to ->
                    add(Line(from, to))
                    from = to
                }
            }

            val (horizontal, vertical) = lines.partition { line -> line.from.y == line.to.y }
            return horizontal.toTypedArray() to vertical.toTypedArray()
        }

        private fun outsideArea(a: Point, b: Point): Long {
            val width = abs(a.x - b.x) + 1
            val height = abs(a.y - b.y) + 1
            return width * height
        }

        /**
         * Checks whether a rectangle intersects any line in the arrays of horizontal and vertical lines.
         *
         * @param horizontal the array of strictly horizontal lines
         * @param vertical the array of strictly vertical lines
         * @param topLeft the top-left corner of the rectangle to check
         * @param bottomRight the bottom-right corner of the rectangle to check
         * @return whether any of the lines intersect the rectangle
         */
        private fun intersectsNone(
            horizontal: Array<Line>,
            vertical: Array<Line>,
            topLeft: Point,
            bottomRight: Point
        ): Boolean {
            // Find the index of the first horizontal line above the rectangle
            val beginHorizontal = horizontal.binarySearchFirst(
                target = topLeft.y
            ) { (from) -> from.y }.coerceAtLeast(0)

            for (i in beginHorizontal until horizontal.size) {
                if (horizontal[i].from.y >= bottomRight.y) {
                    // End early, when encountering the first line on the bottom edge
                    break
                }
                if (isLineInsideRect(horizontal[i], topLeft, bottomRight)) {
                    return false
                }
            }

            // Find the index of the first vertical line on the left edge of the rectangle
            val beginVertical = vertical.binarySearchFirst(
                target = topLeft.x
            ) { (from) -> from.x }.coerceAtLeast(0)

            for (i in beginVertical until vertical.size) {
                if (vertical[i].from.x >= bottomRight.x) {
                    // End early, when encountering the first line on the right edge
                    break
                }
                if (isLineInsideRect(vertical[i], topLeft, bottomRight)) {
                    return false
                }
            }

            return true
        }

        /**
         * Axis-aligned line to rectangle intersection test.
         * Lines are considered inside, if and only if, they are inside the horizontal
         * or vertical bounds of the rectangle.
         * They are not considered inside, if they are on the edges of the rectangle.
         * @param line the line to check the intersection for
         * @param topLeft the top-left corner of the rectangle to check
         * @param bottomRight the bottom-right corner of the rectangle to check
         * @return whether the line intersects the rectangle
         */
        private fun isLineInsideRect(
            line: Line,
            topLeft: Point,
            bottomRight: Point
        ): Boolean {
            val (left, top) = topLeft
            val (right, bottom) = bottomRight

            val fromX = line.from.x
            val toX = line.to.x

            // Vertical
            if ((fromX <= left && toX <= left) || (fromX >= right && toX >= right)) {
                // Line is completely to the left or right of the rectangle
                return false
            }

            val fromY = line.from.y
            val toY = line.to.y
            // Horizontal
            if ((fromY <= top && toY <= top) || (fromY >= bottom && toY >= bottom)) {
                // Line is completely above or below the rectangle
                return false
            }
            return true
        }

        private fun <T> Array<T>.binarySearchFirst(
            from: Int = 0,
            to: Int = size,
            target: Long,
            extractor: ToLongFunction<T>
        ): Int {
            var low = from
            var high = to - 1
            var result = -1

            while (low <= high) {
                val mid = low + ((high - low) / 2)
                val comparison = extractor.applyAsLong(get(mid)).compareTo(target)
                if (comparison == 0) {
                    result = mid
                    high = mid - 1
                } else if (comparison < 0) {
                    low = mid + 1
                } else {
                    high = mid - 1
                }
            }
            return result
        }
    }
}