Crossword Extravaganza Service Specification

FILE ::= ">>" NAME DESCRIPTION "\n" ENTRY*
NAME ::= StringIdent
DESCRIPTION ::= String
ENTRY ::= "("  WORDNAME ","  CLUE "," DIRECTION "," ROW "," COL ")"
WORDNAME ::= [a-z\-]+
CLUE ::= String
DIRECTION ::= "DOWN" | "ACROSS"
ROW ::= Int
COL ::= Int
String::= '"' ([^"\r\n\\] | '\\' [\\nrt] )* '"'
StringIdent ::= '"' [^"\r\n\t\\]* '"'
Int ::= [0-9]+

>> "Simple Puzzle" "A trivial puzzle designed to show how puzzles work"
 (cat, "feline companion", DOWN, 0, 1)
 (mat, "lounging place for feline companion", ACROSS, 1, 0)

As the game server loads the puzzle files it will have to check them for consistency. In addition to the syntactic constraints outlined above, there is an important semantic constraint: each file must correspond to a valid crossword puzzle. In particular, what this means is that if two words intersect, they must intersect at the same letter. The simple example above satisfies that constraint, because the second letter of ‘cat’ and the second letter of ‘mat’ intersect at position (1,1). On the other hand, the puzzle shown below would not be a consistent puzzle because the second letter of ‘cat’ is now on the same cell as the first letter of ‘mat’, but ‘a’ and ‘m’ are not the same letter.

>> "Invalid Puzzle" "A trivial buggy puzzle"
 (cat, "feline companion", DOWN, 0, 0)
 (mat, "lounging place for feline companion", ACROSS, 1, 0)

Your consistency check should also forbid words that overlap in the same direction, so for example, the following puzzle should be illegal.

>> "Bad Overlap" "Puzzle should be rejected because of overlapping words"
 (there, "This word is fine", ACROSS, 0, 0)
 (real, "Illegal overlap with there", ACROSS, 0, 3)
 (starting, "Another example, this word is fine", DOWN, 2, 2)
 (art, "Illegal overlap because this word is contained within the previous word", DOWN, 4, 2)

Additionally, we require all words to be unique, so the same word should not appear twice in the puzzle. The grammar already enforces that words must be in all lowercase and should consist only of letters and hyphens, but no additional characters.

The match corresponds to a puzzle that two players are racing to complete. Each match contains the following:

• A puzzle associated with the match.
• A set of users.
• The state representing what the users have done. The state will include all words that have been entered into the puzzle, the user who entered each word, and whether the word has been confirmed as correct or not; this in addition to any points players have earned or lost. Based on the state, the server must determine whether an action by a player is valid, when the match is over and how many points each user gets.

The rules of the match are relatively simple. At any time, each player is free to enter guesses for any incomplete word in the crossword puzzle. A guess must be consistent with the current state of the puzzle; this means that (a) its length must be of the length required by the puzzle, and (b) it must be consistent with any confirmed words and any words entered by others in the puzzle. If a guess does not satisfy these requirements, it is simply rejected by the server. If a word you enter conflicts with a previous unconfirmed word you entered, the previous word is automatically cleared.

When you enter a consistent word, you will not know for sure whether the word was correct or not until the word is confirmed. The match terminates when all the words in the puzzle are correct, so at that point, all words are automatically confirmed. A word can also be confirmed through a challenge. You can challenge any word you think is wrong by providing what you believe to be the correct word, but in order for a challenge to be considered by the system it has to satisfy some validity constraints: (a) the challenged word was entered by the other player (can’t challenge your own words), (b) challenged word was not already confirmed, (c) your proposed word is different from the word already there, and (d) your proposed word must be of the correct length. An invalid challenge is simply rejected by the system, but a valid challenge can have the following outcomes:

• Word was originally correct, then it gets confirmed as correct and can no longer be challenged or changed. The challenger loses one point for an incorrect challenge.
• Word was originally incorrect, and the challenger was correct. In this case, the challenger gets the word and it gets confirmed. The challenger also gets two bonus points for a correct challenge. An important property of a correct challenge is that a challenge does not have to be consistent with any incorrect words already in the puzzle. Any word that is inconsistent with the correct challenge will be cleared without penalty regardless of who had entered it.
• Word was originally incorrect, but the challenger was also incorrect. In this case, the word is cleared from the board, and the challenger loses one point for an incorrect challenge.

To summarize, a word can get confirmed either 1) when all words in the puzzle have been entered correctly or 2) when an already correct word is challenged or 3) when an incorrect word is challenged and replaced with the correct word.

For any word that you yourself entered, you are free to change the word at any time without penalty before it gets challenged by the other player, but your change must be consistent with any new words entered by others in the puzzle. As with fresh words, existing unconfirmed words entered by you will be cleared if they conflict with the updated word you entered.

For example, consider the cat/mat puzzle shown earlier. Suppose Player 1 incorrectly enters ‘pet’ for word 1. Player 2 may then enter ‘set’ as an incorrect guess for word 2. Player 1 may now realize the first guess was wrong, and want to change it to ‘cat’, but that is no longer possible because it is not consistent with word 2. Player 2 may also realize that ‘set’ was wrong, but Player 2 also cannot change it to ‘mat’ because it’s inconsistent with word 1. So one of the two players must perform a challenge to clear out the other word. If Player 1 challenges word 2 correctly, word 1 will be automatically cleared so either player will be able to enter a new guess.

In contrast, suppose Player 1 enters both ‘pet’ and ‘set’. Player 2 can challenge any of the two words, but Player 1 can simply decide to change ‘pet’ to ‘cat’ and that will now automatically clear word 2.

The game ends when all the cells have their correct letters, and at the end of the match, your score will be the number of correct words under your name plus any points that were added or lost through your challenges.

Words with fully overlapping letters. In some cases, a word may have all of its letters overlapping with other words; for example, consider the below extension of the cat-mat puzzle, with the words ‘car’ and ‘tax’ added to overlap with cat.

After the words ‘car’, ‘mat’ and ‘tax’, all the letters for the word ‘cat’ will be in place, but the word will not be considered as entered until a player actually enters it, at which point, that player will own the word. Note, however, that the game might end without anybody having claimed the word cat, since the game ends when all the cells have their correct letters. Also note that if the same player enters ‘car’ and ‘tax’, for example, but then the same player incorrectly enters ‘bob’ for word 1, the word ‘bob’ will clear the conflicting two words even though they were correct, based on the previously stated rule regarding new words clearing out conflicting unconfirmed words entered by the same player.

If at least one of ‘car’, ‘mat’ and ‘tax’ was entered by another player (or had already been confirmed), however, the inconsistency with that word would prevent you from entering ‘bob’. Finally, suppose Player 1 had entered ‘car’, ‘mat’ and ‘cat’ for words 3, 2 and 1. Now, suppose Player 1 enters ‘bob’ for word ‘4’; that will clear the word ‘cat’, because it conflicts with ‘bob’, but the letters ‘c’ and ‘a’ will remain, because they also belong to ‘car’ and ‘mat’ which do not conflict with ‘bob’.

The rules around challenges are meant to encourage players to quickly disclose their best guess for a word even if unsure. In particular, the players’ ability to change their own words without penalty, and the fact that a challenge never deducts points from the original owner of the word, are both meant to encourage players to put down words as soon as they think they know what the word is, even if they are not sure if their word is correct. However, players are unlikely to benefit from a strategy of “squatting” on a word (adding random text in place of real words just to claim a spot and force the other player into the risk of a challenge) because they would have to craft their random text to be consistent with the puzzle, and they would risk giving their opponent a big bonus when their random text is correctly challenged.

This is when the client first connects to the server.

In this state the client must be asked to enter an ID. If the user provides an ID that is already in use, the user must be asked to provide a new one until a valid ID is provided. At that point, the session transitions to the CHOOSE state. You should have sensible rules for what is allowed as a user id (for example, you probably don’t want to allow tabs or even spaces).

Interface requirements: The canvas must display sufficient instructions for a user who has not read this handout to know what to do at this state. The text box must be able to receive the user ID and validate it when the Enter button is pressed.

In this state, the user is shown both the list of matches and the list of available puzzles, and is given a box to enter a command. The commands can be one of the following:

PLAY Match_ID
NEW Match_ID Puzzle_ID "Description"
EXIT

The PLAY command enters an available match that someone has already created and transitions the session to the PLAY state. Note that the available puzzles should include all the puzzles that were loaded at boot time. In particular, any puzzle should be available to start a new match even if there are players already using that puzzle on a different match.

The NEW command creates a new match and transitions to the WAIT state to wait for another user to join the match. The Match_ID is an identifier that the second player will use to enter this newly created match; the description is a string that will be displayed when displaying the list of available matches. The Puzzle_ID is an identifier for the puzzle you want to use to create the match. You have some flexibility as to how you assign IDs to puzzles. For example, you may decide to just use the name of the puzzle, or to display puzzles with automatically assigned numerical IDs. You should impose some syntactic restrictions on the Match_IDs to make sure they are easy to enter (again, allowing them to have tabs or spaces is probably a bad idea).

Finally, the EXIT command simply terminates the session.

Interface requirements: The canvas must display instructions for the user as well as list the available matches and puzzles. It should be clear to the user how to start a new match or enter an existing one. The interface should also live update to incorporate any new matches that were added after the session transitioned to this state, or to remove any matches that are no longer available either because they already have two players or because they have terminated.

In the WAIT state, the player is waiting for another player to join the match. The only valid command in this state is an EXIT command, which terminates this match and brings the player back to the CHOOSE state (since the match is terminated, it is no longer available for another player to join).

Interface requirements: The canvas must make it clear to the player that they are waiting for another player to join the match and that the only available command is the EXIT command.

In this state, the client interface must now display the match and again provide a text box to enter commands. Each word in the puzzle will have associated with it an id, which the user will use to enter guesses or challenges for the word. In particular, the player can issue the following three commands.

TRY id word
CHALLENGE id word
EXIT

The TRY command is used to enter a guess for a particular id. If the id does not correspond to either an empty word or an un-confirmed word entered by the same user, the command is rejected and an error message is displayed explaining the reason for rejection (i.e. “That word is already confirmed” or “That word was entered by the other player and can only be changed through a challenge”). The CHALLENGE command initiates a challenge that proceeds according to the rules above. Finally, the EXIT command forfeits the match and transitions both players to the SHOW SCORE state. After the match, whether it successfully terminated or was forfeited by one of the players, the interface should transition to the SHOW SCORE state.

Interface requirements: The canvas must display the full crossword puzzle with all the cells and all the words currently filled in, as well as all the questions. The interface should give the user good awareness of the state of the game, including but not limited to: (a) which words were entered by which player, (b) what the id of each word is, (c) how many challenge points each user has, (d) which words have been confirmed. It is important that the interface live update to incorporate any changes to the game from the other player entering or challenging words.

Displays the score of the match until you enter either NEW MATCH, which takes you to the CHOOSE state, or EXIT, which logs you out.

Interface requirements: The canvas must make it clear who won and how many points each player had, as well as instructions on what to do next. Note that games can end in a draw, with both players having the same number of points.