#include  #include  #include  #include  #include  using namespace std; /** * A cookie in the game of chomp. A cookie is begins as * a rectangular arrangement of "crumbs". We can then take * bites at specific locations. A byte at (x,y) eliminates the * crumb at that location and all crumbs below and to the right. * For example, given a cookie * %%%% * %%%% * %%%% * %%%% * a bite at (1,2) would leave: * %%%% * %%%% * % * % * after which, a second bite at (2,1) would leave * %%%% * %% * % * % */ struct Cookie { int initialNumberOfRows; /// Number of rows currently remaining in the cookie int numberOfRows; /// Number of columns currently remaining in the cookie int numberOfColumns; /** * The "shape" of the cookie. * * If crumbs[i] == j, then the cookie currently * has crumbs filling the j columns at row i */ int* crumbs; }; struct Player { std::string name; int numGamesWon; }; struct Game { /// The cookie for this game. Cookie cookie; }; Player computer = {"computer", 0}; Player human = {"", 0}; /** * Number of non-empty rows currently remaining in the cookie * (value decreases as we continue to take bites) * * @param cookie the cookie * @return number of non-empty rows in the cookie */ int getNumberOfRows(const Cookie& cookie); /** * The number of rows remaining in a specific column * @param cookie the cookie * @param colNum a column number in the cookie * @return number of non-empty rows remaining in that column */ int getNumberOfRows(const Cookie& cookie, int colNum); /** * Number of non-empty columns currently remaining in the cookie * @param cookie the cookie * @return number of non-empty columns */ int getNumberOfColumns(const Cookie& cookie); /** * The number of columns remaining in a specific row * @param cookie a cookie * @param rowNum a row * @return number of non-empty columns in that row */ int getNumberOfColumns(const Cookie& cookie, int rowNum); /** * Determines if a proposed bite by the computer player could allow * a skillful opponent to force a loss. * * @param cookie current cookie * @param column column of porposed bite * @param row row of proposed byte * @return true if choosing this bite could lead to a forced loss */ bool isADangerousMove (Cookie& cookie, int column, int row); /** * Remove the crumb at the indicated position and * all crumbs below and to the right of that position. * @param cookie cookie from which we want to take a bite * @param column column of desired bite * @param row row of desired biete */ void takeABite (Cookie& cookie, int column, int row); /** * Check a proposed move to see if it is legal. * A legal move must bite at least one remaining crumb. * * @param g a game * @param column x position of the desred bite * @param row y position of the desired bite * @return true iff this move is legal */ bool biteIsLegal (const Game& g, int column, int row) { return (column >= 0) && (row >= 0) && row < getNumberOfRows(g.cookie) && (column < getNumberOfColumns(g.cookie,row)); } /** * Release storage held by this cookie * * @param cookie cookie that is no longer needed */ void cleanUpCookie(Cookie& cookie) { delete [] cookie.crumbs; } /** * Release any storage held by a game * * @param g a no-longer-needed game */ void cleanUpGame (Game& g) { cleanUpCookie(g.cookie); } /** * Determines if the only legal move for the computer player * is to bite the poison. * * @param cookie current cookie * @param column proposed move - set to 0 if unavoidable * @param row proposed move - set to 0 if unavoidable * @param maxColumns original number of columns in the cookie * @param lastNonEmptyRow highest numbered row containing a non-empty column * @return true iff the computer player has to bite the poison */ bool computerPlayerMustLose (Cookie& cookie, int& column, int& row, int maxColumns, int lastNonEmptyRow) { if (getNumberOfColumns(cookie,0) == 1 && getNumberOfColumns(cookie,1) == 0) { // We have to bite the poison crumb. column = row = 0; return true; } return false; } /** * Determine if there is a move that can allow the computer player to * force a win. * @param cookie the cookie * @param column output - column of the win-forcing move * @param row output - row of the win-forcing move * @param maxColumns remaining columns in this cookie * @param lastNonEmptyRow highest numbered row that contains non-empty columns * @return true iff a move has been found that allows the computer to force a win */ bool computerPlayerCanForceAWin (Cookie& cookie, int& column, int& row, int maxColumns, int lastNonEmptyRow) { // We can force a win if there is only one row and that has // more than one column if (getNumberOfRows(cookie) == 1 && getNumberOfColumns(cookie,0) > 1) { column = 1; row = 0; return true; } // Or if there is only one column and that has more than one row if (getNumberOfColumns(cookie) == 1 && getNumberOfRows(cookie) > 1) { column = 0; row = 1; return true; } // If row 0 is the only row with more than 1 column, and // column 0 is the only column with more than 1 row, and the number of // elements in each are different, then we can force an eventual win // by evening them up. if (getNumberOfRows(cookie) != getNumberOfColumns(cookie) && getNumberOfRows(cookie) > 1 && getNumberOfColumns(cookie) > 1 && getNumberOfColumns(cookie,1) == 1) { if (getNumberOfRows(cookie) > getNumberOfColumns(cookie)) { column = 0; row = getNumberOfColumns(cookie); } else { row = 0; column = getNumberOfRows(cookie); } return true; } // More subtly, if we are down to two rows and the number of columns // in each is different, we can force an eventual win by evening them // up. if (getNumberOfRows(cookie) == 2 && getNumberOfColumns(cookie,0) != getNumberOfColumns(cookie,1)) { row = 0; column = getNumberOfColumns(cookie,1); return true; } // Or, if we are down to two columns and the number of rows // in each is different, we can force an eventual win by evening them // up. if (getNumberOfColumns(cookie) == 2 && getNumberOfColumns(cookie,getNumberOfRows(cookie)-1) == 1) { column = 0; row = 1; while (getNumberOfColumns(cookie,row) == 2) ++row; return true; } // If none of those are true, no obvious way to force a win return false; } /** * Display the cookie on the indicated output stream * @param output where to show the cookie * @param cookie the cookie to be shown */ void display (std::ostream& output, const Cookie& cookie) { // Print top line with numeric index of columns output << ' '; for (int col = 0; col < cookie.numberOfColumns; ++ col) output << (col % 10); output << endl; // Print each row, preceded by a numeric row index for (int row = 0; row < cookie.numberOfRows; ++row) { output << (row % 10); for (int col = 0; col < cookie.crumbs[row]; ++col) if (row == 0 && col == 0) output << "P"; // (poison) else output << "*"; output << endl; } } /** * Check to see if the current game has been ended * (i.e., has someone eaten the poison crumb?) * * @param g the game * @return true iff the poison has been eaten */ bool gameEnded(const Game& g) { return getNumberOfColumns(g.cookie) <= 0; } /** * Get the computer player's next move for this game. * * @param cookie cookie from which to choose the next move * @param x x/column location of the next bite * @param y y/row location of the next bite */ void getComputerPlayerMove (Cookie& cookie, int& column, int& row) { // Collect some basic info about the shape of the cookie int maxColumns = getNumberOfColumns(cookie,0); int lastNonEmptyRow = -1; for (int r = 0; r < getNumberOfRows(cookie); ++r) { if (getNumberOfColumns(cookie,r) > maxColumns) maxColumns = getNumberOfColumns(cookie,r); if (getNumberOfColumns(cookie,r) > 0) lastNonEmptyRow = r; } // If we can force a win, do it. if (computerPlayerCanForceAWin(cookie, column, row, maxColumns, lastNonEmptyRow)) { cout << "You're not going to like this..." << endl; return; } // If we are forced to lose, so be it. if (computerPlayerMustLose(cookie, column, row, maxColumns, lastNonEmptyRow)) { cout << "Alas!" << endl; return; } // Otherwise, choose a random move, but try to find one // that is not obviously dangerous; cout << "Hmm..." << endl; const int LIMIT = 10; row = rand() % lastNonEmptyRow; column = rand() % getNumberOfColumns(cookie,row); for (int attempt = 0; attempt < LIMIT && isADangerousMove(cookie, column, row); ++attempt) { row = rand() % lastNonEmptyRow; column = rand() % getNumberOfColumns(cookie,row); } } void getHumanPlayerMove (Cookie& cookie, int& column, int& row) { cout << "Your turn to take a bite from the cookie. "; cout << "Enter the column number and row number at which "; cout << " you wish to chomp (separated by a blank space): " << flush; cin >> column >> row; if (cin.fail()) { cin.clear(); std::string junk; getline(cin, junk); // discard rest of this input line } } /** * Number of non-empty columns currently remaining in the cookie * @param cookie the cookie * @return number of non-empty columns */ int getNumberOfColumns(const Cookie& cookie) { return cookie.numberOfColumns; } /** * The number of columns remaining in a specific row * @param cookie a cookie * @param rowNum a row * @return number of non-empty columns in that row */ int getNumberOfColumns(const Cookie& cookie, int rowNum) { return cookie.crumbs[rowNum]; } /** * Number of non-empty rows currently remaining in the cookie * (value decreases as we continue to take bites) * * @param cookie the cookie * @return number of non-empty rows in the cookie */ int getNumberOfRows(const Cookie& cookie) { return cookie.numberOfRows; } /** * The number of rows remaining in a specific column * @param cookie the cookie * @param colNum a column number in the cookie * @return number of non-empty rows remaining in that column */ int getNumberOfRows(const Cookie& cookie, int colNum) { int k = 0; while (k < cookie.numberOfRows && cookie.crumbs[k] > colNum) ++k; return k; } /** * Set up a new cookie of random size * @param cookie output - the cookie */ void initCookie(Cookie& cookie) { const int MAXROWS = 10; // Randomply select size of the cookie, between 4 and MAXROWS cookie.initialNumberOfRows = cookie.numberOfRows = 4 + rand() % (MAXROWS - 4); cookie.crumbs = new int[cookie.initialNumberOfRows]; cookie.numberOfColumns = cookie.numberOfRows; while (cookie.numberOfColumns == cookie.numberOfRows) cookie.numberOfColumns = 4 + rand() % (MAXROWS - 4); for (int row = 0; row < cookie.numberOfRows; ++row) cookie.crumbs[row] = cookie.numberOfColumns; } void initHumanPlayer(Player& human) { human.numGamesWon = 0; cout << "Welcome to Chomp! " << "What is your name? " << flush; getline (cin, human.name); cout << "OK, " << human.name << ", let's play." << endl; } /** * Create a new game with a cookie of random size * * @param g newly initialized game */ void initializeGame(Game& g) { initCookie (g.cookie); cout << "The cookie has " << getNumberOfRows(g.cookie) << " rows of " << getNumberOfColumns(g.cookie) << " columns" << endl; } void initPlayer (Player& player, std::string name) { player.name = name; player.numGamesWon = 0; } /** * Determines if a proposed bite by the computer player could allow * a skillful opponent to force a loss. * * @param cookie current cookie * @param column column of porposed bite * @param row row of proposed byte * @return true if choosing this bite could lead to a forced loss */ bool isADangerousMove (Cookie& cookie, int column, int row) { // Always dangerous to eat the poison crumb if (column == 0 && row == 0) return true; // Dangerous to leave only one row or one column unless // it has only one element (the poison) if (column == 0 && row > 1) return true; if (row == 0 && column > 1) return true; // Dangerous to take element (1,1) if the #rows and #cols are equal if (row == 1 && column == 1 && getNumberOfRows(cookie) == getNumberOfColumns(cookie)) return true; // Dangerous to take element (2,0) if the th remaining two rows // are equal length if (row == 2 && column == 0 && getNumberOfColumns(cookie,0) == getNumberOfColumns(cookie,1)) return true; // Dangerous to take element (2,0) if the the remaining two cols // are equal length if (row == 0 && column == 2 && getNumberOfColumns(cookie, getNumberOfRows(cookie)-1) > 1) return true; return false; } /** * Play an entire game * @param game the game with an initialized cookie * @param human human player * @param computer computer player */ void playAGame(Game& game, Player& human, Player& computer) { while (!gameEnded(game)) { display (cout, game.cookie); // First, the human player's move int xBite = -1; int yBite = -1; bool legalMove = false; while (!legalMove) { getHumanPlayerMove (game.cookie, xBite, yBite); legalMove = biteIsLegal (game, xBite, yBite); if (!legalMove) { cout << "Sorry, but that is not a legal move." << endl; } } takeABite (game.cookie, xBite, yBite); if (gameEnded(game)) { ++computer.numGamesWon; cout << "You have eaten the poison crumb! You lose." << endl; } else { // Computer player's move display (cout, game.cookie); getComputerPlayerMove (game.cookie, xBite, yBite); cout << "I will chomp at column " << xBite << ", row " << yBite << "." << endl; takeABite (game.cookie, xBite, yBite); if (gameEnded(game)) { ++human.numGamesWon; cout << "I had to eat the poison crumb. You win!" << endl; } } } } void printScore(Player& human, Player& computer) { cout << "Score\tComputer: " << computer.numGamesWon << "\t" << human.name << ": " << human.numGamesWon << endl; } void printRules() { cout << "Chomp is a game played with a rectangular \"cookie\" made " << "up of square \"crumbs\". "; cout << "Taking turns, each player takes a bite from the cookie, " << "selecting a crumb that is removed from the cookie, together " << "with all crumbs below and to the right of the selected one. "; cout << "The top-left crumb in this cookie is poisoned. The player " << "who eats the poisoned crumb loses the game. " << endl; } /** * Remove the crumb at the indicated position and * all crumbs below and to the right of that position. * @param cookie cookie from which we want to take a bite * @param column column of desired bite * @param row row of desired biete */ void takeABite (Cookie& cookie, int column, int row) { for (int r = row; r < cookie.numberOfRows; ++r) { int c = cookie.crumbs[r]; if (c > column) cookie.crumbs[r] = column; } cookie.numberOfRows = 0; for (int r = 0; r < cookie.initialNumberOfRows && cookie.crumbs[r] > 0; ++r) { cookie.numberOfRows = r + 1; } cookie.numberOfColumns = (cookie.numberOfRows > 0) ? cookie.crumbs[0] : 0; } int main (int argc, char** argv) { // Start the random number generator int seed = 12371; if (argc == 1) seed = time(0); srand (seed); printRules(); bool playAnotherGame = true; while (playAnotherGame) { Game game; initializeGame(game); playAGame(game, human, computer); printScore(human, computer); cout << "Play again? (Y/N) " << flush; string response; playAnotherGame = false; while (response == "" && cin >> response) { if (response[0] == 'Y' || response[0] == 'y' || response[0] == 'N' || response[0] == 'n') playAnotherGame = response[0] == 'Y' || response[0] == 'y'; else response = ""; } cleanUpGame(game); } return 0; } 

Problem Description

Chomp is a simple game (with some surprisingly deep underlying mathematics) described by Martin Gardner in his long-running Mathematical Games column in Scientific American.

Chomp is played with a rectangular cookie made up of square crumbs. Taking turns, each player takes a bite from the cookie, selecting a crumb that is removed from the cookie, together with all crumbs below and to the right of the selected one. The top-left (column 0, row 0) crumb in this cookie is poisoned. The player who eats the poisoned crumb loses the game.

This version of the game pits a human player against the computer. At the start of each game, a randomly sized cookie (maximum of 10 rows and 10 columns) is generated. Beginning with the human, the two players alternate taking bites, with the cookie being redisplayed just before each turn.

As each game is completed, the human is offered the option of quitting or playing again. A running tally of games won by each player is maintained and printed at the end of each game.

Input

This program will read its input from standard in (cin).

The actual format of the input varies from entry to entry, but should be clear from the prompts.

Output

The output of this program mingles a great deal of prompting and commentary with the display of the current state of the cookie. Most of this should be self-explanatory, so the the remainder of this description will concentrate on the cookie display.

The display of the cookie is bounded above and to the left by an index to make it easy for the player to read column and row numbers. The first line of the display consists of a blank space followed by numberOfColumns single-digit integers (ranging from 0 to numberOfColumns-1. This is followed by numberOfRows lines of detail. Each detail line begins with the row number (single-digit integer ranging from 0 to numberOfRows-1) and then as many asterisks (*) as there are crumbs in that row. For example, if 5 crumbs remain in row 1, then the display of that row detail line would be:

1***** 

Example

Here is a sample game transcript:

Chomp is a game played with a rectangular "cookie" made up of square "crumbs". Taking turns, each player takes a bite from the cookie, selecting a crumb that is removed from the cookie, together with all crumbs below and to the right of the selected one. The top-left crumb in this cookie is poisoned. The player who eats the poisoned crumb loses the game. Welcome to Chomp! What is your name? John OK, John, let's play. The cookie has 6 rows of 9 columns 012345678 0P******** 1********* 2********* 3********* 4********* 5********* Your turn to take a bite from the cookie. Enter the column number and row number at which you wish to chomp (separated by a blank space): 4 4 012345678 0P******** 1********* 2********* 3********* 4**** 5**** Hmm... I will chomp at column 0, row 1. 012345678 0P******** Your turn to take a bite from the cookie. Enter the column number and row number at which you wish to chomp (separated by a blank space): 1 0 0 0P Alas! I will chomp at column 0, row 0. I had to eat the poison crumb. You win! Score Computer: 0 John: 1 Play again? (Y/N) n