Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Packing Presents

Advent of Code 2025 - Day 12

Day 12: Packing Presents

Useful Links

‹

Concepts and Packages Demonstrated

NumPyHeuristics

Problem Intro

It’s time to organise presents under trees! We are given a set of unique present shapes and a list of rectangular regions (spaces under trees). For each region, we are given a requirement of how many of each present type must be packed into it.

The presents are tetris-like shapes made of #. They can be rotated and flipped. They must be packed into the region such that:

Example input:

The shapes are defined first:

0:
###
##.
##.

1:
###
##.
.##

Followed by region requirements:

12x5: 1 0 1 0 2 2

This line means a 12x5 region requires:

Part 1

How many of the listed regions can successfully fit all the required presents?

Solution Approach

This problem initially smelled like a classic Backtracking / Recursive DFS problem. My initial thinking was that I’d need to:

  1. Generate all unique configurations (rotations/flips) for each shape.
  2. Try to place the first shape in the first available top-left spot.
  3. Recurse for the next shape. Return True when we find a viable configuration.
  4. Backtrack if we get stuck and recurse again.

This means that for impossible configurations, we will try every possible configuration and return False. That can take a long time, and indicates that this is a NP-complete problem.

In plain English, NP-complete is computer science speak for “computational nightmare”. It describes a class of problems where verifying a solution is trivial (e.g. checking if a specific arrangement of presents fits is instant), but finding that solution from scratch is incredibly hard because there are no known efficient algorithms to do it.

Essentially, as the problem gets bigger (more presents, larger grids), the time required to solve it explodes exponentially. What takes milliseconds for a handful of presents might take years for a few dozen.

That’s why spotting a clever heuristic is often the only way to finish before next Christmas! Think of a heuristic as a “rule of thumb” or a smart shortcut that trades guaranteed perfection for practical speed.

For this specific problem, it turns out that there’s a heuristic that greatly simplifies finding the solution. This is both fortunate and unfortunate, depending on your perspective.

The Heuristic Shortcuts

Instead of brute-forcing every single possibility (which might take until the heat death of the universe), we can use logical deductions to quickly identify:

  1. Solutions that are obviously impossible
  2. Solutions that are obviously possible

With any luck this will rule out most regions, so we only need to do heavy processing on the remaining ones.

Let’s get into how to do this…

Here are how we split the regions/requirements into categories:

  1. Obviously Too Small: If the total number of present units (the # counts) exceeds the total area of the region, then it’s impossible to fit the required number of presents.
  2. Obviously Big Enough: I note that the shapes of the sample data and input data all fit into a grid of size 3x3. If we simplify by assuming that every present is a full 3x3 box (9 units) and then just tile them, then would they fit in the given region? If the region is bigger than 9 * num_presents, it’s guaranteed to fit because every shape fits inside a 3x3 square.
  3. The “Maybe” Zone: Anything in between. This is where we’d normally assume we have to run the expensive solver.

Parsing Code

First, we parse the shapes into NumPy arrays. Why use NumPy? Because:

def parse_input(data:str) -> tuple[list[np.ndarray], list[Region]]:
    """ Parse the input data into shapes and regions """
    blocks = data.strip().split("\n\n")
    shape_blocks = blocks[:-1]
    region_block = blocks[-1]

    shapes = [] # Store in order so we can easily index
    for block in shape_blocks:
        shape_lines = block.splitlines()[1:]
        grid = [[1 if char == '#' else 0 for char in line] for line in shape_lines]
        shape_array = np.array(grid, dtype=np.bool)
        shapes.append(shape_array)

Next, we parse the regions and their associated present requirements.

    regions = []
    for line in region_block.splitlines():
        width, height, *present_counts = list(map(int, re.findall(r"\d+", line)))
        region = Region(width, height, present_counts)
        regions.append(region)

I’m using regex to extract all the numbers from this line. The re.findall function returns a list of all matches, which we then convert to integers.

Each region is stored in our custom Region class, which stores the width, height, and present counts.

@dataclass
class Region:
    width: int
    height: int
    present_counts: list[int] # E.g. [1, 0, 1, 0, 2, 2]

Heuristic Code

Now we can go ahead and check conditions #1 and #2.

    regions_satisfied = 0
    for region in regions:
        region_size = region.width * region.height
        total_shapes_required = sum(region.present_counts)

        # "Safe" area: If every shape took up its full 3x3 bounding box (9 tiles)
        tiled_shape_area = total_shapes_required * 9
        
        # "Actual" area: The sum of the literal '#' pixels in the shapes
        actual_shape_units = 0
        for shapes_count_req, shape in zip(region.present_counts, shapes):
            actual_shape_units += shapes_count_req * shape.sum()

        if actual_shape_units > region_size:
            # Physically impossible: more present pixels than floor pixels
            continue
        elif region_size >= tiled_shape_area: 
            # Guaranteed to fit: Even efficiently tiling 3x3 boxes fits
            regions_satisfied += 1

The Observation

When analyzing the actual puzzle input, I noticed something interesting.

Here’s an extract of some logging from my actual data:

Region area: 1640, Min: 1091 (1.503), Sure: 1521           
Region area: 1813, Min: 1816 (0.998), Sure: 2502           
Region area: 1400, Min: 1403 (0.998), Sure: 1944           
Region area: 1512, Min: 1079 (1.401), Sure: 1503           
Region area: 2352, Min: 1658 (1.419), Sure: 2295           
Region area: 1540, Min: 1002 (1.537), Sure: 1386           
Region area: 1681, Min: 1096 (1.534), Sure: 1512           
Region area: 2112, Min: 2113 (1.000), Sure: 2934           
Region area: 1596, Min: 1084 (1.472), Sure: 1503

Here the numbers are:

Why is the output interesting? Well, it turns out that all the regions align to one of these cases:

There were no cases in between!

So, when we run this code for the real input, we have solved for ALL region requirements in our input data!

Why This is Slightly Annoying

This solution works perfectly for my real input data, because all the regions align to one of the two cases above.

But with the sample data, I get this output:

DEBUG    14:10:39.115 Region area: 16, Min: 14 (1.143)                             
DEBUG    14:10:39.115 Region area: 60, Min: 42 (1.429)                             
DEBUG    14:10:39.116 Region area: 60, Min: 49 (1.224)

This is frustrating because region #2 is clearly big enough, but the other two are both in the “maybe” region. So my simple heuristic works for the real data, but not for the sample data. In short: the sample data is not a good test case for this problem.

You can spend ages trying to make the code work with the sample data, only to find that you’ve wasted your time. In fact, this is the only AoC puzzle I’ve ever tackled where I’ve proceeded to the real input data without getting the code working with the sample data. And I really don’t like that!

Conclusions

Sometimes, heuristics beat general algorithms. And sometimes, looking at your data saves you from implementing a recursive backtracking solver!

‹