“You slide down the firepole in the corner of the playground and land in the North Pole base movie theater!”

Github: GCaggianese/AoC-2025/D9

• Gambit Scheme

Puzzle Day 9: Movie Theater

Part One

Find the largest rectangle using any two “red tiles” (input coordinates) as opposite corners.

• Input: List of coordinates $(x, y)$.
• Metric: Area includes the boundary tiles. \(Area = (|x_1 - x_2| + 1) \times (|y_1 - y_2| + 1)\)
• Algorithm: Brute-force $O(N^2)$ comparison of all pairs.

Part Two

The red tiles form a sequential path (loop) connected by “green tiles” (rectilinear segments). The valid rectangle must be formed entirely by tiles inside or on the boundary of this polygon.

Constraints

For a rectangle defined by corners $P_i, P_j$ to be valid:

1. Corners: All 4 corners must be inside or on the polygon boundary.
2. Edges: No polygon segment may cross through the interior of the rectangle.

Algorithm

1. Polygon Construction: Connect input points sequentially $P_0 \to P_1 \to \dots \to P_n \to P_0$.
2. Ray Casting: Use the even-odd rule to determine if a point is inside the polygon.
   • Correction: Points exactly on horizontal/vertical segments are valid (Green).
3. Validation: Iterate all pairs $(P_i, P_j)$. If the area is greater than the current max, validate geometric constraints.

Manual Analysis

Verification of vector distances and area for sample points

Distance Checks:

Area Calculation: For the rectangle defined by $\vec{V}_1$ and $\vec{V}_3$:

Polygon Trace

The input points form a rectilinear loop. Visualizing the connectivity:

(0,0) . . . . . . . . .
. . . . . . . . . . . .
. . P5----------P4. . .
. . | . . . . . | . . .
. . P6. . . . . P3. . .
. . | . . . . . | . . .
. . P7----------P2. . .
. . . . . . . . | . . .
. . . . . . . . P1--P0.

Implementation in Gambit Scheme

make && ./build/d9