Advent of Code 2025 - Day 9: Movie Theater

Day 9 was about finding the largest rectangle between red tiles on a theater floor. Part 1 was straightforward geometry. Part 2 required checking if rectangles fit inside a polygon - which is where I reached for an external library.

Part 1: Largest Rectangle Between Any Two Points

Given coordinates of red tiles, find the largest rectangle using any two red tiles as opposite corners.

This is pure geometry: for every pair of points, calculate the rectangle area and track the maximum.

Improving the Helper Library

First, I updated my loadFile() helper to handle CSV splitting:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def loadFile(input_f, s: str = None):
    """
    Loads a file and returns its lines as a list.
    
    Args:
        input_f (str): The file path to read from.
        s (str, optional): Delimiter to split lines by. Defaults to None.
    
    Returns:
        list: A list of lines from the file, optionally split by delimiter.
    """
    lines = []
    try:
        with open(input_f) as file:
            for line in file:
                if s == None:
                    lines.append(line.rstrip())
                else:
                    lines.append(line.rstrip().split(s))
    except FileNotFoundError:
        raise FileNotFoundError(f"The file '{input_f}' was not found.")
    except IOError as e:
        raise IOError(f"Error reading file '{input_f}': {e}")
    return lines

This lets me do loadFile(input_f, ',') to get CSV data directly, without breaking existing code.

The Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def area(cords1, cords2):
    width = abs(cords1[0] - cords2[0]) + 1
    height = abs(cords1[1] - cords2[1]) + 1
    return width * height

def part1():
    score = 0
    lines = loadFile(input_f, ',')
    heap = []
    
    for i in range(len(lines)):
        for j in range(i + 1, len(lines)):
            cords1 = tuple(list2int(lines[i]))
            cords2 = tuple(list2int(lines[j]))
            a = area(cords1, cords2)
            heapq.heappush(heap, (a, cords1, cords2))  # Save for part 2
            if a > score:
                score = a
    
    return score, heap

Rectangle area formula: (|x1 - x2| + 1) × (|y1 - y2| + 1). The +1 is because coordinates are inclusive - a rectangle from (2,3) to (5,7) spans 4 units in x and 5 units in y.

Double loop checks every pair. Track the maximum area as we go.

First try!

Part 2: Rectangle Must Fit Inside Polygon

Part 2 reveals that the red tiles form a loop connected by green tiles, and the rectangle can only include red or green tiles. Essentially: find the largest rectangle (with red corners) that fits entirely inside the polygon formed by the red tiles.

The Day of Scribbling

I spent most of my breaks today, scribbling ideas. I thought about AABB (Axis-Aligned Bounding Box) collision detection from game development, but it didn’t quite fit. I kept checking Reddit for visualizations but nothing clicked.

Then I remembered: this is exactly what I did for 2023 Day 18: Lavaduct Lagoon. Use Shapely.

Enter Shapely

Shapely is a Python library for geometric operations. It can create polygons, check containment, calculate intersections, etc.

I normally avoid external libraries for Advent of Code, but sometimes the right tool is the right tool.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def part2(heap): 
    from shapely.geometry import Polygon, box
    
    lines = loadFile(input_f, ',')
    
    # Convert to tuples for Shapely
    for l in range(len(lines)):
        lines[l] = tuple(list2int(lines[l]))
    
    # Create polygon from red tile coordinates
    shape = Polygon(lines)
    
    # Convert min-heap to max-heap (largest first)
    heapq._heapify_max(heap)
    
    score = 0
    
    # Check rectangles from largest to smallest
    while heap:
        area, cords1, cords2 = heapq._heappop_max(heap)
        x1, y1 = cords1
        x2, y2 = cords2
        
        # Create rectangle
        rect = box(min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2))
        
        # Check if rectangle fits inside polygon
        if shape.contains(rect):
            score = area
            break
    
    return score

The algorithm:

1. Create a Polygon from the red tile coordinates
2. Convert the heap to a max-heap (Python’s heapq is min-heap by default)
3. Pop rectangles from largest to smallest
4. For each rectangle, create a box geometry
5. Check if shape.contains(rect)
6. First match is the answer (since we’re going largest-to-smallest)

The key insight: we don’t need to figure out which rectangles fit - Shapely does that for us. Polygon.contains() handles all the geometric edge cases.

First try. Using the right library made this almost trivial.

The Right Tool for the Job

I could have implemented point-in-polygon checking manually. I could have written ray-casting algorithms or winding number calculations.

Sometimes “using external libraries feels like cheating” is perfectionism getting in the way of solving the problem. Advent of Code isn’t about reinventing geometry libraries - it’s about problem-solving and recognizing patterns.

I used Shapely in 2023 Day 18, and I’ll probably use it again next time a polygon problem shows up.

Performance Note

Part 1 generates all possible rectangles and saves them to a heap. For large inputs, this is O(n²) space. If memory were a concern, we could check containment on-the-fly in Part 1 instead of building the heap.

But for Advent of Code input sizes, the heap approach works fine and makes the code cleaner.

Eighteen stars total. Sometimes the hardest part isn’t the algorithm - it’s recognizing that you’ve solved this problem before.