This one took a bit of thinking! This is more like I expected.

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2025/day09.ex

Part 1 I tried to do smartly by taking the outermost points, but failed - so I bruteforced it like yesterday. Generate all combinations of points, find the pair that create the biggest area. Not proud of that one, but okay.

Part 2 I calculated all of the edges created by the points in the input, by grouping them by shared coordinates. Then I took that bruteforced list from part 1, and found the first pair of points that created a rectangle with edges that didn’t intersect/exceed any edges in the list of all edges.

Honestly, I think trying to figure out if two lines intersected was the most annoying part of this And then the edge case of exceeding lines, eg. if these two edges were in the same row

---------- <- rectangle edge
------     <- input edge

It’s a little slower than I’d like (part 2 takes 1.5 seconds on my machine) but it’ll do for now!

I think I have the same solution!
Full disclaimer I got some help because I was doing some ray-casting stuff and it’s not efficient

defmodule AdventOfCode.Solutions.Y25.Day09 do
  alias AoC.Input

  def parse(input, _part) do
    input
    |> Input.stream!(trim: true)
    |> Enum.map(fn line ->
      [x, y] = String.split(line, ",", parts: 2)
      {String.to_integer(x), String.to_integer(y)}
    end)
  end

  def part_one(tiles) do
    Enum.reduce(all_rectangles_w_area(tiles), 0, fn {_, area}, best -> max(area, best) end)
  end

  defp area({xa, ya}, {xb, yb}) do
    (abs(xa - xb) + 1) * (abs(ya - yb) + 1)
  end

  def part_two(tiles) do
    {h_segments, v_segments} = build_segments([List.last(tiles) | tiles])

    tiles
    |> all_rectangles_w_area()
    |> Enum.filter(fn {rect, _} -> within_bounds?(rect, h_segments, v_segments) end)
    |> Enum.reduce(0, fn {_, area}, best -> max(area, best) end)
  end

  defp build_segments(tiles, horizontal \\ [], vertical \\ [])

  defp build_segments([{x, ya}, {x, yb} = b | rest], horizontal, vertical) do
    build_segments(
      [b | rest],
      horizontal,
      [{x, min(ya, yb), max(ya, yb)} | vertical]
    )
  end

  defp build_segments([{xa, y}, {xb, y} = b | rest], horizontal, vertical) do
    build_segments(
      [b | rest],
      [{y, min(xa, xb), max(xa, xb)} | horizontal],
      vertical
    )
  end

  defp build_segments([_], h, v) do
    {h, v}
  end

  defp all_rectangles_w_area([h | [_ | _] = t]) do
    Enum.map(t, &{rect(h, &1), area(h, &1)}) ++ all_rectangles_w_area(t)
  end

  defp all_rectangles_w_area([_]) do
    []
  end

  defp rect({x1, y1}, {x2, y2}) do
    {min(x1, x2), max(x1, x2), min(y1, y2), max(y1, y2)}
  end

  defp within_bounds?(rect, h_segments, v_segments) do
    not crosses_horizontal?(rect, h_segments) && not crosses_vertical?(rect, v_segments)
  end

  defp crosses_horizontal?(rect, h_segments) do
    {xa, xo, ya, yo} = rect

    Enum.any?(h_segments, fn h_segment ->
      {y, xha, xho} = h_segment
      y > ya and y < yo and not (xho <= xa or xha >= xo)
    end)
  end

  defp crosses_vertical?(rect, v_segments) do
    {xa, xo, ya, yo} = rect

    Enum.any?(v_segments, fn v_segment ->
      {x, yha, yho} = v_segment
      x > xa and x < xo and not (yho <= ya or yha >= yo)
    end)
  end
end

Whew, finally got it! Part2 was hard for me.

Description:

• I created a polygon around the input recognizing that tiles have a width and height of 1, so their corners are (0.5,0.5) off their coordinates depending on which way they’re turning.
• Then I go through the box’s line segments and pick the largest that doesn’t cross that polygon anywhere.
• Part 2 takes 380ms on my machine

defmodule RAoc.Solutions.Y25.Day09 do
  alias AoC.Input

  def parse(input, _part) do
    Input.read!(input)
    |> String.split("\n", trim: true)
    |> Enum.map(fn str ->
      [x, y] = String.split(str, ",")
      {String.to_integer(x), String.to_integer(y)}
    end)
  end

  def part_one(problem) do
    problem
    |> get_sorted_squares()
    |> List.first()
    |> elem(0)
  end

  def part_two(problem) do
    polygon = to_polygon(problem)

    problem
    |> get_sorted_squares()
    |> Enum.map(fn {area, {x1, y1}, {x2, y2}} ->
      # Turn these all into floats one time
      {area, {x1 + 0.0, y1 + 0.0}, {x2 + 0.0, y2 + 0.0}}
    end)
    |> Enum.find(fn box -> not square_outside_polygon?(box, polygon) end)
    |> elem(0)
  end

  def square_outside_polygon?({_area, {x1, y1}, {x2, y2}}, polygon) do
    line_seg_intersects_poly?({x1, y1}, {x2, y1}, polygon) or
      line_seg_intersects_poly?({x2, y1}, {x2, y2}, polygon) or
      line_seg_intersects_poly?({x2, y2}, {x1, y2}, polygon) or
      line_seg_intersects_poly?({x1, y2}, {x1, y1}, polygon)
  end

  def line_seg_intersects_poly?(p1, p2, [first | polygon]) do
    line_segment = {p1, p2}

    Enum.reduce_while(polygon, first, fn next, first ->
      case line_seg_intersects_line_seg?(line_segment, {first, next}) do
        true -> {:halt, true}
        false -> {:cont, next}
      end
    end)
    |> case do
      true -> true
      _ -> false
    end
  end

  def line_seg_intersects_line_seg?({{x1a, y1a}, {x2a, y2a}}, {{x1b, y1b}, {x2b, y2b}}) do
    # Take advantage of the fact that we know all these line segments are vertical or horizontal
    if x1a == x2a and y1b == y2b do
      # vertical and horizontal lines

      min(x1b, x2b) < x1a and x1a < max(x1b, x2b) and
        min(y1a, y2a) < y1b and y1b < max(y1a, y2a)
    else
      if x1b == x2b and y1a == y2a do
        # horizontal and vertical lines

        min(x1a, x2a) < x1b and x1b < max(x1a, x2a) and
          min(y1b, y2b) < y1a and y1a < max(y1b, y2b)
      else
        false
      end
    end
  end

  def to_polygon([first, second | rest]) do
    rest = rest ++ [first, second]

    polygon =
      Enum.reduce(rest, {first, second, []}, fn next, {prev, point, acc} ->
        fpoint = get_corner_point(prev, point, next)
        {point, next, [fpoint | acc]}
      end)
      |> elem(2)
      |> Enum.reverse()

    polygon ++ [List.first(polygon)]
  end

  def get_corner_point({x_prev, y_prev}, {x, y}, {x_next, y_next}) do
    l1_dir = get_dir({x_prev, y_prev}, {x, y})
    l2_dir = get_dir({x, y}, {x_next, y_next})

    case {l1_dir, l2_dir} do
      {:right, :down} ->
        {x + 0.5, y - 0.5}

      {:right, :up} ->
        {x - 0.5, y - 0.5}

      {:left, :down} ->
        {x + 0.5, y + 0.5}

      {:left, :up} ->
        {x - 0.5, y + 0.5}

      {:down, :right} ->
        {x + 0.5, y - 0.5}

      {:down, :left} ->
        {x + 0.5, y + 0.5}

      {:up, :right} ->
        {x - 0.5, y - 0.5}

      {:up, :left} ->
        {x - 0.5, y + 0.5}
    end
  end

  def get_dir({x1, y1}, {x2, y2}) when x1 == x2 and y1 < y2, do: :down
  def get_dir({x1, y1}, {x2, y2}) when x1 == x2 and y1 > y2, do: :up
  def get_dir({x1, y1}, {x2, y2}) when x1 < x2 and y1 == y2, do: :right
  def get_dir({x1, y1}, {x2, y2}) when x1 > x2 and y1 == y2, do: :left

  def get_sorted_squares(coords) do
    coords = MapSet.new(coords)

    Enum.reduce(coords, {coords, []}, fn coord1, {others, distances} ->
      others = MapSet.delete(others, coord1)

      {others,
       Enum.map(others, fn coord2 ->
         {area(coord1, coord2), coord1, coord2}
       end) ++ distances}
    end)
    |> elem(1)
    |> Enum.sort(:desc)
  end

  def area({x1, y1}, {x2, y2}) do
    (abs(x1 - x2) + 1) * (abs(y1 - y2) + 1)
  end
end

For fun I tried a version of the above that works only in integers, by multiplying the coordinates by 2 and then dividing the area by 4 at the end. That brings the time down from 380ms to 250ms.

Not the fastest for part 2 (1-2s), but works:

Setup

tiles =
  puzzle_input
  |> String.split()
  |> Enum.map(fn raw ->
    raw
    |> String.split(",")
    |> Enum.map(&String.to_integer/1)
    |> List.to_tuple()
  end)

Impl

defmodule Combinatorics do
  def combinations2(list) do
    Stream.unfold(list, fn
      [] -> nil
      [x | rest] ->
        curr = for y <- rest, do: [x, y]

        {curr, rest}
    end)
    |> Stream.flat_map(& &1)
  end
end

defmodule Rect do
  require Record

  Record.defrecordp(:rect, l: 0, t: 0, r: 0, b: 0)

  def new({ax, ay}, {bx, by}) do
    rect(l: min(ax, bx), r: max(ax, bx), t: min(ay, by), b: max(ay, by))
  end

  def area(rect() = r) do
    width(r) * height(r)
  end

  def intersect?(
        rect(l: al, r: ar, t: at, b: ab),
        rect(l: bl, r: br, t: bt, b: bb)
      ) do
    al < br and ar > bl and at < bb and ab > bt
  end

  def width(rect(r: r, l: l)), do: r - l + 1
  def height(rect(t: t, b: b)), do: b - t + 1

  def to_svg(rect(l: x, t: y) = r, opts \\ []) do
    ~s"""
    <rect x="#{x}" y="#{y}" width=#{width(r)} height="#{height(r)}"
    #{Enum.map_join(opts, " ", fn {k, v} -> ~s(#{k}="#{v}") end)} />
    """
  end
end

rects =
  Combinatorics.combinations2(tiles)
  |> Stream.map(fn [a, b] -> Rect.new(a, b) end)
  |> Enum.sort()

Part 1

rects
|> Enum.max_by(&Rect.area/1)
|> Rect.area()

Part 2

edges =
  tiles
  |> Enum.chunk_every(2, 1, tiles)
  |> Enum.map(&apply(Rect, :new, &1))
  |> Enum.sort()

rects
|> Enum.reduce({0, nil}, fn r, {max, p} ->
  a = Rect.area(r)

  if a > max and not Enum.any?(edges, &Rect.intersect?(r, &1)) do
    {a, r}
  else
    {max, p}
  end
end)

Sheesh, I’ve been bending over backwards in my code to do this. Thanks!

I’m not sure how that works. Since you call the function with a being the rectangle and b being the edge, I interpret this as “check if the rectangle is fully included in the edge”, which will never be true since edges have either a width or a height of 1.

What am I missing here?

Ah nevermind I get it. I should note that somewhere, I always have a hard time writing all the cases for the intersections but yours is very clean.

(PS: I also used svg rendering to see more clearly what I was dealing with, definitely useful!)

defmodule Aoc25.Day09 do
  @moduledoc "https://adventofcode.com/2025/day/9"

  require Aoc

  @doc ~S"""
  ## Examples
    iex> Aoc25.Day09.part1("example.txt")
    50
    iex> Aoc25.Day09.part1("input.txt")
    4746238001
  """
  def part1(file_path) do
    {_points, area} =
      file_path
      |> Aoc.get_input()
      |> Aoc.extract_numbers()
      |> Enum.chunk_every(2)
      |> Enum.map(&List.to_tuple/1)
      |> areas()
      |> Enum.max_by(&elem(&1, 1))

    area
  end

  defp areas(list, acc \\ []) do
    case list do
      [point | rest_points] ->
        acc =
          acc ++
            Enum.map(rest_points, fn other_point ->
              {{point, other_point}, rectangle(point, other_point)}
            end)

        areas(rest_points, acc)

      [] ->
        Enum.sort_by(acc, fn {_points, distance} -> distance end, :desc)
    end
  end

  defp rectangle({x1, y1}, {x2, y2}) do
    (abs(x1 - x2) + 1) * (abs(y1 - y2) + 1)
  end

  @doc ~S"""
  ## Examples
    iex> Aoc25.Day09.part2("example.txt")
    24
    iex> Aoc25.Day09.part2("input.txt")
    1552139370
    iex> Aoc25.Day09.part2("example_edgecase.txt")
    12
  """
  def part2(file_path) do
    vs =
      file_path
      |> Aoc.get_input()
      |> Aoc.extract_numbers()
      |> Enum.map(&Kernel./(&1, 1))
      |> Enum.chunk_every(2)
      |> Enum.map(&List.to_tuple/1)

    edges = Enum.zip(vs, tl(vs) ++ [hd(vs)])

    areas = areas(vs)

    # this works for this example. but it's not a general solution
    # this will fail if there is a big c shaped where the void is bigger.
    # it will identify the void outside as the bigger square
    Enum.find_value(areas, fn {{{x1, y1}, {x2, y2}}, area} ->
      # We change order here to properly provide line_segments
      p1 = {x1, y1}
      p2 = {x1, y2}
      p3 = {x2, y2}
      p4 = {x2, y1}

      no_intersections? =
        edges
        |> Enum.flat_map(
          &[
            intersect?({p1, p2}, &1),
            intersect?({p2, p3}, &1),
            intersect?({p3, p4}, &1),
            intersect?({p4, p1}, &1),
            intersect?({p1, p3}, &1),
            intersect?({p2, p4}, &1)
          ]
        )
        |> Enum.all?(&(&1 == false))

      if no_intersections? do
        trunc(area)
      end
    end)
  end

  defp intersect?(line_seg1, line_seg2) do
    case Aoc.intersect_at_point(line_seg1, line_seg2) do
      {:cross, _} -> true
      _ -> false
    end
  end

  @doc ~S"""
  ## Examples
    iex> Aoc25.Day09.part2_generic("example.txt")
    24
    iex> Aoc25.Day09.part2_generic("input.txt")
    1552139370
    iex> Aoc25.Day09.part2_generic("example_edgecase.txt")
    12
  """
  def part2_generic(file_path) do
    vs =
      file_path
      |> Aoc.get_input()
      |> Aoc.extract_numbers()
      |> Enum.chunk_every(2)
      |> Enum.map(&List.to_tuple/1)

    edges = Enum.zip(vs, tl(vs) ++ [hd(vs)])

    areas = areas(vs)

    fun = fn point, {_, acc} ->
      {in?, acc} = wind(edges, point, acc)

      if in? do
        {:cont, {in?, acc}}
      else
        {:halt, {in?, acc}}
      end
    end

    Enum.reduce_while(areas, %{}, fn {{{x1, y1}, {x2, y2}}, total_area}, acc ->
      p1 = {x1, y1}
      p2 = {x1, y2}
      p3 = {x2, y2}
      p4 = {x2, y1}

      # this nonsense speed things up by quite a lot, we don't need to create all borders at once
      with {true, acc} <- wind(edges, p1, acc),
           {true, acc} <- wind(edges, p2, acc),
           {true, acc} <- wind(edges, p3, acc),
           {true, acc} <- wind(edges, p4, acc),
           {true, acc} <- Enum.reduce_while(fill(p1, p2), {nil, acc}, fun),
           {true, acc} <- Enum.reduce_while(fill(p2, p3), {nil, acc}, fun),
           {true, acc} <- Enum.reduce_while(fill(p3, p4), {nil, acc}, fun),
           {true, _acc} <- Enum.reduce_while(fill(p4, p1), {nil, acc}, fun) do
        {:halt, total_area}
      else
        {false, acc} -> {:cont, acc}
      end
    end)
  end

  defp fill({x1, y1}, {x2, y2}) do
    if x1 == x2 do
      Enum.map(y1..y2, &{x1, &1})
    else
      Enum.map(x1..x2, &{&1, y1})
    end
  end

  defp wind(edges, {px, py}, cache) do
    case Map.get(cache, {px, py}) do
      nil ->
        value = do_wind(edges, {px, py})
        {value, Map.put(cache, {px, py}, value)}

      value ->
        {value, cache}
    end
  end

  @inside 1

  defp do_wind(edges, p3) do
    edges
    |> Enum.reduce_while(0, fn {p1, p2}, acc ->
      cond do
        in_border?(p1, p2, p3) -> {:halt, @inside}
        upwards?(p1, p2, p3) and x_intersect?(p1, p2, p3) -> {:cont, acc + 1}
        downwards?(p1, p2, p3) and x_intersect?(p1, p2, p3) -> {:cont, acc - 1}
        :else -> {:cont, acc}
      end
    end)
    |> then(&(abs(&1) > 0))
  end

  defp in_border?({x1, y1}, {x2, y2}, {px, py}) do
    cross_product = (y2 - y1) * (px - x1) - (x2 - x1) * (py - y1)

    cross_product == 0 and min(x1, x2) <= px and px <= max(x1, x2) and min(y1, y2) <= py and py <= max(y1, y2)
  end

  defp upwards?({_x1, y1}, {_x2, y2}, {_px, py}) do
    y1 <= py and py < y2
  end

  defp downwards?({_x1, y1}, {_x2, y2}, {_px, py}) do
    y2 <= py and py < y1
  end

  defp x_intersect?({x1, y1}, {x2, y2}, {px, py}) do
    px < x1 + (py - y1) * (x2 - x1) / (y2 - y1)
  end
end

Cool problem, it has quite a few solutions, maybe some inputs were not so lucky.

I noticed my first solution for part2 is not complete, because c-shaped polygons would be show as inside of the polygon.

I’ve also did a slower (with some wierd optimizations) to check all cases.

optimized my solution by using my combinations helper instead of permutations - much faster now Want to keep every solution under a second if I can…

Name                     ips        average  deviation         median         99th %
day 09, part 1         72.77       13.74 ms     ±8.83%       13.58 ms       16.81 ms
day 09, part 2          3.20      312.69 ms     ±1.75%      311.01 ms      328.37 ms

Part1 was almost the same as Day8.

Part 2, I tried a few solutions, but wasn’t able to reach an efficient one. My first defeat this year.
I may come back to it after reading the solutions above, but… I’m probably going to learn Erlang over the holidays instead

Per usual, mine is golf’d to oblivion:

defmodule Day09 do
  def part1(file), do: file |> parse() |> rects() |> Enum.map(&area/1) |> Enum.max()

  def part2(file) do
    corners = parse(file)
    corners |> rects() |> Enum.sort_by(&area/1, :desc) |> find(edges(corners)) |> area()
  end

  def parse(file), do: file |> File.read!() |> String.split("\n", trim: true) |> Enum.map(&line/1)
  def line(line), do: line |> String.split(",", trim: true) |> Enum.map(&String.to_integer/1)
  def rects(corners), do: for(a <- corners, b <- corners, a != b, do: rect([a, b]))
  def rect([[ax, ay], [bx, by]]), do: {[min(ax, bx), min(ay, by)], [max(ax, bx), max(ay, by)]}
  def edges([h | t]), do: Enum.chunk_every([h | t] ++ [h], 2, 1, :discard) |> Enum.map(&rect/1)
  def area({[x1, y1], [x2, y2]}), do: (abs(x1 - x2) + 1) * (abs(y1 - y2) + 1)
  def intersect?({[a, b], [c, d]}, {[e, f], [g, h]}), do: a < g and c > e and b < h and d > f
  def find(rs, edges), do: Enum.find(rs, fn r -> Enum.all?(edges, &(not intersect?(r, &1))) end)
end

The only thing of note is that I on part 2, I checked for intersection by pretending that edges were degenerate rectangles which greatly simplified the logic.