June 2001 Programmer's Challenge
Dots
Mail solutions to:
progchallenge@mactech.com
ExtendedDue Date: 11:59pm ET, Friday, 8 June 2001
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;
short col; /* column number of dot, 0..boardSize-1 */
} Dot;
typedef struct DotLine {
Dot dot1;
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,
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
);
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.When all of the squares have been formed, your TermDots routine will be called. You should deallocate any dynamically allocated memory and perform any other cleanup required.
The winner will be determined by a round-robin or other fair tournament played with multiple board sizes. Scoring is based on minimizing your point total, calculated as the number of squares that your opponent occupies, plus a penalty of 1% for each millisecond your solution takes to execute.
The Challenge prize will be divided between the overall winner and the best scoring entry from a contestant that has not won the Challenge recently.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 6 environment. Solutions may be coded in C, C++, or Pascal.
