June 2001 Programmer's Challenge

Dots

Mail solutions to: progchallenge@mactech.com
ExtendedDue Date: 11:59pm ET, Friday, 8 June 2001

You have probably played the game Dots before, although perhaps not in quite some time. My memory of the game dates back to childhood, when we played it in the car while on some long trip. Greg Sadetsky suggested that Dots might make an interesting Challenge, and he wins two Challenge points for that suggestion.

The game starts with a piece of paper with a rectangular grid of NxN dots. The game proceeds with two players alternating turns connecting adjacent dots with a line. Two dots are adjacent if they are in the same row and in adjacent columns, or in the same column and in adjacent rows. The object of the game is to take possession of more squares than does your opponent. Each time a player connects dots that form the fourth edge of a square, the player takes possession of that square. A line can complete zero, one, or two squares. When a player completes one or more squares, s/he must make another move, and continue making additional moves as long as a square is completed with each move. The game continues until every square has been formed.

The prototype for the code you should write is:

typedef struct Dot {
  short row;    /* row number of dot, 0..boardSize-1 */
  short col;    /* column number of dot, 0..boardSize-1 */
} Dot;

typedef struct DotLine {
  Dot dot1;    /* first dot of a line */
  Dot dot2;    /* second dot of a line */
    /*  legal lines are formed by dots in the same row, in adjacent columns,
          or in the same column in adjacent rows */
} DotLine;      

void InitDots(
  short boardSize,    /* number of dots per row/col in board */
  Boolean playFirst,  /* true if you play first, false of opponent plays first */
  WindowPtr dotWindow /* color window where you should draw game results */
);

void OpponentMove(
  const DotLine opponentLine  /* line formed by your opponent on previous move */
);

short /* number of lines generated */ PlayDots(
  DotLine yourLines[]   /* return the lines you form here */
);

void TermDots(void);    /* return any storage you allocated */

Play begins with a call to your InitDots routine, where you are given the size of the game board (boardSize), an indicator of who plays first (playFirst), and a pointer to a CWindow (passed as a WindowPtr because that's what most toolbox routines expect). In that window, you will be required to display the progress of the game as it proceeds.

When it is your turn to move, your PlayDots routine will be called. Your code should select the most advantageous move and return it in yourLines[0]. If that move forms a square, you must select an additional move, store it in yourLines[1], and continue as long as squares are formed. PlayDots should return the number of moves you made during your turn.

After your opponent has played, your OpponentMove routine will be called one or more times, once for each move made by your opponent. The move will be provided in the opponentLine parameter, for use in display and in updating your data structures.

After each of your moves, and after notification of each opponent move, you should display the move and the updated game state in the dotWindow. The window should also display the number of squares completed by each player. The details of the display are left to you, as long as the display is correct.

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".