Uiua

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

::: spoiler a hint that might help you visualising the data reveals some interesting patterns. Follow link to do 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.

::: spoiler Code

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

:::

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

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  

Go

Oh my god. I'm calling: tomorrow will probably be the day I fail lmao. It has been so hard to get a correct result. Then I spent a solid half hour to optimize the solution so that :

• it terminates
• it doesn't need 600GB of RAM

It seems that using a int8 to encode color instead of the default int64 was the right idea lmao. I'm also happy to have understood how to multithread a Go application and I'm totally bought by the simplicity. This language really helped me by abstracting everything in goroutines and call it a day.

I have also been able to create small goroutines which job was to generate values one by one and abstract the real control-flow in order not to allocate a whole big array at once, reducing further my memory footprint.

This is the second time in my life I want to say I loved using Go. Last time was when I waited to pretty print json files, my colleague told me how to write a wannabe-oneliner in Go to do it myself. Never looked back.

::: spoiler day09.go

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

:::

Futhark

First, formatting the input with an unreadable sed script:

::: spoiler formatting 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.

::: spoiler As always, wonky syntax highlighting

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)

:::

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

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) ::: spoiler solution

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

:::

Guile Scheme

Runs in 3.2 seconds.

I quickly got part 2 two to work on the example input, but i struggled a lot with bugs in the polygon-test code before getting the right result. To find my bugs, i made a visualization using raylib. It's not part of the snippet, but you can find the full code here.

(define-module (day9)
  #:use-module (input)
  #:use-module (util)
  #:use-module (srfi srfi-1)
  #:use-module (ice-9 match)
  #:use-module (ice-9 control)
  #:use-module (system foreign)
  #:use-module (rnrs bytevectors)
  #:use-module (raylib)
  #:export (day))

(define (parse-coord str)
  (map string->number (string-split str #\,)))

(define (parse port)
  (-> (read-lines port)
      (curry map string-trim-both)
      (curry filter (negate string-empty?))
      (curry map parse-coord)
      (curry map (match-lambda [(a b) (cons a b)]))))

(define (area a b)
  (match-let ([(ax . ay) a] [(bx . by) b])
             (* (+ 1 (abs (- bx ax)))
                (+ 1 (abs (- by ay))))))

(define (is-in-polygon pos corners)
  (match-let ([(x . y) pos])
    (call/ec (λ (return)
      (odd? (let go ([corners (cons (last corners) corners)])
        (match corners
          [() 0]
          [(_) 0]
          [((bx . by) (ax . ay) . rest)
           (+ (call/ec (λ (next)
                          (cond
                            [(= bx ax)
                             (when (< y (min ay by))
                               (next 0))
                             (when (>= y (max ay by))
                               (next 0))
                             (when (= x ax)
                               (return #t))
                             (when (< x ax)
                               (next 1))
                             (when (> x ax)
                               (next 0))]
                            [(= by ay)
                             (when (not (= y ay))
                               (next 0))
                             (when (< x (min ax bx))
                               (next 0))
                             (when (> x (max ax bx))
                               (next 0))
                             (return #t)])))
                             (go (cons `(,ax . ,ay) rest)))])))))))

(define (lines-intersect? a b)
  (match-let* ([((asx . asy) . (aex . aey)) a]
               [((bsx . bsy) . (bex . bey)) b]
               [alx (min asx aex)]
               [ahx (max asx aex)]
               [blx (min bsx bex)]
               [bhx (max bsx bex)]
               [aly (min asy aey)]
               [ahy (max asy aey)]
               [bly (min bsy bey)]
               [bhy (max bsy bey)]
               [a-horizontal (= asy aey)]
               [b-horizontal (= bsy bey)])
    (and
      (not (equal? a-horizontal b-horizontal))
      (if a-horizontal
        (and
          (<= alx blx)
          (>= ahx blx)
          (> aly bly)
          (< ahy bhy))
        (lines-intersect? b a)))))

(define (line-intersects-polygon? line corners)
  (let go ([corners (cons (last corners) corners)])
    (match corners
        [() #f]
        [(a) #f]
        [(a b . rest)
         (or
           (lines-intersect? line `(,a . ,b))
           (go (cons b rest)))])))

(define (rectangle-corners a b)
  (match-let ([(ax . ay) a] [(bx . by) b])
    `((,(min ax bx) . ,(min ay by))
      (,(min ax bx) . ,(max ay by))
      (,(max ax bx) . ,(min ay by))
      (,(max ax bx) . ,(max ay by)))))

(define (rectangle-edges a b)
  (match-let ([(tl bl tr br) (rectangle-corners a b)])
    `((,tl . ,tr)
      (,tr . ,br)
      (,br . ,bl)
      (,bl . ,tl))))

(define-day day 9 'real
  (λ (port called-directly)
     (define red-tiles (parse port))

     (define is-in-loop? (cached (λ (pos) (is-in-polygon pos red-tiles))))
     (define intersects-loop? (cached (λ (line) (line-intersects-polygon? line red-tiles))))

     (define tile-combinations (pairs red-tiles))

     (define part1 (-> tile-combinations
                       (curry map (match-lambda [(a . b) (area a b)]))
                       (sort _ >)
                       car))

     (define part2 (-> tile-combinations
                       (curry filter (match-lambda [(a . b)
                                                    (and (all is-in-loop? (rectangle-corners a b))
                                                         (all (λ (edge) (not (intersects-loop? edge))) (rectangle-edges a b)))]))
                       (curry map (match-lambda [(a . b) `(,(area a b) . (,a . ,b))]))
                       (sort _ (lambda (a b) (on car > a b)))
                       car))

     (when called-directly (visualization red-tiles (cdr part2)))

     `(,part1 ,(car part2))))

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.

::: spoiler click to view code

# 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

::: ___

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

::: spoiler Code

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

:::

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.

::: spoiler Code and algorithm description (A wall is outside if its entirely to the left OR entirely to the right of the rect) OR (entirely above OR entirely below).

   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

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

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.

::: spoiler Code

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

:::

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.

Kotlin

This one was a journey.

Part 1 is just a greedy search over all the corner pairs to find the largest area.

I began part 2 with just using Java AWT, which worked but was slow. I didn't want to implement a proper polygon intersection algorithm and found a few patterns in the input.
Basically: All lines are axis aligned and all lines are orthogonal to the lines before and after them. This allows me to easily partition and sort the lists of lines. Because all the lines are axis-aligned and the lines are allowed to be on the edges of the rectangles, a smart check against all the lines can be constructed. Horizontal lines above and below and vertical lines to the left or to the right of the rectangle can be skipped entirely. This cuts the time down tremendously.
I needed to implement a custom binary search, though. The standard lib only supplies a search that gives any element that matches the target, not specifically the first one.

Code on GitHub ::: spoiler Code

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

:::

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
≡(/×+₁-⊃↧↥°⊟)
/↥

:::