Advent of Code 2025 Day 12

Day 12: Christmas Tree Farm

https://adventofcode.com/2025/day/12

The elves are worried they won’t be able to fit all presents under their respective trees.

The input for today has 2 parts:

The shapes of the possible presents
Information about the tree regions

The information about the trees also has 2 parts:

The dimensions of the available area in width x length
The amount of presents of each shape that the elves want to put underneath that tree.

An example input looks like this:

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

Parsing

I parse the shapes into a list of 2D lists where # is true and . is false. The index in front of each package, I ignored because it’s the same as that shape’s index in the list anyway.

The tree regions get their own data structure to keep things tidy.

struct Region {
    width: u32,
    length: u32,
    counts: Vec<u32>,
}

fn parse(input: &str) -> (Vec<Vec<Vec<bool>>>, Vec<Region>) {
    let (shapes_str, regions_str) = input.rsplit_once("\n\n").unwrap();

    let shapes = shapes_str
        .split("\n\n")
        .map(|block| {
            block
                .lines()
                .skip(1)
                .map(|line| line.chars().map(|c| c == '#').collect())
                .collect()
        })
        .collect();

    let regions = regions_str
        .lines()
        .map(|line| {
            let (tree, counts) = line.split_once(": ").unwrap();
            let (width, length) = tree.split_once("x").unwrap();
            Region {
                width: width.parse().unwrap(),
                length: length.parse().unwrap(),
                counts: counts.split(" ").map(|s| s.parse().unwrap()).collect(),
            }
        })
        .collect();

    (shapes, regions)
}

Part 1

The question asks how many regions can fit all of their presents.

Initially, I looked for help solving this, because it’s a packing problem and those are NP-hard (fancy math speak for “no fast solution exists”). I even found a public PhD defence on this topic. Having one of those exist for todays problem doesn’t bode well.

Turns out the author was kind and this problem can be drastically simplified.

Every present is shown in a 3x3 grid
Regions are either too small or big enough with a huge margin (meaning no rotation or flipping is needed)

I made a helper function that determines if the area under a tree can definitely hold the amount of presents assigned to it. I treat all presents as a filled 3x3 square and see if they fit if that were the case.

That’s enough, all other regions are way too small!

// assume all presents are 3x3
const BLOCK_SIZE: u32 = 3;

impl Region {
    fn definitely_fits(&self) -> bool {
        let blocks_free = (self.width / BLOCK_SIZE) * (self.length / BLOCK_SIZE);
        let blocks_to_place = self.counts.iter().sum();
        blocks_free >= blocks_to_place
    }
}

fn part_1(input: &str) -> usize {
    let (_, regions) = parse(input);
    regions.into_iter().filter(Region::definitely_fits).count()
}

Part 2

The hardest button to button!

Final code

1
// assume all presents are 3x3
2
const BLOCK_SIZE: u32 = 3;
3

4
struct Region {
5
    width: u32,
6
    length: u32,
7
    counts: Vec<u32>,
8
}
9

10
impl Region {
11
    fn definitely_fits(&self) -> bool {
12
        let blocks_free = (self.width / BLOCK_SIZE) * (self.length / BLOCK_SIZE);
13
        let blocks_to_place = self.counts.iter().sum();
14
        blocks_free >= blocks_to_place
15
    }
16
}
17

18
fn parse(input: &str) -> (Vec<Vec<Vec<bool>>>, Vec<Region>) {
19
    let (shapes_str, regions_str) = input.rsplit_once("\n\n").unwrap();
20

21
    let shapes = shapes_str
22
        .split("\n\n")
23
        .map(|block| {
24
            block
25
                .lines()
26
                .skip(1)
27
                .map(|line| line.chars().map(|c| c == '#').collect())
28
                .collect()
29
        })
30
        .collect();
31

32
    let regions = regions_str
33
        .lines()
34
        .map(|line| {
35
            let (tree, counts) = line.split_once(": ").unwrap();
36
            let (width, length) = tree.split_once("x").unwrap();
37
            Region {
38
                width: width.parse().unwrap(),
39
                length: length.parse().unwrap(),
40
                counts: counts.split(" ").map(|s| s.parse().unwrap()).collect(),
41
            }
42
        })
43
        .collect();
44

45
    (shapes, regions)
46
}
47

48
fn part_1(input: &str) -> usize {
49
    let (_, regions) = parse(input);
50
    regions.into_iter().filter(Region::definitely_fits).count()
51
}

Date

Tagged

Part of series

Newer post