Advent of Code 2025; Day 9: Movie Theater

· 4 min read

Finding the largest rectangle using known corners in a movie theater floor grid.

Part 1: Finding the Largest Rectangle

I’ve landed in an underground movie theater where the elves are redecorating the floor. The floor is a grid of tiles, some of which are red. The elves want to find the largest rectangle that uses two red tiles as opposite corners - doesn’t matter which two, as long as the resulting rectangle is as big as possible.

The input is simply a list of coordinates marking where the red tiles are located:

1
2
3
4
5
6
7
8

7,1
11,1
11,7
9,7
9,5
2,5
2,3
7,3

Data Structure

I created a basic Rect class to represent a rectangle defined by two opposite corners. From these two points I can easily determine the dimensions and area of the rectangle:

python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Rect:
    def __init__(self, a: tuple[int, int], b: tuple[int, int]) -> None:
        self.a = a
        self.b = b

    def width(self) -> int:
        return abs(self.b[0] - self.a[0]) + 1

    def height(self) -> int:
        return abs(self.b[1] - self.a[1]) + 1

    def area(self) -> int:
        return self.width() * self.height()

Using abs() means it doesn’t matter which point is “top-left” or “bottom-right” - the dimensions come out the same either way. The +1 accounts for the fact that a rectangle from (0,0) to (2,2) is actually 3 tiles wide, not 2.

Finding All Rectangles

The naive approach is straightforward: consider every possible pair of red tiles as opposite corners, calculate the area, and find the maximum. Parsing the input is simple enough with some splits and list comprehensions:

python
1
2
3
4
5
6
7
8

def load_tiles(input_data: str) -> list[tuple[int, int]]:
    return [
        (int(x), int(y))
        for x, y in [
            tile.split(",")
            for tile in input_data.strip().splitlines()
        ]
    ]

Then enumerate all pairs:

python
1
2
3
4
5

def find_rects(tiles: list[tuple[int, int]]):
    for a in tiles:
        for b in tiles:
            if a > b:
                yield Rect(a, b)

The a > b condition is an optimisation I touched on in Day 8’s improvements section - there’s no need to consider both Rect(a, b) and Rect(b, a) since they represent the same rectangle. By only yielding pairs where a > b, we’re taking the “upper triangle” of all possible pairings, halving our work. Sweet.

Putting It Together

python
1
2
3
4
5
6
7
8
9

def find_largest_rect(rects: Iterable[Rect]) -> Rect:
    return max(rects, key=lambda x: x.area())


def part1(input_data: str) -> int:
    tiles = load_tiles(input_data)
    rects = find_rects(tiles)
    r = find_largest_rect(rects)
    return r.area()

Python’s max() with a key function makes finding the largest rectangle quite elegant. This approach gets the answer fairly quickly - the input isn’t large enough that the pairwise comparison becomes a problem.

Part 2: Constrained by Colour

The Elves have kindly just informed me that they can only move red or green tiles, therefore the largest rectangle area must only include those tiles. The green tiles are defined by the connections between red tiles in the input list.

Every consecutive pair of red tiles in the input is connected by a straight line of green tiles (the list wraps, so the last tile connects back to the first). Additionally, all tiles inside this loop of red and green tiles are also green. Everything else is neither red nor green and cannot be part of our rectangle (green tiles (X) that connect the red tiles (#)):

1
2
3
4
5
6
7
8
9

..............
.......#XXX#..
.......XXXXX..
..#XXXX#XXXX..
..XXXXXXXXXX..
..#XXXXXX#XX..
.........XXX..
.........#X#..
..............

This is essentially a two-part problem:

  1. Trace the boundary: Walk between consecutive red tiles, marking all the green tiles along the edges. Since consecutive tiles in the input are always on the same row or column, this is just horizontal or vertical line segments.
  2. Fill the interior: Determine which tiles are inside the edges.

Once I know all the green tiles (edges + interior), for each rectangle determined in Part 1, I need to verify that every tile within their rectangle falls within the red or green areas.

To be continued when I have more time to think this through…

As always, code is available at github.com/lordmoocow/aoc25.

Although not a particularly complex problem, trying to complete this without looking up the answer can be the real challenge when you don’t deal with these kinds of issues day-to-day. I was able to intuit a solution to Part 1 quite easily but Part 2 met a knowledge gap that needed a bit more thought. 3 days to go - I’ll come back for part 2 when I have some spare time.