As multicore CPUs and distributed applications become the norm rather than the exception, more and more programmers are discovering that concurrent programming is a lot harder than sequential programming---so much so, in fact, that traditional "hack and patch" approaches simply don't work. Race conditions and deadlocks are hellish hard to reproduce under controlled circumstances; if you don't design and analyze concurrent systems before putting them together, the odds are long that they'll never really work.

I therefore wasn't surprised that several of the contributors to Beautiful Code chose concurrency as their topic. While beauty is desirable elsewhere, I think it's essential in the brave new parallel world the industry is rushing toward. I'd therefore like to set a challenge to readers of this blog: we'll send a free copy of the book to the 20 people who submit the most elegant, correct, solution to the problem described below by this Halloween (October 31, 2007). Answers don't have to consist of running programs---sufficiently detailed pseudocode is fine---but you must explain (a) why you believe your solution works, and (b) what makes it beautiful. You can submit your entry at the Beautiful Code wiki site; the rules of the game are given there, and below.

Speed Scrabble is a game for two or more players that takes only a few minutes to play. The rules are simple:

  1. Spread the tiles face down on the table. Each player chooses 15 tiles at random, and puts them in front of herself; the rest are set aside.
  2. Someone says "Go!" Every player turns over 7 of her tiles and starts trying to make words with them. Words must crisscross in the standard Scrabble way, and the players' "boards" are independent---each player only uses her own characters.
  3. As soon as any player has made a board using all 7 of her characters, she shouts, "Go!" Every player turns over another character, so that all players now have 8 characters to use. Players may rearrange their pre-existing words when and as they please---they do not have to stick to their earlier choices.
  4. When any player has used all 8 of her characters, she shouts, "Go!", and everyone turns over their ninth tile. This repeats until everyone has turned over all 15 tiles. The winner is whoever makes a legal 15-character board first.

The challenge is to design the architecture of a "referee" program for a computer Speed Scrabble tournament. Contestants will submit classes that extend an abstract base class called IPlayScrabble that the contest organizers will provide. These classes will be loaded by a SpeedScrabble program, which will create an instance of each one and pass it the dictionary of words that can be used in the game, and its first seven tiles.

Each player will run in its own thread, in parallel with its competitors. As soon as it has made a board with the tiles it has, it will request another tile from the "referee". The first player to complete a 15-tile board wins.

This is trickier than it first seems because players have to be able handle "interrupts", i.e., notice when the referee is trying to give them another tile that they didn't ask for because some other player has taken the lead. (It's often the case that a set of $N$ tiles has no solution, but an $N+1$-tile extension does, so not taking tiles as soon as they're offered is a good way to come in last.) At the same time, when the central referee is handing out tiles, it must never wait for a player to accept one before moving on to the next player, because if it takes player P two seconds to say, "Yes, thank you, carry on," that's two seconds that player P+1 has lost.

So: how will the central referee hand out characters? What methods will you give players, and which ones will they be trusted to implement themselves? Most importantly, how will you convince sceptics that your synchronization and communication scheme can't deadlock, and won't ever starve one player because of something another player has done?