By Adam Kalai and Danny Sleator


Check out the results and the puzzles and solutions.

The 2000 Immigration Course Programming Contest

Adam Kalai and Danny Sleator

Consider the game of Tetris. Being perverse, you start to doodle, and create interesting patterns of occupied and empty cells on the board (instead of trying to optimize your Tetris score). This is what you will try to do in this contest. We will give you some pictures (actually, we'll call them "puzzles" from now on) that you must "draw." For each puzzle, you will give us a sequence of Tetris pieces (and orientations and positions from which to drop them) that makes this puzzle. The fewer pieces you use, the better. (You can play with an applet to get a feel for what this problem is like.)

Prize: The winner will get a Palm Pilot of his or her choice! (In case this prize is inappropriate, like, for example, the winner already has a Palm Pilot, then the winner can choose an electronic gizmo of comparable value instead.)

Who can enter: Anybody from the CMU SCS community is eligible. You must have an email address ending in "@cs.cmu.edu" or "@andrew.cmu.edu".

Teams: You may work in teams of up to two people. In case a team with two members wins, then each member of the team will receive a prize.

Administration: We've set up an Administration page for the contest where you can register, submit solutions to the puzzles, and see the current status of the contest. You may submit as many solutions to any puzzle as you like, as long as your new solution is better (uses fewer pieces) than your previous solution.

Determining the Winner: Roughly speaking, the goal is to solve all the puzzles with as few pieces as possible. More formally, the winner is the contestant solving the most puzzles, with ties being broken by preferring the solutions that drop the fewest pieces (summed over all the puzzles solved). If there are ties by this criterion, then the one submitting the last of the solutions earliest will be the winner. The current standing can be seen at any time by displaying the contest status page. The winner will be determined based on what has been submitted prior to the contest deadline.

Deadline: The deadline is a SECRET TIME between 4pm on the 9th of October and 4pm on the 14th of October, 2000. When the contest ends, this fact will be announced on the contest administration page (and you will be surprised :-). No further submissions will be allowed after the deadline. Therefore, between these two times, it behooves you to submit an improved solution the moment you compute it.

Award Announcement: The winner will be announced at the Login Ball, which is the evening of October 14th.

Postmortem: After the award announcement, the actual identities of all the contestants will be revealed. The winners will be asked to write a description of how their program works, and how they came up with their solution. The winning code will be made public. Everybody else, of course, is welcome to submit such descriptions. These will be posted on the postmortem page.

Questions: If you have questions, or want clarifications, send email to Adam Kalai. He'll anonymize your question and post the question and answer on the questions page.

Acknowledgements: We had helpful discussions with John Lafferty. Darrell Kindred let us use his secure web server for the administration page.

Now that you're excited about this, go to the Gory Details page to see how this is all going to work.

WINNERS: Scott Lenser and James Bruce.


The contest is over. See the winner's program and writeup.
Daniel Sleator
Last modified: Sat Oct 14 14:38:24 EDT 2000