Advent of Code 2025 - Day 12Christmas Tree Farm

| Problem statement | Source code | Tags: Puzzle

An all-time classic:

Let's see what the pointless thing is.

First, regarding parsing the input. The regions are fairly straightforwardly Vec<(usize, usize, Vec<usize>)>. For the shapes, since they can be freely rotated and flipped, I decided to precompute all rotations and flips of each shape, as a struct:

struct Shape {
    cells: Vec<(usize, usize)>,
    block_id: usize,
}

Now we need to test if we can pack said shapes into the regions. First, there are two obvious bounds: since each shape is is bounded by a 3x3 square, if we treat them as 3x3 blocks, and the region is still able to fit them, then we can pack them.

let definitely_fits = (width / 3) * (height / 3) >= counts.iter().sum::<usize>();

Conversely, if the region's total area is less than the total area of the shapes, then it definitely doesn't fit, no matter how nicely we can pack them.

let shape_area = counts
    .iter()
    .enumerate()
    .map(|(i, &x)| x * shapes.iter().find(|s| s.block_id == i).unwrap().cells.len())
    .sum::<usize>();
let definitely_not_fit = width * height < shape_area;

For the remaining cases, I implemented a backtracking search. I picture it as a game of Tetris: the shapes are dropped one by one, each time it can be dropped along any column, but it has to be dropped as far as possible. If at any point the shape cannot be dropped, we backtrack and try a different column or a different shape.

But... but... *gasps* It turns out that this case doesn't exist!! Every region is either definitely_fits or definitely_not_fit. So this hugely expensive search function is never called.

Anyway, I'm extremely underwhelmed by this meme problem on the last day. I get that problems are usually easy on the last day, but it used to be Christmas day when everyone was busy, and now it's just the 12th and everyone's supposed to be having fun. I was amused but also bummed.