Haskell, part 2

I broke down the outline into a set of boxes by scanning over them.

type Box = (C, C) -- inclusive coordinates
makeBoxes :: [C] -> [Box]
makeBoxes cs =
    let cs' = sort cs -- left-to-right first, top-to-bottom second
        scanLines = cs' & groupOn fst
     in scanOver 0 [] scanLines
  where
    scanOver lastX currentYs [] = []
    scanOver lastX currentYs (new : rest) =
        let newX = new & head & fst
            closedBoxes = do
                [y1, y2] <- currentYs & chunksOf 2
                pure ((lastX, y1), (newX, y2))
            newYs =
                -- Take the new column and remove anything that
                -- corresponds to a y value that appears in both
                merge currentYs (map snd new)
         in -- Close the current boxes
            closedBoxes ++ scanOver newX newYs rest
    merge [] ns = ns
    merge ms [] = ms
    merge (m : ms) (n : ns)
        | m < n = m : merge ms (n : ns)
        | m > n = n : merge (m : ms) ns
        | otherwise = merge ms ns

The fiddly bit was handling all the cases for shape subtraction. I don't give it here because it's just a slog, but the gist is this:

type Shape = [Box]
subtractBox :: Box -> Box -> Shape -- returns whatever's left

subtractShape :: Shape -> Shape -> Shape -- this is just a fold.

The idea: take a bounding box that's just large enough to cover all coordinates. From that, subtract the set of boxes above. You get a set of boxes that are in the "outside", ie, illegal region. [I did it this way because managing shape subtraction from the set of "inside" boxes is just more work.]

Then for each candidate rectangle, if it overlaps with any of the "out-of-bounds" boxes, it's not a solution.

C++

Correct answer in under 2 seconds, ie. about a hundred times longer than the rest of the puzzles so far combined. Can't think of a more efficient way to do this; no doubt it'll come to me at two in the morning, like usual.

Part 2 implementation breaks down the 'green tiles outline' into a series of line segments and then uses the even-odd winding rule to decide whether a point is inside or outside. Tracing the outline of the potential boxes to see whether the entirety is inside allows selection of the largest. We can skip tracing any potential box that wouldn't be bigger than what we have so far, and since the tests are easy to parallelise, have done so.

#include <atomic>
#include <boost/log/trivial.hpp>
#include <boost/unordered/concurrent_flat_map.hpp>
#include <cstddef>
#include <fstream>
#include <mutex>
#include <thread>

namespace {

struct Point {
  int x, y;
  auto operator+=(const Point &b) -> Point & {
    x += b.x;
    y += b.y;
    return *this;
  }
};

auto operator==(const Point &a, const Point &b) {
  return a.x == b.x && a.y == b.y;
}

auto operator!=(const Point &a, const Point &b) { return !(a == b); }

std::size_t hash_value(const Point &p) {
  return size_t(p.x) << 32 | size_t(p.y);
}

using Map = std::vector<Point>;
struct Line {
  Point a, b;
};

auto read() {
  auto rval = std::vector<Point>{};
  auto ih = std::ifstream{"09.txt"};
  auto line = std::string{};
  while (std::getline(ih, line)) {
    auto c1 = line.find(',');
    rval.emplace_back(
        std::stoi(line.substr(0, c1)), std::stoi(line.substr(c1 + 1))
    );
  }
  return rval;
}

auto size(const Point &a, const Point &b) -> uint64_t {
  size_t w = std::abs(a.x - b.x) + 1;
  size_t h = std::abs(a.y - b.y) + 1;
  return w * h;
}

auto part1(const std::vector<Point> &p) {
  auto maxi = std::size_t{};
  for (auto a = size_t{}; a < p.size() - 1; ++a)
    for (auto b = a + 1; b < p.size(); ++b)
      maxi = std::max(maxi, size(p[a], p[b]));
  return maxi;
}

auto make_line(const Point &a, const Point &b) {
  return Line{
      {std::min(a.x, b.x), std::min(a.y, b.y)},
      {std::max(a.x, b.x), std::max(a.y, b.y)}
  };
}

auto direction(const Point &a, const Point &b) {
  auto dx = b.x - a.x;
  auto dy = b.y - a.y;
  if (dx != 0)
    dx /= std::abs(dx);
  if (dy != 0)
    dy /= std::abs(dy);
  return Point{dx, dy};
}

// evaluates 'insideness' with the even-odd rule.  On the line -> inside
auto inside_uncached(const Point &a, const std::vector<Line> &lines) -> bool {
  auto even_odd = 0;
  for (const auto &line : lines) {
    if (line.a.y == line.b.y) { // horizontal
      if (a.y != line.a.y)
        continue;
      if (a.x <= line.a.x)
        continue;
      if (a.x < line.b.x)
        return true;
      even_odd += 1;
    } else { // vertical
      if (a.x < line.a.x)
        continue;
      if (a.y < line.a.y || a.y > line.b.y)
        continue;
      if (a.x == line.a.x)
        return true;
      even_odd += 1;
    }
  }
  return even_odd % 2 == 1;
}

using Cache = boost::unordered::concurrent_flat_map<Point, bool>;
auto cache = Cache{};

auto inside(const Point &a, const std::vector<Line> &lines) -> bool {
  std::optional<bool> o;
  bool found = cache.visit(a, [&](const auto &x) { o = x.second; });
  if (found)
    return o.value();
  auto b = inside_uncached(a, lines);
  cache.insert({a, b});
  return b;
}

auto inside(const Line &a, const std::vector<Line> &lines) -> bool {
  auto dir = direction(a.a, a.b);
  auto point = a.a;
  while (point != a.b) {
    point += dir;
    if (!inside(point, lines))
      return false;
  }
  return true;
}

auto part2(std::vector<Point> p) {
  auto outline = std::vector<Line>{};

  for (auto a = size_t{}; a < p.size() - 1; ++a)
    outline.push_back(make_line(p[a], p[a + 1]));
  outline.push_back(make_line(p.back(), p.front()));

  std::sort(outline.begin(), outline.end(), [](auto &a, auto &b) {
    return a.a.x < b.a.x;
  });

  std::sort(p.begin(), p.end(), [](auto &a, auto &b) {
    if (a.x != b.x)
      return a.x < b.x;
    return a.y > b.y;
  });

  auto maximum = std::atomic_uint64_t{};
  auto update_lock = std::mutex{};
  auto column_worker = std::atomic_uint64_t{};
  auto threadpool = std::vector<std::thread>{};

  for (auto t = size_t{}; t < std::thread::hardware_concurrency(); ++t) {
    threadpool.push_back(std::thread([&]() {
      while (true) {
        auto a = column_worker++;
        if (a > p.size() - 1)
          break;
        for (auto b = p.size() - 1; b > a; --b) {
          auto box = size(p[a], p[b]);

          // if it wouldn't be bigger, skip it
          if (box <= maximum)
            continue;

          // quick check for the opposite corners
          if (!inside(Point{p[a].x, p[b].y}, outline) ||
              !inside(Point{p[b].x, p[a].y}, outline))
            continue;

          // trace the outline
          auto left = make_line(p[a], Point{p[a].x, p[b].y});
          if (!inside(left, outline))
            continue;
          auto top = make_line(Point{p[a].x, p[b].y}, p[b]);
          if (!inside(top, outline))
            continue;
          auto right = make_line(Point{p[b].x, p[a].y}, p[b]);
          if (!inside(right, outline))
            continue;
          auto bottom = make_line(p[a], Point{p[b].x, p[a].y});
          if (!inside(bottom, outline))
            continue;

          // it's all on green tiles.  update as the biggest so far
          {
            auto _ = std::lock_guard<std::mutex>(update_lock);
            if (box > maximum)
              maximum = box;
          }
        }
      }
    }));
  }

  for (auto &thread : threadpool)
    thread.join();

  return uint64_t(maximum);
}

} // namespace

auto main() -> int {
  auto tiles = read();
  BOOST_LOG_TRIVIAL(info) << "Day 9: read " << tiles.size();
  BOOST_LOG_TRIVIAL(info) << "1: " << part1(tiles);
  BOOST_LOG_TRIVIAL(info) << "2: " << part2(tiles);
}

Uiua

Part 1 was easy, part 2 is ...less so...

Any way, here's my Part 1 while I'm still thinking about this.

# AOC 2025 Day 09
# Experimental!
D ← &fras"AOC2025day09.txt"  # Drop your file here and edit name
/↥/×+1⌵⍉/-⍉₂⧅<2⋕°csv D       # Part 1 
∧⍜⊡⋅1⟜(˜↯0+1/↥)⍜⍉≡⍜⍆⊛⋕°csv D # Visualised data

Part 2

This is basically me thinking out loud, so it's untidy, brutal, repetitive and slow. (20s in the pad) link if you care

# Experimental!
# AOC 2025 Day 09
D     ← "7,1\n11,1\n11,7\n9,7\n9,5\n2,5\n2,3\n7,3"
D     ← &fras"AOC2025day09.txt" # Drop your file here and edit name
Parse ← ⋕°csv
Part₁ ← /↥/×+1⌵⍉/-⍉₂⧅<2

Squeeze ← ⍜⍉≡⍜⍆⊛          # Squeeze (add a sort to inspect)
Draw    ← ∧⍜⊡⋅1⟜(˜↯0+1/↥) # Draw

HLines ← (
  Squeeze Parse D
  ⍆⊕(□⍆)⊛⊸≡⊢
  ∧◇(⍜⊡˜⍜(⊏|˙=)⊙˜∘⊃(⊢⊢|↘⊙⇡°⊟+0_1⊣⍉))
)

VLines ← (
  Squeeze Parse D
  ⍆⊕(□⍆)⊛⊸≡⊣
  ∧◇(⍜⊡˜⍜(⊏|˙=)⊙˜∘⊃(⊣⊣|↘⊙⇡°⊟+0_1⊢⍉))
)
DrawBorder ← ⍜⍉VLines HLines ˜↯0↯2+1/↥♭Squeeze Parse D # Draws full border

# DrawBorder Squeeze # running this shows these as key boundary points -> [219 121] [219 123]
# ⊏≡⌟˜⨂[[219 121] [219 123]]⊸Squeeze # which map to -> [[94985 48652][94985 50114]]
# leftmost -> only look left, rightmost-> only look right
# SO, now fill the shape to make this easier.
Fill ← (
  ⊙⊙1           # fill colour.
  Good ← =0⊙◌⊡⊢ # Needs filling. Simple edges-check.
  # Take first of list. If needs fill, do so and then add
  # its four neighbours into queue. Repeat until queue is empty.
  ⍢(⨬(↘1|◴⊂+A₂¤°⊂ ⊃(⋅∘|∘|⋅⋅⋅∘)◡(⍜(⊡|⋅∘)⊢))◡Good
  | >0⧻)
  ⋅⊙⋅
)
DrawBorder     # Comment out everything below here to view the boundary.
Fill [219_120] # Now fill that boundary ([2_1] for test)
Squeeze Parse D
# ([0 1] for test)
[219 123] #  [219 121] gave the wrong answer, so it's this.
≡⌞⊟       # couple this with every other point
# Extract the covered window of the array for each pair of corners.
# (Very probably doing this the hard way:-()
# Only keep those that are all 1.
▽⤚≡⌟(=1/×♭≡⌞⊏⊙⊏˜∘∩(↘⊙⇡°⊟+0_1⍆)°⊟⍉)
# Pick out our squeezed indices
⨂Squeeze Parse D
# Find out what the unsqueezed values were
˜⊏Parse D
# Find areas, return max.
/↥≡/×+1⌵≡/-

Javascript

I generally like trying the brute force approach first (though in the latter days it just wastes time). After exhausting 32GB of RAM I changed approaches.

Admittedly I don't really understand these algorithms as well as I would like, and I also will admit I inadvertently was LLM assisted :(. When I was trying to figure out what algo I should use and the AI summary in Google's search spoiled me. But I did learn alot.

One interesting observation, unrelated to the solution itself, is the solutions runs about 30% faster in Firefox than it does via Node (25.2.1 and 24.11.1) on my machine.

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}`);

Haskell

This is pretty ugly. I got rather fed up after trying out various heuristics when the test case passed but actual data didn't.

import Control.Arrow  
import Data.Function  
import Data.Ix  
import Data.List  
import Data.Ord  

readInput :: String -> [(Int, Int)]  
readInput = map ((read *** (read . tail)) . break (== ',')) . lines  

pairs = concatMap (\(x : xs) -> map (x,) xs) . init . tails  

toRange ((a, b), (c, d)) = ((min a c, min b d), (max a c, max b d))  

onTiles loop rect = cornersInside && not crossingEdges  
  where  
    cornersInside =  
      let ((a, b), (c, d)) = rect  
       in inside (a, d) && inside (c, b)  
    verticalEdges = sortOn (Down . fst . fst) $ filter (uncurry ((==) `on` fst)) loop  
    inside (x, y) =  
      let intersecting ((a, b), (_, d)) = a <= x && inRange (min b d, max b d) y  
       in maybe False (uncurry ((>) `on` snd)) $ find intersecting verticalEdges  
    crossingEdges =  
      let ((a, b), (c, d)) = rect  
       in any (crossingLoop . toRange) $  
            [ ((a, b), (c, b)),  
              ((c, b), (c, d)),  
              ((c, d), (a, d)),  
              ((a, d), (a, b))  
            ]  
    crossingLoop ((a, b), (c, d))  
      | a == c = anyEdge (\((e, f), (g, h)) -> f == h && f > b && f < d && g > a && e < c)  
      | b == d = anyEdge (\((e, f), (g, h)) -> e == g && e > a && e < c && h > b && f < d)  
    anyEdge = flip any $ map toRange loop  

main = do  
  input <- readInput <$> readFile "input09"  
  let rects = pairs input  
      loop = zip (last input : input) input  
      go = print . maximum . map (rangeSize . toRange)  
  go rects  
  go $ filter (onTiles loop) rects  

Kotlin

My solution can't be very good because it took over a minute to run part 2. I used a ray casting algorithm to determine if a point was in the main polygon. I did that for the 2 corners of each rectangle that weren't given as input. If both of those corners were in the polygon, then I checked each point of each edge of that rectangle.

My first stab at this didn't consider the edge points of the rectangle, and after looking at some visualizations of the polygon, I could see where I was going wrong. I wouldn't have considered a rectangle with all 4 corners in the polygon could have an edge that goes outside the polygon without looking at a visualization.

Part 2 code:

fun main() {
    val input = getInput(9)
    val polygon = parseInput1(input)
    val rectangles: MutableList<Rectangle> = mutableListOf()
    for (i in polygon.indices) {
        for (j in i + 1..<polygon.size) {
            rectangles.add(Rectangle(polygon[i], polygon[j]))
        }
    }
    rectangles.sortByDescending { it.area }
    var answer: Rectangle? = null
    for (rectangle in rectangles) {
        if (isInsidePolygon(rectangle.corner3, polygon)
            && isInsidePolygon(rectangle.corner4, polygon)
        ) {
            val edgePoints: MutableList<Pair<Long, Long>> = mutableListOf()
            edgePoints.addAll(getAllPointsBetween(rectangle.corner1, rectangle.corner3))
            edgePoints.addAll(getAllPointsBetween(rectangle.corner1, rectangle.corner4))
            edgePoints.addAll(getAllPointsBetween(rectangle.corner2, rectangle.corner3))
            edgePoints.addAll(getAllPointsBetween(rectangle.corner2, rectangle.corner4))
            var isInside = true
            for (edgePoint in edgePoints) {
                if (!isInsidePolygon(edgePoint, polygon)) {
                    isInside = false
                    break
                }
            }
            if (isInside) {
                answer = rectangle
                break
            }
        }
    }
    println(answer?.area ?: "Whoops")
}

fun parseInput1(input: String): List<Pair<Long, Long>> = input.lines()
    .filter { it.isNotBlank() }
    .map {
        val split = it.split(",")
        split[0].toLong() to split[1].toLong()
    }

data class Rectangle(val corner1: Pair<Long, Long>, val corner2: Pair<Long, Long>) {
    val corner3: Pair<Long, Long> = corner1.first to corner2.second
    val corner4: Pair<Long, Long> = corner2.first to corner1.second
    val area: Long = (1 + abs(corner1.first - corner2.first)) * (1 + abs(corner1.second - corner2.second))
}

fun isInsidePolygon(point: Pair<Long, Long>, polygon: List<Pair<Long, Long>>): Boolean {
    val x = point.first
    val y = point.second
    var intersectionCount = 0L
    for (i in polygon.indices) {
        val p1 = polygon[i]
        val p2 = polygon[(i + 1) % polygon.size]
        if (point == p1 || point == p2 || isOnEdge(point, p1, p2)) {
            return true
        }
        val y1 = p1.second
        val y2 = p2.second
        val crossesRay = (y in y1..<y2) || (y in y2..<y1)
        if (crossesRay) {
            val x1 = p1.first
            val x2 = p2.first
            val xIntersect = (x2 - x1) * (y - y1).toDouble() / (y2 - y1) + x1
            if (x < xIntersect) {
                intersectionCount++
            }
        }
    }
    return intersectionCount % 2L != 0L
}

fun isOnEdge(p: Pair<Long, Long>, p1: Pair<Long, Long>, p2: Pair<Long, Long>): Boolean {
    val crossProduct = (p.second - p1.second) * (p2.first - p1.first) -
            (p.first - p1.first) * (p2.second - p1.second)
    if (crossProduct != 0L) {
        return false
    }
    val isBetweenX = p.first in minOf(p1.first, p2.first)..maxOf(p1.first, p2.first)
    val isBetweenY = p.second in minOf(p1.second, p2.second)..maxOf(p1.second, p2.second)
    return isBetweenX && isBetweenY
}

fun getAllPointsBetween(left: Pair<Long, Long>, right: Pair<Long, Long>): List<Pair<Long, Long>> {
    if (right.first == left.first) {
        val max = maxOf(left.second, right.second)
        val min = minOf(left.second, right.second)
        return (min + 1..<max).toList().map { right.first to it }
    } else if (right.second == left.second) {
        val max = maxOf(left.first, right.first)
        val min = minOf(left.first, right.first)
        return (min + 1..<max).toList().map { it to right.second }
    } else {
        throw Exception("Whoops")
    }
}

Futhark

First, formatting the input with an unreadable sed script:

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

Then, the actual program. main is the default entrypoint, part one is trivially solved in the preparations for part two. In part two, the faster check is to look for any point inside the current rectangle. If this can't find any, it'll have to check whether any edge crosses through the rectangle with a simple range check. I'm not happy with the performance, I feel like I left a lot on the table.

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)

Rust

The problem today just flustered me. Sometimes I'm not convinced I've gotten any better at programming since 2022 (yes, I still used that exact hack of a combine_ranges for this problem) Runs on my Thinkpad P1 Gen2 in 180.9 +- 0.9 ms on external power (or 726.8 +- 2.1 ms on battery; can't remember how I configured performance/battery saver honestly lol)

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)
}

Rust

This one broke me, I couldn't do it without looking at some of the solutions in this thread. In the end, basically all that was necessary for part 2 is to check for every candidate rectangle if:

1. No corners (red tiles) are inside the rectangle, and
2. No lines intersect the rectangle.

Plus a bunch shifting numbers around by 1. The code is not pretty at all, but at least it turned very efficient, solving part 2 in just 4.3ms. I have no idea how generalized the solution is. It definitely assumes that any larger rectangle is spanned inside the area and that the path doesn't cross over itself. Also of course that there are no two corners next to each other forming a 180 degree turn.

View on github

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!();

Yes I used a polygon library so what... I did eyeball the shape and guessed what the result should have been like but still more pleasing to write something that applies generally. Although I did put an area threshold (eyeballed) which subsets the corners to test, it only reduces run time to about 1/2 (from ~10s to ~5s) so that is not necessarily very critical. If I hadn't used this library, I would probably do sth along the lines of defining my own rectangle classes with unions, intersections etc so wouldn't be a more clever approach but much more time consuming.

from pathlib import Path

import numpy as np
import shapely

cwd = Path(__file__).parent

def parse_input(file_path):
  with file_path.open("r") as fp:
    data = list(map(lambda x: list(map(int,x.split(','))), fp.readlines()))

  return np.array(data)


def construct_shapes(coordinates, threshold):

  Itriu = np.triu_indices(coordinates.shape[0], k=2)
  squares = []

  for i0,i1 in zip(*Itriu):

    c0 = tuple(coordinates[i0,:])
    c1 = tuple(coordinates[i1,:])
    area = np.prod(abs(np.array(c0) - np.array(c1)) + np.array([1,1]))

    if area>threshold:
      c2 = (c0[0],c1[1])
      c3 = (c1[0],c0[1])
      squares.append(shapely.Polygon((c0,c3,c1,c2)))

  polygon = shapely.Polygon(coordinates)

  return polygon, squares


def solve_problem(file_name, redgreen=False, threshold=0):

  coordinates = parse_input(Path(cwd, file_name))

  if not redgreen:
    areas = np.prod(abs(coordinates[None,:] - coordinates[:,None]) +\
                    np.array([1,1])[None,None,:], axis=-1)
    max_area = np.max(areas)

  else:
    polygon, squares = construct_shapes(coordinates, threshold)
    max_area = -np.inf

    for inds,square in enumerate(squares):
      if square.area==0:
        continue

      if polygon.contains(square):
        c = np.array(list(zip(*square.exterior.coords.xy)))
        if (a:=np.prod(abs(c[0] - c[2]) + np.array([1,1])))>max_area:
          max_area = a

  return int(max_area)



if __name__ == "__main__":

  assert solve_problem("test_input") == 50
  assert solve_problem("input") == 4763509452
  assert solve_problem("test_input", True, 1) == 24
  assert solve_problem("input", True, 15000*80000) == 1516897893 # threshold by eyeballing the shape

Python

Part 2 is only partially optimized (runs in ~7.5s).

The optimization I did do is to compress the grid coords by recording all red tiles and their adjacent cells only (thanks Everybody,Codes #15)
The part which needs further optimization is my approach to getting the largest rectangle in the polygon. I did it by flood-filling the area outside the polygon, then walking through all cells of every pair of red tiles to make sure their rectangle is within the polygon.

# 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

C

Well this one got me stumped for a bit but after a few false starts, lots of debugging and some cleanup I'd say I have a pretty good solution now! The points being tiles rather than zero-width corners was the tricky bit here.

Basic working: it walks through the points, keeping track of normal vectors (the "outside" direction). With those, it generates the zero-width outline around the points, and from there on it's pretty much old fashioned line intersection checks.

The initial nasty solve took 1.2 seconds on my Raspberry Pi 400, but some optimization (like sorting the edges list) brought that down to 0.08s on the Pi, and 0.02s on my 10-year old PC, and I'm quite happy with the code now.

#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);
}

Uiua

My silly part one solution, because I have no idea how to do part two (this is usually the difficulty at which I bow out, but I want to try actually expanding my knowledge this year!).

Parse         ← ⊜(⊜⋕⊸≠@,)⊸≠@\n
CornerClosest ← ⊏⊢⍏⊸≡⌞(/+ⁿ2-)
Big           ← 9999999
RectSize      ← /×+1⌵-
Part₁ ← (
  ∩⌟∩⌟CornerClosest 0_0 1000000_1000000 Big_0 0_Big
  ↥∩RectSize
)

$ 7,1
$ 11,1
$ 11,7
$ 9,7
$ 9,5
$ 2,5
$ 2,3
$ 7,3

&fras "9.txt"
Part₁ Parse

Applied topology! Instead of using the standard even-odd raycasting trick for winding number (which I didn't remember), I constructed an explicit inward-pointing normal at each edge of the large polygon. This way you can test directly whether edges that lie on the boundary of your candidate rectangle have the right orientation. The code isn't pretty (edge-exterior-to-rect? is particularly awful), and I'm sure it could be made faster, but this worked almost the first time.

(ql:quickload :str)

(defun parse-line (line)
  (map 'vector #'parse-integer (str:split "," line)))

(defun read-inputs (filename)
  (let ((lines (uiop:read-file-lines filename)))
    (make-array (list (length lines) 2)
                :initial-contents (mapcar #'parse-line lines))))

(defun area (corners v w)
  "Yield the area of the rectangle between two diagonally opposite corners identified by index."
  (* (1+ (abs (- (aref corners v 0) (aref corners w 0))))
     (1+ (abs (- (aref corners v 1) (aref corners w 1))))))

(defun main-1 (filename)
  (let* ((red-tiles (read-inputs filename))
         (ntiles (car (array-dimensions red-tiles))))
    (loop for v from 0 to (1- ntiles)
          maximize (loop for w from 0 to (1- v)
                         maximize (area red-tiles v w)))))

;;; A rectangle is enclosed by the region if and only if both of the following are true:
;;; 1. No edge of the region passes through the interior of the rectangle;
;;; 2. When an edge of the region runs along an edge of the rectangle, the interior of
;;;    the region and the interior of the rectangle lie on the same side.
;;; So our first problem is to find the interior side of each edge of the region.

(defun edges-with-interior (corners)
  ;; Anchor: a vertical edge with minimum x coordinate has the interior on the +x side
  (let* ((n (car (array-dimensions corners)))
         (min-x (loop for i from 0 to (1- n) minimize (aref corners i 0)))
         (arg-min-x (loop for i from 0 to (1- n)
                          when (= (aref corners i 0) min-x)
                            return i))
         ;; Mapping from edge direction unit vector to inward-pointing normal to edge
         ;; Initial inward normal is known to be #(1 0); sense of the rotation from edge
         ;; direction depends on direction of initial edge
         (edge-interior-dir
           (if (> (aref corners (1+ arg-min-x) 1) (aref corners arg-min-x 1)) ; +y
               '((#(0 1) . #(1 0)) (#(1 0) . #(0 -1)) (#(0 -1) . #(-1 0)) (#(-1 0) . #(0 1)))
               '((#(0 -1) . #(1 0)) (#(1 0) . #(0 1)) (#(0 1) . #(-1 0)) (#(-1 0) . #(0 -1)))))
         (interior-labeled-edges
           (loop for i from arg-min-x to (+ arg-min-x n -1)
                 collect (let* ((j (mod i n))
                                (jj (mod (1+ i) n))
                                (unit-edge
                                  (vector (signum (- (aref corners jj 0) (aref corners j 0)))
                                          (signum (- (aref corners jj 1) (aref corners j 1)))))
                                (unit-interior-normal
                                  (cdr (assoc unit-edge edge-interior-dir :test #'equalp))))
                           (vector (aref corners j 0) (aref corners j 1)
                                   (aref corners jj 0) (aref corners jj 1)
                                   (aref unit-interior-normal 0) (aref unit-interior-normal 1))))))
    (make-array (list n 6) :initial-contents interior-labeled-edges)))

(defun edge-exterior-to-rect? (corners edges-with-interior i v w)
  (let ((rxmin (min (aref corners v 0) (aref corners w 0)))
        (rxmax (max (aref corners v 0) (aref corners w 0)))
        (rymin (min (aref corners v 1) (aref corners w 1)))
        (rymax (max (aref corners v 1) (aref corners w 1)))
        (exmin (min (aref edges-with-interior i 0) (aref edges-with-interior i 2)))
        (exmax (max (aref edges-with-interior i 0) (aref edges-with-interior i 2)))
        (eymin (min (aref edges-with-interior i 1) (aref edges-with-interior i 3)))
        (eymax (max (aref edges-with-interior i 1) (aref edges-with-interior i 3)))
        (ixdir (aref edges-with-interior i 4))
        (iydir (aref edges-with-interior i 5)))
    (or (and (< exmin rxmin) (<= exmax rxmin)) ; edge is left of rectangle
        (and (>= exmin rxmax) (> exmax rxmax)) ; edge is right of rectangle
        (and (< eymin rymin) (<= eymax rymin)) ; edge is above rectangle
        (and (>= eymin rymax) (> eymax rymax)) ; edge is below rectangle
        (and (= exmin exmax rxmin) (= ixdir 1) (= iydir 0)) ; edge lies on left side pointing in
        (and (= exmin exmax rxmax) (= ixdir -1) (= iydir 0)) ; edge lies on right side pointing in
        (and (= eymin eymax rymin) (= ixdir 0) (= iydir 1)) ; edge lies on top side pointing in
        (and (= eymin eymax rymax) (= ixdir 0) (= iydir -1))))) ; edge lies on bottom side pointing in

(defun enclosed? (corners edges-with-interior v w)
  (loop for i from 0 to (1- (car (array-dimensions edges-with-interior)))
        unless (edge-exterior-to-rect? corners edges-with-interior i v w)
          return nil
        finally (return t)))

(defun main-2 (filename)
  (let* ((red-tiles (read-inputs filename))
         (ntiles (car (array-dimensions red-tiles)))
         (edges-with-interior (edges-with-interior red-tiles)))
    (loop for v from 0 to (1- ntiles)
          maximize (loop for w from 0 to (1- v)
                         maximize (if (enclosed? red-tiles edges-with-interior v w)
                                      (area red-tiles v w)
                                      0)))))

Rust

pt2: 71ms.

Wow. What a step up in difficulty. Using the geo library got me the right answer, and quickly in terms of code, but run time was terrible (2m+). Switching back to simply checking if a wall is entirely outside the rectangle got me a much faster win, and the code isn't too bad either.

   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);
    }

Uiua

Part 1 only for now, probably not the most optimal solution (calculating all possible rectangles) but at least it's short ^^

Run with example input

::spoiler Code

$ 7,1
$ 11,1
$ 11,7
$ 9,7
$ 9,5
$ 2,5
$ 2,3
$ 7,3
# &fras "input-9.txt" ◌
⊜(⊜⋕⊸≠@,)⊸≠@\n
⧅<2
≡(/×+₁-⊃↧↥°⊟)
/↥

:::