Log in

No account? Create an account
Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

ICFP Contest 2011! [Jun. 19th, 2011|08:05 pm]
Lindsey Kuper

Team K&R just finished competing in the ICFP Programming Contest! This was our third time participating, having done it before in 2009 and 2008, and we're having what I think is our best showing yet.1 We did it in public this time -- why not, you know? -- so you're welcome to poke around at our code, including the whole revision history. There's also a README that explains some of the details of our submission, for those interested in such things.

The contest has always been pretty fun, but I think the organizers did a particularly tremendous job with it this year. This problem pushed all our buttons. There were lots of clever things about the design of the game that made it fun and challenging to play, and I'm humbled when I think about the amount of work that they must have put into it. Well done, contest organizers!

  1. We ended up in 76th place out of 291 teams on the leaderboard at the time they stopped updating it, which was nine hours before the end of the contest. The unofficial duel server is still running, and it looks like our most recent entry has won exactly half of its duels. If we assume that our official place does end up being something like 76th, then that's a marked improvement over 2009, when we finished in 149th place, and 2008, where the results are harder to interpret, but at some point I worked out that we came in something like 174th. So, as you can clearly see from a linear regression fit to the data, we're on track to get first place in roughly 2013. That's how math works, right? [Update, June 27: the official results put us in 110th place, so the data now clearly indicate that we're on track to win in roughly 2016. Good; that gives us time to finish dissertatin' and spend some time chillaxin' first!

[User Picture]From: lindseykuper
2011-06-20 04:26 pm (UTC)
You know, we totally missed the part of the task description that shows how to implement an infinite loop. (The example they give is: put S(get)(I) in slot 0, then apply 0 to it. get(0) evaluates to S(get)(I), I(0) evaluates to 0, and then you apply those to each other, repeating the process. But as far as I can tell, you could pass in any function in place of the I, as long as it's a one-argument function that returns identity -- including something that does side effects. Side effects like decrementing the other player's slots. *facepalm* I need to try this after work.)

In a sense, though, I'm glad that we did it the way we did, with the Y combinator and all. Holy crap, those were some big SKI terms we constructed. It was slow, but it worked!
(Reply) (Parent) (Thread)
[User Picture]From: jcreed
2011-06-20 10:55 pm (UTC)
AHHHHHHHHHH that's how you do it.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2011-06-21 09:45 am (UTC)
Actually, I misspoke. You don't want to pass a function that returns identity; you want one that behaves like identity, except for possible side effects. Otherwise, you won't be returning yourself, which is the whole point. So, I'm still not really sure how to take advantage of that kind of looping. I was chatting about this with sully at work today, though, and he pointed out the Unlambda self-application trick, which is a lot faster to set up than a full-blown Y combinator.
(Reply) (Parent) (Thread)