July 10th, 2007


We are all geeks

gdmusumeci pointed me at this XKCD comic:

He laughed at himself at what a geek he was for actually solving it, which only egged me on, of course, and then I had to waste a good ten minutes of work solving it myself. I spent a minute trying to finesse it before realizing, duh, the knapsack problem is NP-Complete, there ISN'T any way to finesse it, only this way:

Collapse )

$ perl app.pl
got it: 15.05,  1 0 0 2 0 1

So, the (unique) answer is one mixed fruit, two hot wings, and a sampler plate. And thus was I able to proceed with my work.

EDIT: That solution is not unique; there is another, completely obvious solution of seven mixed fruits. See the comments for the geekery of why this script misses that answer. Grr.