For today’s challenge, we are presented with what initially appears to be a difficult optimization problem. In fact, a quick search reveals that this problem can be modeled as a variant of the geometric knapsack problem, which is NP-hard. A good lecture on this class of problems can be found here.
A naïve dynamic programming approach that precomputes all translations and rotations of each of the five shapes is infeasible. With five shapes, four rotations each, translations, and arbitrary placements, the problem space quickly explodes to well over $50! \approx 8.3.0414 \times 10^{64}$ permutations.
My initial approach was to better understand the structure of the input and look for ways to aggressively reduce the search space. The first key insight was to establish an easy lower bound that eliminates invalid specifications outright. In other words, without trying every rotation or flip, I identified X×Y spaces that are simply too small to accommodate the required number of shapes and their combined area.
For example, a 10×10 space cannot hold 20 shapes if each shape has an area of 10, regardless of how they are rotated. Applying this constraint immediately eliminates roughly half of the candidate spaces.
with open("12.input") as f:
data = f.read().split("\n\n")
shapes = [i.splitlines() for i in data[0:6]]
specs = data[6].splitlines()
specs = [(tuple(int(j) for j in i.split(": ")[0].split("x")), [
int(k) for k in i.split(": ")[1].split(" ")])
for i in specs
]
sim_area = dict((int(s[0].strip(":")),sum( t.count("#") for t in s[1:])) for s in shapes)
val1 = [ ((x,y),l) for (x,y), l in specs if x*y > sum( [ sim_area[i]*num for i, num in enumerate(l)])]
inval1 = [ ((x,y),l) for (x,y), l in specs if x*y < sum( [ sim_area[i]*num for i, num in enumerate(l)])]
print(f"The number of valid areas with simple floor bounding are {len(val1)} and the number invalid are {len(inval1)}")
The number of valid areas with simple floor bounding are 546 and the number invalid are 454
Next, I examined the opposite extreme: spaces with excessive area—that is, spaces that are sparse. I bounded each shape by a 3×3 box and checked whether the number of such boxes could fit within the given problem space. This idea was inspired by the lecture referenced above.
loose_areas = [ ((x,y),l) for (x,y),l in val1 if x * y >= sum(l)*9]
print(f"The number of loose areas are {len(loose_areas)}")
The number of loose areas are 546
Interestingly, the number of valid spaces identified by the lower-bound constraint exactly matched the number of “sparse” spaces identified by this upper-bound analysis. This overlap turns out to be the answer to the problem. Ultimately, no advanced algorithmic technique was required—just careful reasoning about bounds and constraints.
Please comment!