I ignored my own advice, burned a day, and proved—once again—that
I am my own worst client.
Our new book distributor has a talent for inventing things to charge us money for. Dozens of them. We have to account for each of these, assigning costs to individual titles so we can correctly calculate royalties. Easy, right?
Except the “per-book” expenses show up on one statement, and the lump-sum deductions that we end up paying come on another. And each of these lumps can hide a grab-bag of individual expenses, none labeled. All we get is a couple of dates and one random-looking total. We then have to match that total to some combination of expenses.
In coding-interview lore, that’s the Subset Sum problem: take a pile of numbers and figure out which combinations add up to a given total.
It’s an NP problem; big, scary running time.
I knew that. And that was the trap.
Armed with my one dangerous fact, I set out to optimize. Pruning strategies. Grouping likely pairs. A truly deranged idea involving only the last digit of each number, because apparently I hate myself.
Hours vanished. Lunch went cold. I kept convincing myself the next trick would crack it.
At last I had something that looked promising, but I needed to be sure it caught all the subsets. So I wrote a brute-force version to test against.
I set it running and shoved my chair back, ready to walk the dog while it ground away for hours. Before I’d even stood up, the prompt blinked back.
That couldn’t be right—must be a bug. But the output looked fine.
I hammered it with property-based tests. All green. It finished in milliseconds.
I’ve stood on countless stages quoting Knuth’s immortal line: “Premature optimization is the root of all evil.” And then I went and sacrificed a day on the altar of exactly that.
Physician, heal thyself.