I had a pesky, seemingly insoluble programming task I've been dabbling with for about 3 weeks now in my downtime. Some fellow programmers have posted implications that they have created a correct solution, but until last night, I had been getting something wrong. I suspected my reading of the specs wasn't correct, my approach was skewed, or, God forbid, my choice of programming language was wrong. A little background:
Facebook has a "careers" link on its homepage, which I found one day when a grass-is-greener-on-the-other-side moment led me to poke around job app sites and see what was out there that may make me happier. [Predictably, nothing seemed more attractive or stable than AEP... at least, nothing that would let me stay in my current home]. On Facebook's careers page is also a link to "Puzzles". Curious, I investigated.
The Puzzles page has a list of programming languages (plus make and model, e.g., Gnu C++ version 5.2 instead of just C++) that their black-box puzzle evaluator supported, and a set of puzzles with input and output specifications for prospective programmers to try their hands at. Prominently displayed are a couple of pictures of smiling winners under the caption "solved and hired", implying that if I can write good solutions to all the puzzles, Facebook will fly me out to Palo Alto for a new, joyous life of coding for a social networking company.
After seeing that, I queried the missus "Hey, angel, want to move to Palo Alto?". "No." So that settled that, but some of the puzzles seemed interesting. One was a basic test to see if you can read a spec and write something that is no more complicated than a "Hello, World" program. Not being a tool, I skipped that and moved onto the next, which was reading an input file that had a number in it, counting from 1 to that number, and outputting one of three strings if the count was evenly divisible by 3, 5, or 15. A few minutes later I had some sample perl code to do that, submitted it, and later got an email back congratulating me on my working solution.
Then came the "Gattaca" puzzle. The bad news about submitting code for Facebook puzzles is that if your code doesn't pass their tests, they don't tell you why. It's all automated, and all the replies have the same text, to the tune of "sorry, that didn't work, try reading the specs or trying more test cases, and don't use any funny modules I might not have installed." Good advice, to be sure, but the one thing I've always had in all my coding jobs is good feedback. The error message. The log file. I've never been faced with mysterious, black box test cases, and no results other than a pass or fail. That's a real drag.
So I had been drowning in the shame of suddenly being sub-elite as my first four code submissions to the puzzle all failed, but contradictorily I was excited about all the cool optimizations I found in code rewrites. For example, an early version of the code took 6 minutes to handle a sample test of 100 genes in a 1000 character long DNA string, where my final version tackled the same set in a couple milliseconds.
The premise of the puzzle is that you have a string of DNA codes [ACGT], a list of the start and stop positions of possible genes, and a value, or "weight" for those genes. The genes may or may not overlap each other. The goal is to calculate a path through the entire DNA string that has the highest total genetic weight with no selected genes overlapping. The output is just the final total value. Here's an example, omitting the actual DNA string:
| Start | End | Weight |
|---|---|---|
| 10 | 15 | 5 |
| 12 | 20 | 10 |
| 25 | 30 | 3 |
| 35 | 40 | 3 |
| 27 | 37 | 5 |
