REVERSI (OTHELLO) [20]

Rename reversi_skeleton.c to reversi.c. Then, implement the incomplete functions: checkstate(), canPlayAt(), and numReverseDirection(). Your implementation must follow the design by contract principle. In addition, make your solution fail gracefully in production (i.e., when assertion is disabled).

The code is to read a Reversi game board from standard input, compute the best move for a player, and print the result to standard output. In our case, the best move refers to a move which allows the player to capture the most opponents pieces. If you want to learn more about the game, you can read the Wikipedia entry (https://en.wikipedia.org/wiki/Reversi); I have listed the game rules that you need for this assignment.

there are two players, black and white

each player can only play at the place where they capture the opponents piece(s)

when a piece placed, we check if there are opponents pieces wrapped by the players

o we check 8-direction (4 straights, up, down, left, right; and 4 diagonals, left-up, left-down, right-up, right-down) by moving along on this direction

o if we found the players piece along the way, the opponents pieces in between are captured and becomes the players

we get the number of captures for a specific position by adding every directions captures

Implementation Requirements

All following conditions must be met by your solution

void checkstate( const GameBoard * board )

This function should check if the given board is valid. Our valid state means

nColumns is (0, MAX_BOARD_COLUMNS), i.e., 0 < nColumns < MAX

nRows is (0, MAX_BOARD_ROWS), i.e., 0 < nRows < MAX

player is either BLACK or WHITE

boolean canPlayAt( const GameBoard * board, int row, int col )

This function should check if the opponents piece is around given position (i.e., check 8-direction). For example, if current player is BLACK, you need to find out if WHITEs piece appears as a neighbour.

int numReverseDirection( const GameBoard * board, int row, int col, int dirRow, int dirCol )

This function should count and return the number of opponents pieces which are wrapped in between players. At the given column and row, the players piece is played. You must move toward the given direction [-1, 1] to count the opponent pieces. If you could not find the players piece along the given direction, the count should be zero.

BONUS [1]

If you completed this bonus question, write a note for a marker in the readme file. For this bonus, update the readGameBoard() routine to handle any error in input. The correct input format is

first line is the boards title

second line contains three space separated items

o first item is the number of columns

o second item is the number of rows

o third item is either B or W which indicates whos the player is

from third line, the board presents

o each line represents each row of the board

o each character on a line represents each column of the board

o each cell is B, W, or space character

at the end, there is an empty line

Your updated function must be able to detect incorrect input format and return false. Use assertions to follow the design by contract principle and help you to debug. In addition, use safeguard to gracefully fail the process in production. You can write any helper functions.

reversi_skeleton.c :

#include #include #include #include

//------------------------------------------------------------------------------ // CONSTANTS AND TYPES //------------------------------------------------------------------------------ #define LINE_MAX 512 #define MAX_BOARD_COLUMNS 26 #define MAX_BOARD_ROWS 26 #define MAX_BOARD_TITLE LINE_MAX #define PLAY_BOARD_COLUMNS 8 #define PLAY_BOARD_ROWS 8

typedef enum { false, true } boolean;

typedef enum { NONE, BLACK, WHITE }GameBoardCell;

typedef struct { int nColumns; int nRows; GameBoardCell player; // who can move next GameBoardCell state[MAX_BOARD_ROWS][PLAY_BOARD_COLUMNS]; char title[MAX_BOARD_TITLE]; }GameBoard;

//------------------------------------------------------------------------------ // PROTOTYPES //------------------------------------------------------------------------------ //-------------------------------------------------- // checkstate // PURPOSE: Check if the given board is valid // INPUT PARAMETERS: // [board] Game board to check // OUTPUT PARAMETERS: // [boolean] True if valid; otherwise, false //-------------------------------------------------- boolean checkstate( const GameBoard * board );

//-------------------------------------------------- // computeBestMove // PURPOSE: Read one board from standard input and compute a player's best move // INPUT PARAMETERS: // OUTPUT PARAMETERS: // [boolean] True if succeeded; otherwise, false //-------------------------------------------------- boolean computeBestMove( );

//-------------------------------------------------- // canPlayAt // PURPOSE: Check if current player perhaps be able to play at the given row and column // INPUT PARAMETERS: // [board] Game board to check // [row] Cell row position to check playability // [col] Cell column position to check playability // OUTPUT PARAMETERS: // [boolean] True if possibly playable; otherwise, false // REMARKS: The function may return true if the cell is possibly playable. // To check if cell is indeed playable, after this, the caller must make sure that // there will be at least one piece which will be reversed by playing at this cell. //-------------------------------------------------- boolean canPlayAt( const GameBoard * board, int row, int col );

//-------------------------------------------------- // numAllReverse // PURPOSE: Find out all number of reverses by playing at the given position // INPUT PARAMETERS: // [board] Game board to check // [row] Cell row position // [col] Cell column position // OUTPUT PARAMETERS: // [int] Total number of reverses caused by playing at the given position //-------------------------------------------------- int numAllReverse( const GameBoard * board, int row, int col );

//-------------------------------------------------- // numReverseDirection // PURPOSE: Find out all number of reverses from the given position toward the given direction // INPUT PARAMETERS: // [board] Game board to check // [row] Cell row position // [col] Cell column position // [dirRow] Row direction to check reverses [-1, 1] // -1 for moving above, 0 for no move, 1 for moving below // [dirCol] Column direction to check reverses [-1, 1] // -1 for moving left, 0 for no move, 1 for moving right // OUTPUT PARAMETERS: // [int] Total number of reverses caused by playing at the given location toward the direction //-------------------------------------------------- int numReverseDirection( const GameBoard * board, int row, int col, int dirRow, int dirCol );

//-------------------------------------------------- // readGameBoard // PURPOSE: Read a game board from standard input // INPUT PARAMETERS: // [board] Board to store the information // OUTPUT PARAMETERS: // [boolean] True if no error occurred; otherwise, false // REMARKS: Input must have the board's title on the first line, // number of columns, number of rows, and current player ('B' or 'W') on the second (space as a delimiter), // the board's row on each line (' ' for NONE, 'B' for BLACK, and 'W' for WHITE) // and an empty line at the end. //-------------------------------------------------- boolean readGameBoard( GameBoard * board );

//-------------------------------------------------- // printBoard // PURPOSE: Print board in pretty format // INPUT PARAMETERS: // [board] Game board to print //-------------------------------------------------- void printBoard( const GameBoard * board );

//-------------------------------------------------- // printBoardColumnName // PURPOSE: Print board's column head. Support function for printBoard() // INPUT PARAMETERS: // [nColumns] The number of columns for the currently printing board //-------------------------------------------------- void printBoardColumnName( int nColumns );

//-------------------------------------------------- // printBoardRowSeparator // PURPOSE: Print board's row separator. Support function for printBoard() // INPUT PARAMETERS: // [nColumns] The number of columns for the currently printing board //-------------------------------------------------- void printBoardRowSeparator( int nColumns );

//------------------------------------------------------------------------------ // VARIABLES //------------------------------------------------------------------------------

//------------------------------------------------------------------------------ // FUNCTIONS //------------------------------------------------------------------------------ //------------------------------------------------------ // main // PURPOSE: Application entry point. // INPUT PARAMETERS: // OUTPUT PARAMETERS: // [int] Application exit code. //------------------------------------------------------ int main( void ) { while( computeBestMove( ) ) { printf( "================================================================================ " ); printf( " " ); } printf( " *** END OF PROCESSING *** " ); return EXIT_SUCCESS; }

boolean checkstate( const GameBoard * board ) { // TODO: COMPLETE THIS ROUTINE return true; }

boolean computeBestMove( ) { GameBoard board; int col, row; int bestCol = -1; int bestRow = -1; int bestReverse = 0; int currReverse = 0; boolean success = false;

if( readGameBoard( &board ) ) { printBoard( &board ); for( row = 0; row < board.nRows; row++ ) { for( col = 0; col < board.nColumns; col++ ) { if( canPlayAt( &board, row, col ) ) { board.state[row][col] = board.player; // play the piece currReverse = numAllReverse( &board, row, col ); board.state[row][col] = NONE; // revert our last change if( currReverse > bestReverse ) { bestCol = col; bestRow = row; bestReverse = currReverse; } } } } printf( " " ); printf( "The best move for %s is (%c, %d), which will reverse %d opponent piece(s) ", WHITE == board.player ? "WHITE" : "BLACK", bestCol + 'a', bestRow + 1, bestReverse ); printf( " " ); success = true; } return success; }

boolean canPlayAt( const GameBoard * board, int row, int col ) { // TODO: COMPLETE THIS ROUTINE return false; }

int numAllReverse( const GameBoard * board, int row, int col ) { int count = 0;

if( checkstate( board ) ) { assert( 0 <= row && row < board->nRows ); assert( 0 <= col && col < board->nColumns ); assert( board->state[row][col] == board->player );

if( 0 <= row && row < board->nRows && 0 <= col && col < board->nColumns && board->state[row][col] == board->player ) { // we could make following statements to one; however, this is easier to step-in in debugger count += numReverseDirection( board, row, col, -1, -1 ); count += numReverseDirection( board, row, col, -1, 0 ); count += numReverseDirection( board, row, col, -1, 1 ); count += numReverseDirection( board, row, col, 0, -1 ); count += numReverseDirection( board, row, col, 0, 1 ); count += numReverseDirection( board, row, col, 1, -1 ); count += numReverseDirection( board, row, col, 1, 0 ); count += numReverseDirection( board, row, col, 1, 1 ); } } return count; }

int numReverseDirection( const GameBoard * board, int row, int col, int dirRow, int dirCol ) { // TODO: COMPLETE THIS ROUTINE return 0; }

boolean readGameBoard( GameBoard * board ) { char line[LINE_MAX]; char player = 0; int length = 0; int col, row; boolean success = false;

assert( NULL != board ); if( NULL != board ) { memset( board, 0, sizeof( GameBoard ) ); // initialization

fgets( board->title, MAX_BOARD_TITLE, stdin ); length = strlen( board->title ); if( length > 0 && board->title[length - 1] == ' ' ) { // remove board->title[length - 1] = '\0'; }

fgets( line, MAX_BOARD_TITLE, stdin ); sscanf( line, "%d %d %c", &board->nColumns, &board->nRows, &player ); board->player = 'W' == player ? WHITE : BLACK; // who will play next?

for( row = 0; NULL != fgets( line, LINE_MAX, stdin ) && row < board->nRows; row++ ) { // by putting read line first, we discard the last empty line for( col = 0; '\0' != line[col] && col < board->nColumns; col++ ) { switch( line[col] ) { case 'B': board->state[row][col] = BLACK; break; case 'W': board->state[row][col] = WHITE; break; case ' ': default: board->state[row][col] = NONE; break; } } } success = row > 0 && row >= board->nRows && checkstate( board ); } return success; }

void printBoard( const GameBoard * board ) { int col, row;

if( checkstate( board ) ) { printf( "%s ", board->title ); printBoardColumnName( board->nColumns ); printBoardRowSeparator( board->nColumns ); for( row = 0; row < board->nRows; row++ ) { printf( "%2d|", row + 1 ); for( col = 0; col < board->nColumns; col++ ) { switch( board->state[row][col] ) { case BLACK: printf( "B|" ); break; case WHITE: printf( "W|" ); break; default: printf( " |" ); break; } } printf( "%-2d ", row + 1 ); printBoardRowSeparator( board->nColumns ); } printBoardColumnName( board->nColumns ); } }

void printBoardColumnName( int nColumns ) { int col;

assert( nColumns > 0 ); assert( nColumns < MAX_BOARD_COLUMNS ); printf( " " ); for( col = 0; col < nColumns; col++ ) { printf( "%c ", 'a' + col ); } printf( " " ); }

void printBoardRowSeparator( int nColumns ) { int col;

assert( nColumns > 0 ); assert( nColumns < MAX_BOARD_COLUMNS ); printf( " +" ); for( col = 0; col < nColumns; col++ ) { printf( "-+" ); } printf( " " ); }

test_in :

TEST BOARD 1 4 4 W BBBB WB WBB WBB TEST BOARD 2 8 8 B BW WB TEST BOARD 3 8 8 W BW WB TEST BOARD 4 8 8 B W WW WWWWWB WWWW B WWW B 

test_out :

TEST BOARD 1 a b c d +-+-+-+-+ 1|B|B|B|B|1 +-+-+-+-+ 2|W|B| | |2 +-+-+-+-+ 3|W|B|B| |3 +-+-+-+-+ 4| |W|B|B|4 +-+-+-+-+ a b c d The best move for WHITE is (d, 3), which will reverse 2 opponent piece(s) ================================================================================ TEST BOARD 2 a b c d e f g h +-+-+-+-+-+-+-+-+ 1| | | | | | | | |1 +-+-+-+-+-+-+-+-+ 2| | | | | | | | |2 +-+-+-+-+-+-+-+-+ 3| | | | | | | | |3 +-+-+-+-+-+-+-+-+ 4| | | |B|W| | | |4 +-+-+-+-+-+-+-+-+ 5| | | |W|B| | | |5 +-+-+-+-+-+-+-+-+ 6| | | | | | | | |6 +-+-+-+-+-+-+-+-+ 7| | | | | | | | |7 +-+-+-+-+-+-+-+-+ 8| | | | | | | | |8 +-+-+-+-+-+-+-+-+ a b c d e f g h The best move for BLACK is (e, 3), which will reverse 1 opponent piece(s) ================================================================================ TEST BOARD 3 a b c d e f g h +-+-+-+-+-+-+-+-+ 1| | | | | | | | |1 +-+-+-+-+-+-+-+-+ 2| | | | | | | | |2 +-+-+-+-+-+-+-+-+ 3| | | | | | | | |3 +-+-+-+-+-+-+-+-+ 4| | | |B|W| | | |4 +-+-+-+-+-+-+-+-+ 5| | | |W|B| | | |5 +-+-+-+-+-+-+-+-+ 6| | | | | | | | |6 +-+-+-+-+-+-+-+-+ 7| | | | | | | | |7 +-+-+-+-+-+-+-+-+ 8| | | | | | | | |8 +-+-+-+-+-+-+-+-+ a b c d e f g h The best move for WHITE is (d, 3), which will reverse 1 opponent piece(s) ================================================================================ TEST BOARD 4 a b c d e f g h +-+-+-+-+-+-+-+-+ 1| | | | |W| | | |1 +-+-+-+-+-+-+-+-+ 2| | | | |W|W| | |2 +-+-+-+-+-+-+-+-+ 3| | |W|W|W|W|W|B|3 +-+-+-+-+-+-+-+-+ 4| | |W|W|W|W| |B|4 +-+-+-+-+-+-+-+-+ 5| | |W|W|W| | |B|5 +-+-+-+-+-+-+-+-+ 6| | | | | | | | |6 +-+-+-+-+-+-+-+-+ 7| | | | | | | | |7 +-+-+-+-+-+-+-+-+ 8| | | | | | | | |8 +-+-+-+-+-+-+-+-+ a b c d e f g h The best move for BLACK is (b, 3), which will reverse 5 opponent piece(s) ================================================================================ *** END OF PROCESSING ***