C++

Hah, got me good too Mr Wastl. Was wondering how long this could possibly take to run - the worst-case is very bad indeed. This prints out the first “fit” it finds, for verification purposes, and keeps the successful ones in case they’re needed for “part 2”.

Merry Xmas, everyone.

#include <boost/describe.hpp>
#include <boost/describe/operators.hpp>
#include <boost/log/trivial.hpp>
#include <boost/unordered/unordered_flat_set.hpp>
#include <fstream>
#include <iostream>
#include <ostream>
#include <sstream>
#include <string>
#include <vector>

namespace {

struct Point {
  int x, y;
};
BOOST_DESCRIBE_STRUCT(Point, (), (x, y))
using boost::describe::operators::operator==;

using Present = boost::unordered::unordered_flat_set<Point>;
using PresentList = std::vector<size_t>;

struct Tree {
  int width;
  int height;
  PresentList presents;
};
auto operator<<(std::ostream &o, const Tree &t) -> std::ostream & {
  o << t.width << 'x' << t.height << ": ";
  auto total = size_t{};
  for (auto &p : t.presents) {
    o << p << ' ';
    total += p;
  }
  return o << "(" << total << ")";
}

auto copy_if(const Present &in, Present &out, const Point &a, const Point &b) {
  if (in.contains(a))
    out.insert(b);
}

auto rotate(const Present &in) {
  auto out = Present{};
  copy_if(in, out, {0, 0}, {2, 0});
  copy_if(in, out, {1, 0}, {2, 1});
  copy_if(in, out, {2, 0}, {2, 2});
  copy_if(in, out, {0, 1}, {1, 0});
  copy_if(in, out, {1, 1}, {1, 1});
  copy_if(in, out, {2, 1}, {1, 2});
  copy_if(in, out, {0, 2}, {0, 0});
  copy_if(in, out, {1, 2}, {0, 1});
  copy_if(in, out, {2, 2}, {0, 2});
  return out;
}

auto hflip(const Present &in) {
  auto out = Present{};
  for (auto x = 0; x < 3; ++x)
    for (auto y = 0; y < 3; ++y)
      copy_if(in, out, {x, y}, {2 - x, y});
  return out;
}

auto vflip(const Present &in) {
  auto out = Present{};
  for (auto x = 0; x < 3; ++x)
    for (auto y = 0; y < 3; ++y)
      copy_if(in, out, {x, y}, {x, 2 - y});
  return out;
}

struct Puzzle {
  std::vector<Present> presents;
  std::vector<Tree> trees;
};

auto read() {
  auto rval = Puzzle{};
  auto ih = std::ifstream{"12.txt"};
  auto line = std::string{};
  for (auto i = 0; i < 6; ++i) {
    std::getline(ih, line); // number
    auto present = Present{};
    for (auto y = size_t{}; y < 3; ++y) {
      std::getline(ih, line);
      for (auto x = size_t{}; x < 3; ++x) {
        if (line.at(x) == '#')
          present.emplace(x, y);
      }
    }
    std::getline(ih, line); // following space
    rval.presents.push_back(std::move(present));
  }
  while (std::getline(ih, line)) {
    auto tree = Tree{};
    auto times = line.find('x');
    auto colon = line.find(':');
    tree.width = std::stoi(line.substr(0, times));
    tree.height = std::stoi(line.substr(times + 1, colon - times - 1));
    auto count = size_t{};
    auto ss = std::istringstream{line.substr(colon + 1)};
    while (ss >> count)
      tree.presents.push_back(count);
    rval.trees.push_back(std::move(tree));
  }
  return rval;
}

using Occupied = boost::unordered::unordered_flat_set<Point>;
using PresentFlips = boost::unordered::unordered_flat_set<Present>;
using PresentFlipsList = std::vector<PresentFlips>;

auto place_present(
    Occupied occupied,
    const Present &present,
    const Point &origin
) -> std::optional<Occupied> {
  for (const auto &point : present) {
    auto px = origin.x + point.x;
    auto py = origin.y + point.y;
    if (occupied.contains({px, py}))
      return {};
    occupied.insert({px, py});
  }
  return {occupied};
}

auto draw_occupied(const Tree &t, const Occupied &occupied) {
  for (auto x = 0; x < t.width; ++x) {
    for (auto y = 0; y < t.height; ++y) {
      if (occupied.contains({x, y}))
        std::cout << '#';
      else
        std::cout << '.';
    }
    std::cout << '\n';
  }
}

auto can_place(
    const Tree &tree,
    const PresentFlipsList &flips,
    Occupied occupied,
    PresentList list
) -> bool {
  auto j = size_t{};
  for (; j < list.size(); ++j) {
    if (list.at(j) > 0)
      break;
  }
  if (j == list.size()) {
    draw_occupied(tree, occupied);
    return true; // yeah!
  }
  list[j]--;

  for (auto x = 0; x < tree.width - 2; ++x)
    for (auto y = 0; y < tree.height - 2; ++y) {
      for (auto &flip : flips.at(j)) {
        auto test = place_present(occupied, flip, {x, y});
        if (!test.has_value())
          continue;
        auto works = can_place(tree, flips, test.value(), list);
        if (works)
          return true;
      }
    }
  return false;
}

auto part1(const Puzzle &puzzle) {
  auto possible = std::vector<Tree>{};
  for (const auto &tree : puzzle.trees) {
    auto area = size_t(tree.width * tree.height);
    auto used = size_t{};
    for (auto present = size_t{}; present < puzzle.presents.size(); ++present) {
      used += tree.presents.at(present) * puzzle.presents.at(present).size();
    }
    if (used > area)
      continue;
    possible.push_back(tree);
  }
  auto flips = PresentFlipsList{};
  for (auto j = size_t{}; j < puzzle.presents.size(); ++j) {
    auto flip = PresentFlips{};
    auto rotation = puzzle.presents.at(j);
    for (auto i = 0; i < 4; ++i) {
      flip.insert(rotation);
      flip.insert(hflip(rotation));
      flip.insert(vflip(rotation));
      flip.insert(hflip(vflip(rotation)));
      rotation = rotate(rotation);
    }
    BOOST_LOG_TRIVIAL(debug) << j << " has " << flip.size() << " flips";
    flips.push_back(std::move(flip));
  }
  auto confirmed = std::vector<Tree>{};
  for (auto &tree : possible)
    if (can_place(tree, flips, Occupied{}, tree.presents)) {
      BOOST_LOG_TRIVIAL(debug) << tree << " can be placed";
      confirmed.push_back(std::move(tree));
    } else {
      BOOST_LOG_TRIVIAL(debug) << tree << " can't be placed";
    }
  return confirmed.size();
}

} // namespace

auto main() -> int {
  auto puzzle = read();
  BOOST_LOG_TRIVIAL(info) << "Day 12: read " << puzzle.presents.size() << " / "
                          << puzzle.trees.size();
  BOOST_LOG_TRIVIAL(info) << "1:" << part1(puzzle);
}

Obviously very spoilery code, if you dare read it closely. try it here

It feels very anticlimactic to be ending so early in the month, but see you all next year!

# AOC 2025 day 12 - Packing parcels
▽⊸≡◇˜∊@x⊜□⊸≠@\n&fras"AOC2025day12.txt"
/+<⊙×₉≡◇(⊓/×/+⊃↙↘2⊜⋕¬⊸∊": x")

Kotlin

Looking at the puzzle, I knew that I had no clue how to solve it. So I came here to see if I was missing something or if there were any hints.

And the hint I saw was to do the simplest check possible, so I gave it a shot.

And that got the test input wrong, but I ran it against the real input anyway just to see if it was right. And it was.

I think if I had gone on my instincts and just tried to solve this, I could have gone around in circles for hours or days trying to get it right.

fun main() {
    val input = getInput(12)
    val (gifts, regions) = parseInput1(input)
    var total = 0
    for (i in regions.indices) {
        val totalAreaOfGifts = regions[i].gifts.mapIndexed { index, count -> count * gifts[index].area }.sum()
        if (totalAreaOfGifts <= regions[i].area) {
            total++
        }
    }
    println(total)
}

data class Gift(val shape: List<List<Char>>, val area: Int)

data class Region(val width: Int, val height: Int, val area: Int, val gifts: List<Int>)

fun parseInput1(input: String): Pair<List<Gift>, List<Region>> {
    val gifts: MutableList<Gift> = mutableListOf()
    val regions: MutableList<Region> = mutableListOf()
    val lines = input.lines()
    lines.forEachIndexed { index, line ->
        if (line.contains(":")) {
            if (line.contains("x")) {
                val split = line.split(" ")
                val shape = split.first().replace(":", "").split("x")
                val width = shape.first().toInt()
                val height = shape.last().toInt()
                regions.add(
                    Region(
                        width,
                        height,
                        width * height,
                        split.slice(1..<split.size).map { str -> str.toInt() })
                )
            } else {
                var nextBlankLineIndex = 0
                for (i in index + 1..<lines.size) {
                    if (lines[i].isBlank()) {
                        nextBlankLineIndex = i
                        break
                    }
                }
                val shape = lines.slice(index + 1..<nextBlankLineIndex).map { it.toCharArray().toList() }
                val area = shape.flatten().filter { it == '#' }.size
                gifts.add(Gift(shape, area))
            }
        }
    }
    return gifts to regions
}

Go

Well… I was about to dive into bin packing and stuff. I started by pruning the obvious candidates (those which can fit all the shapes one next to the other, without more computation) so save CPU time for the real stuff. I ran my code on the real input just to see and… what to do mean there are no candidate left? I write the number of obvious boys into the website’s input box, just to check and… Ah. I understand why people on reddit said they felt dirty x)

Anyway the code:

package main

import (
	"aoc/utils"
	"fmt"
	"slices"
	"strconv"
	"strings"
)

type shape [3][3]bool

func parseShape(input chan string) shape {
	// remove the header
	_ = <-input

	sh := shape{}
	idx := 0
	for line := range input {
		if line == "" {
			break
		}

		row := [3]bool{}
		for idx, c := range []rune(line) {
			if c == '#' {
				row[idx] = true
			}
		}

		sh[idx] = row
		idx++
	}

	return sh
}

func (sh shape) usedArea() int {
	sum := 0
	for _, row := range sh {
		for _, cell := range row {
			if cell {
				sum++
			}
		}
	}
	return sum
}

type regionConstraints struct {
	width, height int
	shapes        []int
}

func parseRegionConstraint(line string) (rc regionConstraints) {
	parts := strings.Split(line, ":")
	dims := strings.Split(parts[0], "x")
	rc.width, _ = strconv.Atoi(dims[0])
	rc.height, _ = strconv.Atoi(dims[1])

	shapes := strings.Fields(parts[1])
	rc.shapes = make([]int, len(shapes))
	for idx, shape := range shapes {
		rc.shapes[idx], _ = strconv.Atoi(shape)
	}
	return rc
}

type problem struct {
	shapes      []shape
	constraints []regionConstraints
}

func newProblem(input chan string) problem {
	shapes := make([]shape, 6)
	for idx := range 6 {
		shapes[idx] = parseShape(input)
	}

	regionConstraints := []regionConstraints{}
	for line := range input {
		rc := parseRegionConstraint(line)
		regionConstraints = append(regionConstraints, rc)
	}

	return problem{shapes, regionConstraints}
}

func (pb *problem) pruneRegionsTooSmall() {
	toPrune := []int{}
	for idx, rc := range pb.constraints {
		availableArea := rc.height * rc.width
		neededArea := 0
		for shapeId, count := range rc.shapes {
			neededArea += pb.shapes[shapeId].usedArea() * count
			if neededArea > availableArea {
				toPrune = append(toPrune, idx)
				break
			}
		}
	}

	slices.Reverse(toPrune)
	for _, idx := range toPrune {
		pb.constraints = slices.Delete(pb.constraints, idx, idx+1)
	}
}

func (pb *problem) pruneObviousCandidates() int {
	toPrune := []int{}

	for idx, rc := range pb.constraints {
		maxShapePlacements := (rc.width / 3) * (rc.height / 3)
		shapeCount := 0
		for _, count := range rc.shapes {
			shapeCount += count
		}
		if maxShapePlacements >= shapeCount {
			toPrune = append(toPrune, idx)
		}
	}

	slices.Reverse(toPrune)
	for _, idx := range toPrune {
		pb.constraints = slices.Delete(pb.constraints, idx, idx+1)
	}

	return len(toPrune)
}

func stepOne(input chan string) (int, error) {
	pb := newProblem(input)
	pb.pruneRegionsTooSmall()
	obviousCandidates := pb.pruneObviousCandidates()

	fmt.Println(pb)
	fmt.Println(obviousCandidates)
	return 0, nil
}

func stepTwo(input chan string) (int, error) {
	return 0, nil
}

func main() {
	input, err := utils.DownloadTodaysInputFile()
	if err != nil {
		_ = fmt.Errorf("error fetching the input: %v", err)
	}

	utils.RunStep(utils.ONE, input, stepOne)
	utils.RunStep(utils.TWO, input, stepTwo)
}

Python

You got me good, Eric.

# This does not work for the sample :D

def solve(data: str):
    # split input
    blocks = data.split("\n\n")
    shape_blocks = blocks[:-1]
    region_block = blocks[-1]

    # for every shape, get the number of occupied cells
    shape_area = []
    for shape_block in shape_blocks:
        shape_area.append(shape_block.count('#'))

    fit_regions = 0

    # for every region, check if the area is sufficient to fit all shapes
    for region_data in region_block.splitlines():
        size_data, shape_data = region_data.split(': ')

        # get region size
        m, n = [int(dim) for dim in size_data.split('x')]

        # get area needed to fit all shapes, without considering arrangement
        area_needed = 0
        for id, freq in enumerate(map(int, shape_data.split(' '))):
            area_needed += shape_area[id] * freq
        
        # if the region area is sufficient, count it as a fit (!!!)
        if m * n > area_needed:
            fit_regions += 1
    
    return fit_regions

Rust

Its not Christmas, but this one was a gift :D. Merry Christmas all, thanks for everyone who has contributed solutions!

Rest easy little advent bot, your work is done now.

    struct Tree {
        w: u32,
        h: u32,
        presents: Vec<u32>,
    }

    fn is_solveable(tree: &Tree) -> bool {
        if tree.h * tree.w < tree.presents.iter().sum::<u32>() * 9 {
            return false;
        }
        true
    }

    #[test]
    fn test_y2025_day12_part1() {
        let input = include_str!("../../input/2025/day_12.txt");
        let parts = input.split("\n\n").collect::<Vec<_>>();

        let trees: Vec<Tree> = parts
            .last()
            .unwrap()
            .lines()
            .map(|line| {
                let parts: (&str, &str) = line.split_once(": ").unwrap();
                let [w, h] = parts
                    .0
                    .split("x")
                    .map(u32::from_str)
                    .map(Result::unwrap)
                    .collect::<Vec<_>>()[..]
                else {
                    unreachable!()
                };
                let num_presents = parts
                    .1
                    .split(" ")
                    .map(u32::from_str)
                    .map(Result::unwrap)
                    .collect::<Vec<_>>();
                Tree {
                    w,
                    h,
                    presents: num_presents,
                }
            })
            .collect();

        let mut solvable = 0;
        for tree in trees {
            if is_solveable(&tree) {
                solvable += 1;
            }
        }
        println!("solvable: {}", solvable);
    }