October 1999 Programmer's Challenge

SuperDuperGhost

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm ET, Sundar, 3 October 1999

This month we’re going to play a word game. One derived from a game called GHOST. The basic concept is simple — players spell a word, taking turns adding letters to the growing word, trying to avoid being the player who says the last letter of the word.

To start, one player says a letter. The next player thinks of (but does not reveal) a word that begins with the given letter, and then announces the first two letters of that word. The next player thinks of a (possibly different) word that starts with the first two letters, and announces the first three letters of that word. Play continues until a player spells an entire word that is more than three letters long. The player who completes the word loses the round. If a player spells a string that is not part of a real word, that player loses the round.

A game with three players might go like this:

In our game, there are a few variations. Instead of always adding a letter to the end of the string, we’ll also play games where you can only add to the beginning, games where you can add to the beginning or to the end, and games where you can add a letter anywhere. Our games will also be restricted to two players, with each Challenge contestant competing against each other contestant.

The prototype for the code you should write is:

#if defined(__cplusplus)
extern "C" {
#endif

typedef enum {
  addToEndOnly = 0,
  addToBeginningOnly,
  addToBeginningOrEnd,
  addAnywhere
} GameType;

void InitSuperDuperGhost(
  const char *dictWords[],  /* alphabetically sorted uppercase dictionary words */
  long numDictionaryWords   /* number of null-terminated words in dictionary */
);

void NewGhostGame(
  GameType theGameType
);

void PlayGhost(
  const char *ghostString,  /* the string so far, null-terminated */
  char newGhostString[256], /* new ghostString, one letter added to ghostString */
  int *wordInMindIndex,     /* your string will match dictWords[wordInMindIndex] */
  int charPositions[256]
        /* index into dictWords[wordInMindIndex] for each char in newGhostString */
);

void TermSuperDuperGhost(void);

#if defined(__cplusplus)
}
#endif

The vocabulary for our game consists of numDictionaryWords alphabetically sorted uppercase words provided to your InitSuperDuperGhost routine in the dictWords parameter. The dictionary will typically consist of 40000-50000 words but will never exceed 100000 words. All dictWords will be greater than 3 letters in length. InitSuperDuperGhost should analyze the dictionary and create intermediate tables if appropriate. At the end of the contest, TermSuperDuperGhost will be called, where you should deallocate any dynamic memory allocated by InitSuperDuperGhost.

Each round will consist of each Challenge entry competing against each other entry in a game of each GameType, once playing first and once playing second. Each player will be notified of the start of a new game with a call to NewGhostGame. At each turn, a player’s PlayGhost routine will be called. The null-terminated ghostString parameter will provide the string played thus far in the game, which is guaranteed to be part of some word in dictWords. The PlayGhost routine must add a single character to the ghostString, at the beginning, the end, or anywhere, depending on theGameType parameter to this game, and return the result in newGhostString. PlayGhost must return in wordInMindIndex the index into dictWords of the word matched by newGhostString. To help the test program evaluate your move, you must also set the charPositions array, so that:

         newGhostString[i] = dictWords[wordInMindIndex][charPositions[i]]

The winner of each game wins 100 points. Each player’s score is reduced by 1 point for each 10 milliseconds of execution time, including the time taken by the initialization and termination routines. The Challenge winner will be the player with the most points at the end of the tournament.

If you cannot add a letter to the ghostString without forming a word, you should return a null string in newGhostString. Alternatively, if you form a word in dictWords but return a non-null string, you will be penalized 50 points.

This month’s Challenge was suggested by JG Heithcock, who wins 2 Challenge points for the suggestion. If you have an idea that you think would make a good Challenge problem, send it to progchallenge@mactech.com for possible consideration in a future Challenge.

This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment. Solutions may be coded in C, C++, or Pascal. Solutions in Java will also be accepted this month. Java entries must be accompanied by a test driver that uses the interface provided in the problem statement.

Test code for this Challenge is available.

You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".