Here we go again.

My brother pointed me to challenge problems up at Dropbox.  The first one asks to find the minimum enclosing rectangle of smaller rectangles.  This is a kind of combinatorial packing problem.  It is NP-hard: an algorithm that could solve this problem efficiently could also be used to solve some other very hard problems – but hey, at least the problem is not that hard.  It’s the subject of much research, (researchresearch, research!), as it turns out to be quite important for resource scheduling.

Goodbye, free time.

Protected: Quora Datacenter Cooling Solution

Programming Enter your password to view comments.
Jan 252011

This content is password protected. To view it please enter your password below:

I don’t remember how I originally came across this challenge problem, but it tickled my brain, and I wanted to give it a shot.  It’s clear the problem is a variation on that good old depth-first-search problem of finding a Hamilton Path on a graph – in this case a 2D grid graph.  I knew the general problem to be NP-complete, but I wasn’t sure whether the constrained problem (on a 2D graph) was too.

I did some research and found papers and resources online: here, here, and later, here.  It turns out that searching a grid graph with holes for a Hamiltonian Path is indeed NP-complete.  The Quora problem is in an even harder complexity class: we want to find ALL Hamiltonian Paths.  I’m no complexity expert, but it appears this problem is in the class #P.

I also wanted to try coding it up in the D programming language, which I eventually did.  But at first I found it a bit cumbersome to “think in D”, so I started hacking in Python.  I used the NetworkX libary to model the problem abstractly, which gave me an easy way to work with vertices and edges as Python objects.  I had a solution to the problem in short order, but on Quora’s 8×7 example input, it took over an hour!

It wasn’t until I looked at Faase’s work (in the links above) that I realized a much faster search would not care about edges.  It would visit only vertices, and make only local decisions about what vertex to visit next and how to cut the search short.  I revisited and finished the solution in D, and then ported it to C for speed (using GCC 4.2 with optimizations in XCode) .  This was actually quite easy to do, since I didn’t use any major D-specific language constructs.

My final solution in C completes the 8×7 example in just over two seconds on my 2.53Ghz Macbook pro.  The code is up as a protected post.  If you’d like to check out the solution, contact me for the password!

© 2014 Adam Klein's Blog Suffusion theme by Sayontan Sinha, modified by Adam :)