Facebook organizes this cool competition called the Hacker Cup. Yesterday the Qualification Round finished, and the user solutions got published. So, since the problems text is under a CC license (thanks FB!) I’m publishing here the problems and my answers.
This code pretty much embodies why I love Python: it’s clear, fast to write and reads almost like English. When I (thought I) needed speed, I just turned at Cython with a few edits to the code.
NOTE: if for some reason I misunderstood and I wasn’t allowed to do this, please get in contact with me ASAP and I’ll take this down.
This was an easy one, I just scanned the grid until I found a
#, assumed it was the upper-left corner and counted the following
# to learn the edge length. At this point I had all the info to build a model of how a correct grid should look like, so I just checked the real one against it.
This is actually my favorite. The problem was fun and the Python code reads as if it was English. It makes hard use of mutable objects and their properties.
Finally the hardest one. This was a nice recursive problem. The constrains allowed for a lot of big test cases, so I went a bit overkill with speed, wrote some custom caching, ported my actual recursive function to Cython (it’s awesome! Just check out the
-a HTML output to figure out what you have to optimize and you’re done) and made the program parallelizable.
Turns out, memoization would have been enough. Still, it has been really fun!
That’s all! I got admitted to the next round, so maybe follow me on Twitter if you want to read the next batch of problems and solutions!