PFC TRAGIC RESULTS
By jacob (Fri Jun 18, 2004 at 10:55:59 AM EST) (all tags)
Some of you Husi old-timers may remember back in the days of yore when the most recent Programming Fun Challenge was announced. Well, it's been a long time, but I'm happy to announce that I've finally finished grading the competition, so here are the results.

THE BIG PICTURE

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.

• 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.

THE STRATEGIES

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.

THE RESULTS

``` 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.

PFC TRAGIC RESULTS | 14 comments (14 topical, 0 hidden) | Trackback
Do you realise by Evil Cloaked User (3.00 / 0) #1 Fri Jun 18, 2004 at 11:08:41 AM EST
That I didn't enter 'cos I didn't think I'd make the deadline!

Right, I'm gonna go read the diary now.

sorry about that :( [nt] by jacob (3.00 / 0) #2 Fri Jun 18, 2004 at 11:09:44 AM EST

--

[ Parent ]

IAWTP :) by komet (3.00 / 0) #4 Fri Jun 18, 2004 at 11:14:19 AM EST

--
<ni> komet: You are functionally illiterate as regards trashy erotica.
[ Parent ]

yay! by ucblockhead (3.00 / 0) #3 Fri Jun 18, 2004 at 11:12:27 AM EST
Fun problem!
---

Thanks, jacob! You picked a great problem. by tmoertel (6.00 / 2) #5 Fri Jun 18, 2004 at 01:24:02 PM EST
Let's give jacob a big thanks for hosting this round.
T H A N K S ,   J A C O B !

(For those of you who have never done it, hosting a PFC can easily eat several days of your time. Volunteering for this duty is a generous gift to the community of programmers who like to solve tricky yet reasonably sized problems.)

Jacob's selection of a challenge task was ideal. I cannot think of any task so well suited for PFC.

Again, thanks, jacob!

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

I agree by TPD (3.00 / 0) #7 Fri Jun 18, 2004 at 10:37:32 PM EST
An excellent problem very well hosted, hopefully we'll see Edwin or somebody else pick up the hosting baton soon.

I think a few of the contenders might not be HuSi regulars.... it might be worth sending a mail through the mailing list pointing to this page.

why sit, when you can sit and swivel with The Ab-SwivellerTM
[ Parent ]

cleverness by ucblockhead (3.00 / 0) #6 Fri Jun 18, 2004 at 02:59:44 PM EST
I think you were a bit generous giving me an eight for cleverness. I wish I could have figured out a way to determine a real end case other than just assuming that if I hadn't found a legal set in a certain number of iterations, I wasn't going to.
---

Did you try my decks? by tmoertel (3.00 / 0) #10 Sat Jun 19, 2004 at 06:36:43 AM EST
I'm wondering if you tried your program on the decks I provided. I designed one of the decks (can't remember which one) to cause a cycle in your deck-swapping algorithm and cause a false "illegal" judgment. (You might need to try the color-traded variant to actually trigger the cycle.)

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]

WTF by steve h (3.00 / 0) #8 Fri Jun 18, 2004 at 10:56:22 PM EST
Did they all take exactly 10 milliseconds or something?

Blimey by edwin (3.00 / 0) #9 Sat Jun 19, 2004 at 06:21:56 AM EST
I didn't actually look at the other entries in detail, but several people claimed to have a linear time solution, so I'm pretty surprised to get the nod.

Anyway, thanks to Jacob for a fun challenge. I've posted a few ideas for potential PFCs here. I'm not super-pleased by any of them, but let me know what you think.

Did the "fast" entries work? by tmoertel (3.00 / 0) #11 Sat Jun 19, 2004 at 06:53:24 AM EST
I think that I can build decks that jjayson and ucblockhead's solutions classify incorrectly. See jjayson's comment and my follow-up to it for one such counter-example deck. (You might also want to read the containing diary entry for context.)

So far, nobody has shown that a linear-time solution is even possible.

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]

should've clarified by jacob (3.00 / 0) #12 Sat Jun 19, 2004 at 09:06:59 AM EST
The reason I chose yours was that while I couldn't build counterexamples for many of the algorithms, they weren't obviously correct (and the authors couldn't convince me or themselves of correctness).  So they got correctness points (seems mean to take points away on suspicion), but I gave extra cleverness points to solutions that convincingly always worked, particularly if they did so by relating the problem to something else in mathematics. Your solution came with both a very convincing case for correctness and a pretty fast running time in the worst case, and it was well-coded and easy to read, so I decided that was deciding factor.

Anyway, congratulations and thanks for a neat solution.

--

[ Parent ]

Nooo... :( by codemonkey uk (3.00 / 0) #13 Sat Jun 19, 2004 at 09:23:34 AM EST
I hate failing on correctness. Which test did it fail on?

Thanks for hosting!