//----------------------------------------------------------------------- // File: rings.cpp // Description: Solve the Rings game // Author: Dave Mount (mount@cs.umd.edu) // Date: Feb 2003 // // This program is given an instance (a,b,c) of the rings game, // played by two players, Bilbo and Frodo. It determines which // player has a winning strategy. Here are the rules: // // Bilbo and Frodo alternate moves, with Bilbo going first. // Initially the board consists of three piles of rings which we // denote (a,b,c), which means that there are a rings in the first // pile, b in the second pile, and c in the third. The board // always consist of three numbers that are greater than or equal // to 0. During a move a player can do any one of the following: // // (1) Remove 1 ring from pile 1. // (2) Remove either 1 or 2 rings from pile 2. // (3) Remove either 1 or 2 or 3 rings from pile 3. // (4) Remove one ring each from all of the nonempty piles. // // The first player who cannot make a move loses. That is, if it // is a players turn to move and the board is (0,0,0) then he // loses. // // The input consists of a sequence of triples of integers, // separated by whitespace. The program reads the triple and // outputs the winner. The program is terminated by end of file or // the triple "0 0 0". // // NOTE: There is a trapdoor for debugging purposes. An input // containing a negative value toggles the debugging flag. When in // the debugging mode, the entire table contents are printed. (The // meaning of the entries is described below.) //----------------------------------------------------------------------- #include // standard library #include // input/ouput #include // assertion checking // Uncomment the following lines if using APCS classes // #include "apvector.h" // #include "apmatrix.h" // #include "apstack.h" // #include "apqueue.h" // #include "apstring.cpp" // #include "apstring.cpp" //----------------------------------------------------------------------- // Rings // The state of the game is complete described by the board, which // is given by three numbers (a,b,c). We model all possible boards // using a 3-dimensional string move array, M, where M[a,b,c] is // "L" if Bilbo has no winning strategy, and otherwise M[a,b,c] is // equal to either "11", "21", "22", "31", "32", "33", or "4" // depending on what Bilbo's first move should be. The first // character signifies the rule being applied and the second gives // the number of rings involved. For example, move "32" means // that Bilbo should use rule (3) to remove 2 rings from pile 3. // // Note that this is actually much more than the problem requires. // (It would have been sufficient to store either true or false.) // However, the additional information allows us to determine // Bilbo's moves at each step. //----------------------------------------------------------------------- const int MAX_A = 100; // max rings per pile const int MAX_B = 100; const int MAX_C = 100; bool debugFlag = false; // true if in debugging mode class Rings { private: char M[MAX_A+1][MAX_B+1][MAX_C+1]; // array of moves protected: // utilities char getM(int a, int b, int c); // access an entry of M char bestMove(int a, int b, int c); // determines best move char * showMove(char c); // decode actual move public: Rings() { }; // default constructor bool bilboWins(int a, int b, int c); // returns true if Bilbo wins }; //----------------------------------------------------------------------- // getM - index array M with error checking // If the subscripts are out of bounds, the value "X" is returned, // and otherwise the contents of M are returned. //----------------------------------------------------------------------- char Rings::getM(int a, int b, int c) { if ((a < 0 || a > MAX_A) || // out of bounds? (b < 0 || b > MAX_B) || (c < 0 || c > MAX_B)) return 'X'; // any nonempty value works here else return M[a][b][c]; } //----------------------------------------------------------------------- // showMove - decode character representation of move //----------------------------------------------------------------------- char * Rings::showMove(char c) { switch (c) { case 'a': return("11"); case 'b': return("21"); case 'c': return("22"); case 'd': return("31"); case 'e': return("32"); case 'f': return("33"); case 'g': return("4"); case 'L': return("L"); } cout << "ERROR, illegal code " << c << endl; return "ERROR"; } //----------------------------------------------------------------------- // bilboWins - determines whether Bilbo wins // Constructs the move array M in bottom-up fashion, by invoking // bestMove() for each entry. //----------------------------------------------------------------------- bool Rings::bilboWins(int aa, int bb, int cc) { assert (aa >= 0 && aa <= MAX_A && // check that parameters are in bounds bb >= 0 && bb <= MAX_B && cc >= 0 && cc <= MAX_C); for (int a = 0; a <= aa; a++) { for (int b = 0; b <= bb; b++) { for (int c = 0; c <= cc; c++) { M[a][b][c] = bestMove(a, b, c); if (debugFlag) { // output if degbugging cout << "M[" << a << "," << b << "," << c << "] = " << showMove(M[a][b][c]) << endl; } } } } return M[aa][bb][cc] != 'L'; } //----------------------------------------------------------------------- // bestMove // Determines Bilbo's best move given the board (a,b,c). Bilbo // wins if and only if he can force Frodo into a nonwinning // position. A nonwinning position is indicated by M(a,b,c)="L". // Thus, it suffices to determine whether from the current // configuration we can apply a rule which moves us to a // configuration (a',b',c') such that M[a',b',c'] == "L". If so, we // force Frodo into a loosing configuration by making this rule. // // We check all possible configurations that are reachable from // (a,b,c). For example, an application of rule 1 maps us to // configuration (a-1,b,c). // // Observe that an illegal move results in a negative subscript. // To avoid the need to check for negative subscripts, instead of // accessing M directly, we have a utility getM(), which accesses M // if the indices are in bounds and otherwise returns a nonempty // string. (Since we are looking for an empty string, we will // never select a nonempty string, and hence never select an // illegal move.) //----------------------------------------------------------------------- inline int max(int x, int y) { return (x > y ? x : y ); } char Rings::bestMove(int a, int b, int c) { if (a == 0 && b == 0 && c == 0) return 'L'; else if (getM(a-1, b, c ) == 'L') return 'a'; else if (getM(a, b-1, c ) == 'L') return 'b'; else if (getM(a, b-2, c ) == 'L') return 'c'; else if (getM(a, b, c-1) == 'L') return 'd'; else if (getM(a, b, c-2) == 'L') return 'e'; else if (getM(a, b, c-3) == 'L') return 'f'; else if (getM(max(0,a-1), max(0,b-1), max(0,c-1)) == 'L') return 'g'; else return 'L'; } //----------------------------------------------------------------------- // playRings // Plays the game and outputs the winner. // // The program has a "trap door". If any of the arguments is // negative, the program toggles its debug mode, which causes the // entire table of moves to be printed for all future games. //----------------------------------------------------------------------- void playRings(int a, int b, int c) { Rings R; if (a < 0 || b < 0 || c < 0) { cout << "Toggling debug mode" << endl; debugFlag = !debugFlag; } else { cout << a << " " << b << " " << c << " "; if (R.bilboWins(a, b, c)) cout << "Bilbo wins" << endl; else cout << "Frodo wins" << endl; } } //----------------------------------------------------------------------- // main // Reads inputs and calls playRings() to determine actual winner. // // THIS CAN BE PROVIDED TO THE CONTESTANTS. //----------------------------------------------------------------------- int main() { int a, b, c; while (true) { cin >> a >> b >> c; if (!cin || (a == 0 && b == 0 && c == 0)) exit(0); playRings(a, b, c); } return 0; }