Already the last day, that went by quickly. Usually the last day of AoC is easy so people can spend Christmas with their close ones. But there are still 13 days before Christmas, so maybe it's supposed to be a longer solve?

Anyway, the problem seems to have a non-trivial parsing (but not too hard either). I do it, then start thinking about a solution. I need to rotate the pieces, and that's easy, I can just use my grid code for that; then I remove the duplicates from rotations. Problem looks complex, so I integrate the example as tests immediately (as opposed to later if I'm blocked).

So this looks like it's a 2D bin-packing problem (Tetris-style). I do some research and find an excellent thesis in french on the subject: https://theses.hal.science/tel-00158728v1/document

As I read through, it reminds me that this is an unsolved NP-hard problem. So surely there must be a trick?

I decide on hunch to try the minimum test that could work. It fails on the example. Nevertheless, I have nothing to lose, so I submit my solution… and it works!

Turns out the last day *was* that easy, and a funny joke with the example as a trap. Luckily I hadn't written too much code before realizing that.

And that concludes this edition of AoC!

#AdventOfCode #BinPacking

Thanks for coming along with me! This was me liveblogging "Solving the Batch Stochastic Bin Packing Problem in Cloud: A Chance-constrained Optimization Approach", by Jie Yan, et al. It's from a bunch of folks at Microsoft and Peking University.

Follow along for more of this in the future! Or, if you're interested in more long-form writing about these topics, you can subscribe to my blog! It's right here:

https://blog.appliedcomputing.io

#liveblogging #distributedsystems #optimization #binpacking