As I said before, the Tragic problem is not a pure figment of my imagination. It actually came from an article I read in which the author, one of the programmers for the Magic Online computer game, talked about his difficulty implementing a program that would check to see if a submitted deck was legal for a particular variant of Magic. I loved the problem because it was so simple and easy to describe but at the same time so difficult to say anything concrete about. Many ways to solve the problem spring to mind immediately for everyone who hears the problem, but are those ways correct? Are they fast? Can we guarantee it in all cases? How can we even come up with a deck that taxes even a stupid brute-forcer to the point where it's not workable? It's pretty clear the problem is in NP, but is it NP-complete? I posed the PFC partially to see what the answers to those questions were.

The answers:

• Is it NP-complete? No (unless P=NP). edwin was the first to prove this by posting an elegant reduction to a problem with a known polynomial-time solution.
  
• Is brute force fast? Yes (in practice anyway). Most of the programs submitted to the competition were brute-force algorithms of some stripe, and the best ones routinely outperformed the more complicated algorithms on average cases. If I were to recommend a program to the Magic Online people, it'd definitely be a brute-forcer.
  
• Can brute-forcers pare the search-space down without sacrificing correctness? Yes. Lots of clever search-space reduction strategies were in evidence. Even simple strategies like counting to make sure there are at least twenty cards that have each color at all before starting the search make a huge difference.

There were two general approaches that submitters took:

1. Brute force with search-space reduction — by far the most popular tactic. jjayson, george, siddhi, tmoertel, TPD, codemonkey uk, and Xenocide all submitted programs of this sort. ucblockhead submitted a variant of this tactic that in practice amounts to mostly a brute-force search, but isn't actually guaranteed to visit every relevant state (though it works fine in practice).
   
2. Reduction — reduction of the problem to one already solved in mathematics.  edwin, celeriac, and the submitted programs that took this strategy.


Entrant        | language | correctness   | speed    | code clarity   | cleverness
----------------------------------------------------------------------------------
TPD            | Pascal   | 10            | 10       | 8              | 6
Xenocide       | C        | 5             | 10       | 6              | 6          fails one of the posted examples :(
celeriac       | Python   | 10            | 10       | 9              | 9          great!
codemonkey uk  | C++      | 5             | 10       | 10             | 6          fails one of the posted examples :(
edwin          | C++      | 10            | 10       | 10             | 10         I loved this reduction
george         | C        | 10            | 10       | 8              | 6
jjayson (1)    | K        | 10            | 1        | :)             | 10         winner, most seconds taken per character of source code
jjayson (2)    | K        | 10            | 10       | 7              | 6          don't know how to judge code clarity on this one
siddhi         | Python   | 10            | 10       | 9              | 6
the            | C++      | 10            | 10       | 9              | 7          good brute-forcer
tmoertel       | Haskell  | 10            | 10       | 10             | 7          very beautiful code
ucblockhead    | Forth    | 10            | 10       | 8              | 8          yay forth!


CLEVEREST PROGRAM: Edwin edges out the competition here due to his surprising but clear reduction of the problem to the familiar graph flow problem. Honorable mentions go out to celeriac and the.

CLEAREST CODE: tmoertel wins this one, whose ability to write fantastic Haskell continues to impress me.

SHORTEST CODE: If you're like me, you've had the sneaking suspicion that jjayson just writes down random characters for these PFC's more than once. But amazingly the line noise produces correct answers, and that's got to be worth something. I particularly liked how his program avoids duplication by always printing "legal" and prepending "il" if deck doesn't meet the criterion.

OVERALL WINNER: Edwin. His program's speed was admirable and the mathematical insight behind it was substantial. Good job!

Congratulations, edwin, and to everyone who participated! It was fun and enlightening for me; I hope is was for you too.