Advent of Code 2025 - Day 9 Solution

Problem Description

Given a simple polygon (non self-intersecting) in grid space, with each edge axis-aligned (parallel to either the x-axis or y-axis). Find the largest rectangle, defined by any two polygon vertices as opposite corners, that lies entirely within the polygon’s interior.

*(Left)* Problem input, the polygon vertex coordinates
*(Right)* Illustration of valid and invalid rectangles formed by choosing any two vertices as opposite corners

As shown above, the polygon is defined by a sequence of vertices (left figure). Choosing any two vertices as opposite corners yields many possible rectangles. In the right figure, the green rectangle lies entirely within the polygon, while the red rectangle is partially outside. Our task is to find the largest area rectangle among all valid ones.

Thought Process

Just Checking Key Points?

In Part One, we already implemented functionality to find all rectangles. Naturally, collision detection comes to mind. A simple approach would be to sample points inside the rectangle and check if they are inside the polygon. To check if a point is inside a shape, a classic method is the ray casting algorithm. The core idea is to cast a ray from the point in any direction and count intersections with the shape’s boundary; an odd count means the point is inside, even means outside. For example:

The ray casting algorithm efficiently tests if a point is inside an arbitrary shape

Why not enumerate all grid points?

Even for a regular, grid-aligned polygon like in this problem, we cannot practically check every single grid point inside the rectangle for being inside the polygon. The shape’s size is unknown and could be very large, causing the number of points to check to grow rapidly, severely impacting performance.

Thus, a natural thought arises: perhaps we only need to check a few key points of the rectangle? Like its four corners, or the corners plus the center? However, this approach is insufficient for this problem. A counterexample easily arises:

Checking the rectangle center and its four corners is insufficient to guarantee the entire rectangle’s validity

In the left rectangle above, the center and all four corners are inside the polygon, yet parts of the rectangle’s edges extend outside the polygon’s boundary. In fact, arbitrarily adding more key points, like edge midpoints, still cannot guarantee the rectangle’s validity because there could still be parts of the rectangle outside the polygon. Therefore, checking a fixed set of key points cannot ensure the entire rectangle’s validity.

Enumerating Intersections with All Edges

Although not explicitly stated, the polygon is non self-intersecting (the left case in the figure below). This implies a property: the polygon’s “exterior” is connected. More formally:

The polygon partitions the 2D plane into “interior” (valid region) and “exterior” (invalid region). Let $\mathcal{S}$ be the set of all points exterior to the polygon. $\mathcal{S}$ is connected if and only if for any two points $\forall A, B \in \mathcal{S}$ , there exists a path $\exists P \subset \mathcal{S}$ such that the starting point $P_0$ is $A$ and the ending point $P_n$ is $B$ . Intuitively, this means the polygon does not create isolated enclosures, as shown on the left below.

*(Left)* Self-intersection makes the exterior disconnected
*(Right)* Property of rectangle boundaries derivable from connectivity

Therefore, if any part of a rectangle lies outside the polygon, then due to connectivity, there must exist a path, with every point on it outside the polygon, starting from some point $A$ inside the rectangle and ending at some necessarily existing point $B$ outside the rectangle, as shown on the right above. This path connects the interior and exterior of the rectangle. By simple topology, it must intersect the rectangle’s boundary at some point. That is, at least one point on one of the rectangle’s edges lies outside the polygon.

Based on this, we could instead try to enumerate all points on the rectangle’s edges and check if any are outside the polygon to determine if the rectangle is partially outside.

Performance Consideration

This method improves efficiency significantly compared to checking every grid point, reducing complexity from $O(mn)$ to $O(m+n)$ , where $m$ and $n$ are the rectangle’s width and height. However, for this problem, the rectangle could still be very large, leading to too many points to check and severely impacting performance. Thus, we need to find a more efficient solution.

A Step Back

To further improve algorithm efficiency, let’s try a different perspective: what are the fundamental conditions that make a rectangle invalid? We can identify the following scenarios:

*(Left)* **Fully inside**: valid
*(Middle)* **Partially inside**: invalid
*(Right)* **Fully outside**: invalid

It’s easy to see that the vast majority of invalid cases are caused by the “partially inside” scenario (middle), while the “fully outside” case can be handled separately later. For the “partially inside” case, we can observe that one edge of the rectangle must intersect an edge of the polygon. More strictly, if a rectangle’s edge intersects a polygon edge perpendicular to it, and the intersection point is not at a vertex of either the rectangle or the polygon, then the rectangle must be partially outside the polygon. A less formal but intuitive proof is that each polygon edge divides space into interior (valid) and exterior (invalid). When a polygon edge “pierces” the rectangle, the rectangle necessarily straddles the valid/invalid regions defined by that edge, meaning part of it is outside, as illustrated below:

When “pierced” by a polygon edge, the rectangle must span both valid and invalid regions

Is this enough? Don’t we still have the “fully outside” case? Actually, for this specific problem input, we don’t need to handle it separately. We can observe that the input polygon resembles a circle with a thin rectangle subtracted from it (see figure below). Therefore, the largest possible “fully outside” rectangle would be this thin rectangle itself, whose area is obviously smaller than the area of the largest valid rectangle we can find. So, we only need to focus on the “partially inside” case.

The actual input polygon shape resembles a circle with a rectangle carved out

Handling Rectangles Fully Outside the Polygon

In general, there might be cases where a “fully outside” rectangle’s area is larger than any valid rectangle’s area. Then we would need to handle this case.

In fact, this only requires an additional check: test if the rectangle’s center point is inside the polygon, because if a rectangle is fully outside the polygon, its center must also be outside. We can use the ray casting algorithm mentioned earlier for this check. The rest of the logic remains the same.

Based on the above analysis, we can design the following algorithm:

Enumerate all rectangles formed by any two vertices.
For each rectangle, enumerate its four edges.
For each rectangle edge, enumerate all perpendicular polygon edges. Check if they intersect, and the intersection point is not at a vertex of either shape (the piercing condition).
If such an intersection exists, the rectangle is invalid; skip it.
Otherwise, the rectangle is valid. Calculate its area and update the maximum area.

Determining Piercing

Here we omit the detailed explanation of the piercing condition and why we don’t need to consider intersections at vertices. This is left as an exercise for the reader. Hint: consider two cases separately: intersection at a rectangle vertex and intersection at a polygon vertex.

With this, our algorithm’s complexity no longer depends on the shape’s size, but only on the number of polygon vertices, greatly improving efficiency.

Core Algorithm Implementation

1
struct Puzzle {
2
    nodes: Array2<i64>,
3
}
4

5
type Edge = (usize, usize);
6

7
impl Puzzle {
8
    fn measure(&self, i: usize, j: usize) -> u64 {
9
        (&self.nodes.row(i) - &self.nodes.row(j))
10
            .mapv(|v| v.unsigned_abs() + 1)
11
            .product()
12
    }
13

14
    fn get_edges(&self) -> (Vec<Edge>, Vec<Edge>) {
15
        let n = self.nodes.nrows();
16
        (0..n)
17
            .into_par_iter()
18
            .map(|i| (i, (i + 1) % n))
19
            .partition(|&(i, j)| self.nodes[[i, 0]] == self.nodes[[j, 0]])
20
    }
21

22
    fn intersect_edge(
23
        &self,
24
        xs: (i64, i64),
25
        ys: (i64, i64),
26
        edges: &[Edge],
27
        transpose: bool,
28
    ) -> bool {
29
        let (x1, x2) = xs;
30
        let (x1, x2) = (x1.min(x2), x1.max(x2));
31
        let (y1, y2) = ys;
32
        let (y1, y2) = (y1.min(y2), y1.max(y2));
33

34
        edges.into_par_iter().any(|&(i, j)| {
35
            let i = self.nodes.row(i);
36
            let j = self.nodes.row(j);
37
            let (ex1, ex2, ey) = if transpose {
38
                (i[1].min(j[1]), i[1].max(j[1]), j[0])
39
            } else {
40
                (i[0].min(j[0]), i[0].max(j[0]), i[1])
41
            };
42

43
            ey > y1 && ey < y2 && ex1 < x2 && ex2 > x1
44
        })
45
    }
46
}
47

48
impl Solution for Puzzle {
49
    fn part2(&self) -> String {
50
        let (vertical_edges, horizontal_edges) = self.get_edges();
51

52
        (0..self.nodes.nrows())
53
            .into_par_iter()
54
            .flat_map_iter(|i| {
55
                (i + 1..self.nodes.nrows())
56
                    .map(|j| (i, j))
57
                    .collect::<Vec<_>>()
58
            })
59
            .filter_map(|(i, j)| {
60
                let (px1, py1) = (self.nodes[[i, 0]], self.nodes[[j, 1]]);
61
                let (px2, py2) = (self.nodes[[j, 0]], self.nodes[[i, 1]]);
62

63
                if !self.intersect_edge((px1, px2), (py1, py2), &horizontal_edges, false)
64
                    && !self.intersect_edge((py1, py2), (px1, px2), &vertical_edges, true)
65
                {
66
                    Some(self.measure(i, j))
67
                } else {
68
                    None
69
                }
70
            })
71
            .max()
72
            .unwrap_or_else(|| unreachable!("Must have at least one pair of nodes"))
73
            .to_string()
74
    }
75
}

Summary

The complete code can be found here.

Although the problem itself is not overly complex, by re-examining and analyzing the problem, we found a more elegant and efficient solution. This highlights the importance of understanding a problem’s essence in algorithm design.