I’m pulling out all the junk stuff I did on my spare time. I promise 100% all the code samples coming out were built on my own time, and boy am I glad to GPLv3 all of them. The latest one, and easiest one to post was a rectangle packing program I was trying out for the DropBox challenge (as part of hiring – considering I worked on Mesh, DropBox seemed like a great company to move to at the time.)
Anyhow, I learnt increasing an order of magnitude for an NP-Hard exponential problem doesn’t help (an N+1 input will kill you anyway.) Couldn’t think of a probabilistic method in the 2 days I spent on it. There’s a couple of optimizations I wasn’t able to do due to the DS I choose. A sparse grid or matrix would have been the right way to go here, but reverting state is difficult on those. The one thing that would speed this up further is to proactively look at the shape of the unfilled area in the candidate box, and find one of the unplaced rectangles that would never fit in that shape. That would trim a large number of candidate boxes fast.
For what it’s worth, here’s the dirty code. More of the BCI signal-processing code to follow over the weekend. Here’s the file: RectanglePacker
