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)

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.