Advent of Code 2025; Day 12: Christmas Tree Farm

Part 1: Presents Under the Trees

I’m running a couple of days behind on this one, but the Christmas tree farm waits for no one. After tumbling through a ventilation duct - because apparently that’s how we navigate the North Pole now - I’ve landed in a cavern full of Christmas trees and panicking elves.

Their problem? Presents. Specifically, oddly-shaped presents that need to fit into the regions beneath each tree. It’s like Tetris, except the pieces are weird, there’s no gravity, and instead of clearing lines you’re just trying not to disappoint young elves on Christmas morning. No pressure.

The input comes in two parts: first, a catalogue of present shapes, then a list of tree regions with the presents that need to fit in each:

 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
33

0:
###
##.
##.

1:
###
##.
.##

2:
.##
###
##.

3:
##.
###
##.

4:
###
#..
###

5:
###
.#.
###

4x4: 0 0 0 0 2 0
12x5: 1 0 1 0 2 2
12x5: 1 0 1 0 3 2

That 4x4: 0 0 0 0 2 0 means “here’s a 4-by-4 region, and you need to fit zero of shape 0, zero of shape 1, zero of shape 2, zero of shape 3, two of shape 4, and zero of shape 5.” The presents can be rotated and flipped, and while the # parts can’t overlap, the . parts are just empty space in the shape’s bounding box - other presents can happily occupy those cells.

Parsing the Input

I’m using numpy here, it provides multi-dimensional arrays with convenient rotation and flip operations, which is nothing too crazy but not something I want to implement myself for this challenge (it’s probably a lot more efficient than what I would throw together too). The parsing once again is a load of list comprehension gymnastics, but it gets the job done:

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

def load_presents(input_data: str) -> tuple[list[np.ndarray], list[tuple[np.ndarray, list[int]]]]:
    parts = input_data.split("\n\n")
    presents = [
        np.array([list(row) for row in shape[3:].splitlines()]) == "#"
        for shape in parts[:-1]
    ]
    trees = [
        (np.zeros((int(a), int(b)), bool), list(map(int, p.split())))
        for (a, _, b), p in [
            (dimensions.partition("x"), p)
            for dimensions, _, p in [
                tree.partition(": ")
                for tree in parts[-1].splitlines()
            ]
        ]
    ]
    return (presents, trees)

This gives me a list of boolean numpy arrays representing each present shape (True where there’s a #), and a list of tuples containing an empty area (as a boolean array of the right dimensions) plus the count of each shape type needed.

Orientations: Flip and Rotate

Before diving into the fitting algorithm, I need to think about all the ways a present can be oriented. Each shape can be flipped horizontally, and each flip can be rotated 0, 90, 180, or 270 degrees. That’s potentially 8 orientations per present - but some shapes have symmetries that make certain orientations identical.

1
2
3
4
5
6
7
8

def flip_rotate(present: np.ndarray) -> list[np.ndarray]:
    orientations = []
    for flip in [present, np.fliplr(present)]:
        for r in range(4):
            rot = np.rot90(flip, r)
            if not any(np.array_equal(rot, o) for o in orientations):
                orientations.append(rot)
    return orientations

The deduplication here is a small win in what I think will be a slog of a computation - no point exploring the same orientation twice. A square-ish symmetrical shape might only have 1 or 2 unique orientations, while an L-shaped piece might have all 8. Every reduction is a win.

Finding Valid Placements

Where can a present actually go? Given an area (which might already have some presents placed in it), I need to find all positions where a given present orientation fits without overlapping anything.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def placements(area: np.ndarray, present: np.ndarray):
    for x in range(np.size(area, 1) - present.shape[1] + 1):
        for y in range(np.size(area, 0) - present.shape[0] + 1):
            # check for overlaps
            placement = area[y:y+present.shape[0], x:x+present.shape[1]]
            if not (placement & present).any():
                # create a new area including the newly placed present
                a = area.copy()
                a[y:y+present.shape[0], x:x+present.shape[1]] |= present
                yield a

The overlap check is rather elegant thanks to numpy’s boolean operations. If I slice out the region where the present would go and bitwise-AND it with the present shape, any True values indicate a collision. If the result is all False, the placement is valid.

 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

Given this area with a            And this present
present already placed:           we want to place:
┌─────────┐                       ┌───────┐
│ . . # # │                       │ # # . │
│ . . # # │                       │ # # # │
│ . . . . │                       │ . # . │
│ . . . . │                       └───────┘
└─────────┘

Attempt 1: Place at position (1, 0)
─────────────────────────────────────────────────────────────────
Slice area[0:3, 1:4]:    AND with present:       Result:

┌───────┐                ┌───────┐               ┌───────┐
│ . # # │                │ # # . │               │ . # . │
│ . # # │       &        │ # # # │       =       │ . # # │
│ . . . │                │ . # . │               │ . . . │
└───────┘                └───────┘               └───────┘

Result contains # → Collision! Skip this placement.

Attempt 2: Place at position (0, 1)
─────────────────────────────────────────────────────────────────
Slice area[1:4, 0:3]:    AND with present:       Result:

┌───────┐                ┌───────┐               ┌───────┐
│ . . # │                │ # # . │               │ . . . │
│ . . . │       &        │ # # # │        =      │ . . . │
│ . . . │                │ . # . │               │ . . . │
└───────┘                └───────┘               └───────┘

Result is all empty → Valid placement! Yield the new area.

The generator yields new areas with the present “placed” (bitwise-OR’d into the array). The area is copied to ensure that different branches of the search get independent instances of state without interference.

The Recursive Fit

The algorithm is conceptually simple: pick a present from the pile, try every valid placement in every valid orientation, and recursively attempt to fit the remaining presents. If we ever empty the pile, success! If we exhaust all options, backtrack.

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

def try_fit(area: np.ndarray, presents: list[np.ndarray]) -> bool:
    # if there are no remaining presents then we must have fit everything in
    if not presents:
        return True

    # if there isn't enough space remaining don't bother checking further
    required_area = sum(np.count_nonzero(p) for p in presents)
    remaining_space = np.size(area) - np.count_nonzero(area)
    if required_area > remaining_space:
        return False

    # take a present from the pile to test with
    present = presents[0]
    remaining_presents = presents[1:]

    # in each orientation
    for orientation in flip_rotate(present):
        # each position
        for new_area in placements(area, orientation):
            # try remaining presents in remaining area
            if try_fit(new_area, remaining_presents):
                return True
    return False

There’s a nice early termination check in there - if the total area of remaining presents exceeds the remaining empty space, there’s no point continuing down that branch. It’s not going to magically fit.

The search is depth-first, and crucially it returns True as soon as it finds any valid arrangement. I don’t need the optimal packing, I don’t need all solutions - just confirmation that one exists.

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

def part1(input_data: str) -> int:
    presents, trees = load_presents(input_data)
    count = 0
    for area, pcount in trees:
        tofit = [
            presents[i]
            for i, n in enumerate(pcount)
            for _ in range(n)
            if n > 0
        ]

        if try_fit(area, tofit):
            print(f"{len(area)}x{len(area[0])}: fits")
            count += 1
        else:
            print(f"{len(area)}x{len(area[0])}: doesn't fit")

    return count

That nested list comprehension expands the count list into actual present shapes - if we need three of shape 4, we get three copies of that shape in our tofit list.

Performance Thoughts

I’ll be honest: this runs for about 1.5 minutes on my machine. That’s… not fast. But it does finish, which counts for something! The explosion of trying every present in every orientation at every position is quite heavy.

There’s probably room for improvement here. I was thinking of caching combinations of presents that are known to fit into a given area, effectively building “composite” shapes out of the presents. I could also potentially prune earlier by identifying isolated regions that can’t possibly fit any remaining presents. But at 1.5 minutes, it was done before I finished thinking about optimisations let alone implement them.

Sometimes the best optimisation is just… seeing if it’s even necessary!

Part 2: To Be Continued

Part 2 remains unsolved for now. It appears to suggest I have 2 remaining stars to collect before I can access this one, I assume the two days I have yet to complete Part 2. Will revisit this if it unlocks once I get around to those.

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

Day 12 stumped me a first but I got a solution to Part 1 with a bit of force, not sure if that will stand up for the next part. Part 2 awaits once I figureo out the rest.