Introduction
Advent of Code is a series of coding challenges in December, now in its eleventh season. Each day a new puzzle is unlocked and programmers in all the world try to solve them, with various goals in mind: to learn a new language, to improve their skills, to have fun, to help Santa… This year there were 12 days of puzzles.
The Problem
The Day 12 2025 problem was on placing presents in a limited space under the Christmas tree. You get presented with 1000 scenarios and you have to figure out for each of them whether it is solvable, meaning that the presents fit into the designated area.
For each scenario, the area is rectangular, but its size varies. The presents come in a handful of shapes, but their number varies again. Here is an example of how the 6 pieces can be placed in the given area (here 12x5):
(The visualization is done via Ansys SpaceClaim scripting by creating the present geometries.)
Note that the presents can be flipped and rotated in the plane (by multiples of 90°).
Now for the actual problems, the number of presents, but also the areas are a lot larger:
Bin packing is a hard problem (NP-hard), so in general, this means that often you need to run through all the possibilities to check whether there is any solution (bruteforcing). Of course, you can do so in more and less clever ways, for instance by taking symmetries into account and stopping early if a branch becomes infeasible. My solution implements a backtracking algorithm and stops at the first solution (i.e. it doesn’t try to find a tighter packing). It is able to solve also packing-wise more challenging problems like this:
However, the complexity grows exponentially with the size of the problem and solving it becomes very quickly intractable.
There is one caveat, this problem happens to be a “troll” problem, tricking people into writing much more complicated code than needed (I’m guilty as charged). The scenarios fall in two categories: a) the presents all fit into a 3x3 subregion and there are more than enough 3x3-subregions in the domain (i.e. trivially solvable); b) the total area of all presents is larger than the area of the domain (i.e. trivially non-solvable). There are no problems of the intermediate category (like the last example here) which would need a proper packaging algorithm. It was nonetheless a fun exercise.
The Code
You can check out Andreas' code here: https://gist.github.com/andreas-hilti/81d419a90bd6067b16751f9b3cf0677c . However, please bear in mind that this code was written for fun, as part of Advent of Code and does not conform to Ansys' usual standards of code quality. It is also subject to change as further developments are made.
