We were all waiting for a (more) complex problem, and here it is, finally! As of now, it’s the only problem that has 3x more people who only solved the first part than those who solved both - for previous days, the ratio is ~6x the other way.
First part is fairly straightforward: just pick the “top” and “bottom” corners (to reduce the search somewhat), and calculate the maximum possible area between them (note the “mirroring” trick).
# Part 1
defmodule Y2025.Day09 do
def corners(points, sort) do
do_corners(points |> Enum.sort(sort), [], sort)
end
def do_corners([], acc, _), do: acc
def do_corners([[x, y] = head | rest], acc, sort) do
acc = [head | acc]
points =
rest
|> Enum.reject(fn [x1, y1] ->
if sort == :asc do
x1 >= x && y1 >= y
else
x1 <= x && y1 <= y
end
end)
do_corners(points, acc, sort)
end
def bottom_corners(points), do: corners(points, :asc)
def top_corners(points), do: corners(points, :desc)
def parse(s) do
String.split(s, "\n")
|> Enum.map(fn line -> String.split(line, ",") |> Enum.map(&String.to_integer/1) end)
end
def top_bottom_max(points) do
for [x1, y1] <- bottom_corners(points), [x2, y2] <- top_corners(points) do
max(x2 - x1 + 1, 0) * max(y2 - y1 + 1, 0)
end
|> Enum.max()
end
def part1(s) do
points = parse(s)
mirror_points = points |> Enum.map(fn [x, y] -> [-x, y] end)
max(top_bottom_max(points), top_bottom_max(mirror_points))
end
end
Part 2 is much less straightforward. I came up with the following algorithm - I’m sure both the algorithm and the implementation can be simplified (and I might do the latter tomorrow):
-
We turn point coordinates into
Pointstructures containing (a) thex,ycoordinates themselves, (b) vectorsv1andv2pointing to the next and previous points in the loop, (c)angle, which is either:sharpor:obtuse, depending on the “local” shape of the inside of the loop at this point, (d) a set of other points belonging strictly to top left, top right, bottom left, and bottom right quadrants (tp,tr,bt,br), and a set of sides of the loop that are at thetop,bottom,left, orrightfrom this point. -
We then select the maximum area between all the pairs
p1,p2of points that are allowed. -
A pair is allowed if: (a) the line from
p1top2lies inside both angles atp1andp2, respectively; (b) there are no other points lying strictly withinp1, p2rectangle; (c) no other side intersects thep1, p2line.
There are two less trivial pars of the implementation:
-
We use a scalar product of two vectors to determine whether a given vector is inside the angle at point
p, using the following fact: ifv1,v2are two orthogonal vectors, thenvlies between them iff both scalar productsv * v1andv * v2are positive. For obtuse angles, we reverse this check. -
To assign angles, we select the point with the minimum (lexicographic) coordinates - it is guaranteed to have a sharp angle - and then we follow the loop, keeping or flipping the angle, until we return to the starting point.
# Part 2
defmodule Y2025.Day09
# ... part 1
defmodule Point do
defstruct [:left, :right, :top, :bottom, :v1, :v2, :x, :y, :angle, :tl, :tr, :bl, :br]
def new([x, y], points) do
tl = Enum.filter(points, fn [x1, y1] -> x1 < x && y1 > y end) |> MapSet.new()
tr = Enum.filter(points, fn [x1, y1] -> x1 > x && y1 > y end) |> MapSet.new()
bl = Enum.filter(points, fn [x1, y1] -> x1 < x && y1 < y end) |> MapSet.new()
br = Enum.filter(points, fn [x1, y1] -> x1 > x && y1 < y end) |> MapSet.new()
[_, y1] =
Enum.filter(points, fn [x1, y1] -> x1 == x && y1 != y end)
|> Enum.min_by(fn [_, y1] -> abs(y1 - y) end)
v1 = [0, y1 - y]
[x1, _] =
Enum.filter(points, fn [x1, y1] -> x1 != x && y1 == y end)
|> Enum.min_by(fn [x1, _] -> abs(x1 - x) end)
v2 = [x1 - x, 0]
%Point{v1: v1, v2: v2, x: x, y: y, tl: tl, tr: tr, br: br, bl: bl}
end
def assign_angles(points) do
index = points |> Enum.into(%{}, fn p -> {[p.x, p.y], p} end)
min_coords = index |> Map.keys() |> Enum.min()
min = index[min_coords] |> Map.put(:angle, :sharp)
index = index |> Map.put([min.x, min.y], min)
do_assign_angles(index, min, 0, :v1, :sharp)
end
def do_assign_angles(index, _, n, _, _) when map_size(index) == n, do: index |> Map.values()
def do_assign_angles(index, p, count, dir, kind) do
p1 = index[add(p, if(dir == :v1, do: p.v1, else: p.v2))]
new_kind =
if (dir == :v1 && scalar(p.v2, p1.v2) >= 0) || (dir == :v2 && scalar(p.v1, p1.v1) >= 0) do
kind
else
if kind == :sharp, do: :obtuse, else: :sharp
end
p1 = p1 |> Map.put(:angle, new_kind)
index = index |> Map.put([p1.x, p1.y], p1)
do_assign_angles(index, p1, count + 1, if(dir == :v1, do: :v2, else: :v1), new_kind)
end
def assign_sides(points) do
sides = sides(points)
points
|> Enum.map(fn p ->
top =
Enum.filter(sides, fn {[_, y1], [_, y2]} -> y1 == y2 && y1 > p.y end) |> MapSet.new()
bottom =
Enum.filter(sides, fn {[_, y1], [_, y2]} -> y1 == y2 && y1 < p.y end) |> MapSet.new()
left =
Enum.filter(sides, fn {[x1, _], [x2, _]} -> x1 == x2 && x1 < p.x end) |> MapSet.new()
right =
Enum.filter(sides, fn {[x1, _], [x2, _]} -> x1 == x2 && x1 > p.x end) |> MapSet.new()
%{p | left: left, right: right, top: top, bottom: bottom}
end)
end
def sides(points) do
points
|> Enum.flat_map(fn p -> [{[p.x, p.y], add(p, p.v1)}, {[p.x, p.y], add(p, p.v2)}] end)
|> Enum.map(fn
{[x, y1], [x, y2]} -> {[x, min(y1, y2)], [x, max(y1, y2)]}
{[x1, y], [x2, y]} -> {[min(x1, x2), y], [max(x1, x2), y]}
end)
|> Enum.uniq()
end
def add(%Point{x: x, y: y}, [x1, y1]), do: [x + x1, y + y1]
def area(%Point{x: x1, y: y1}, %Point{x: x2, y: y2}),
do: (abs(x1 - x2) + 1) * (abs(y1 - y2) + 1)
def allowed?(%Point{} = p1, %Point{} = p2) do
[p1, p2] = sort(p1, p2)
v12 = [p2.x - p1.x, p2.y - p1.y]
v21 = opposite(v12)
inside_vector?(p1, v12) && inside_vector?(p2, v21) && !intersections?(p1, p2) &&
no_vertexes_inside?(p1, p2)
end
def opposite([x, y]), do: [-x, -y]
def inside_vector?(%Point{angle: angle} = p, v) do
if angle == :sharp do
between_vectors?(p, v)
else
!between_vectors?(p, v)
end
end
def between_vectors?(%Point{v1: v1, v2: v2}, v) do
scalar(v1, v) >= 0 && scalar(v2, v) >= 0
end
def scalar([x1, y1], [x2, y2]), do: x1 * x2 + y1 * y2
def no_vertexes_inside?(p1, p2) do
if p1.y < p2.y do
MapSet.intersection(p1.tr, p2.bl) |> Enum.empty?()
else
MapSet.intersection(p1.br, p2.tl) |> Enum.empty?()
end
end
def intersections?(p1, p2) do
[p1, p2] = sort(p1, p2)
{horizontal, vertical} =
if p1.y < p2.y do
{MapSet.intersection(p1.top, p2.bottom), MapSet.intersection(p1.right, p2.left)}
else
{MapSet.intersection(p1.bottom, p2.top), MapSet.intersection(p1.right, p2.left)}
end
Enum.concat(horizontal, vertical)
|> Enum.any?(fn line -> intersects?(p1, p2, line) end)
end
def intersects?(%Point{x: x1, y: y1}, %Point{x: x2, y: y2}, {[x3, y], [x4, y]}) do
x = (x2 - x1) / (y2 - y1) * (y - y1) + x1
x3 < x && x < x4
end
def intersects?(%Point{x: x1, y: y1}, %Point{x: x2, y: y2}, {[x, y3], [x, y4]}) do
y = (y2 - y1) / (x2 - x1) * (x - x1) + y1
y3 < y && y < y4
end
def sort(p1, p2), do: Enum.sort_by([p1, p2], fn %Point{x: x, y: y} -> {x, y} end)
end
def part2(s) do
points = parse(s)
points =
points
|> Enum.map(fn p -> Point.new(p, points) end)
|> Point.assign_angles()
|> Point.assign_sides()
pairs(points)
|> Enum.map(fn {p1, p2} -> (Point.allowed?(p1, p2) && Point.area(p1, p2)) || 0 end)
|> Enum.max()
end
def pairs(enum) do
l = enum |> Enum.with_index()
for {a, i} <- l, {b, j} <- l, i < j, do: {a, b}
end
end
And then the edge case of exceeding lines, eg. if these two edges were in the same row
Want to keep every solution under a second if I can…
