The Game of Nim - Step 4

◀ The Game of Nim - Step 3▶ Exercise #3: Solve The Eight Queens Puzzle Amazon Let’s apply the final step of the Four-Step Programming Model to solve the game of Nim!

Four Step Programming Model: Step 4
Here is a complete program following the above skeleton:

/*
Michael Wen
6/5/2003
This program plays a game of Nim with the user.
*/
#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;

bool deadNum(int);
int compute(int);
const int MAX = 91;
const int MIN = 13;

int main() {  
	int size, whoseTurn, compTakeOff, youTakeOff, mode;

/* initialize random number generator */
	srand(time(0));
/* introduce the game of Nim and display its rules */
	cout << "\n****** Welcome to the game of Nim ******\n";
	cout << "The number of marbles you draw must be > 0 and <= half of the 			total marbles.\n";
	cout << "The person who gets the last marble loses.\n\n";

/* determine who goes first and the initial number of marbles */
	whoseTurn = rand() % 2;
	if(whoseTurn==0)
		cout << "Computer goes first.\n";
	else
	    cout << "You go first.\n";
	size = MIN + rand() % (MAX-MIN);
	cout << "Initial number of marbles: " << size << endl;
	mode = rand() % 2;

/* deal with the case when computer plays stupid */	
	if (mode==0) {
		cout << "The computer is playing stupid.\n";
	   
 	    while (size!=1) {
			if (whoseTurn==0) {
/* draw a random legal number of marbles */
				compTakeOff = 1 + rand() % (size / 2);
		    	size -= compTakeOff;
cout << "Computer takes off " << compTakeOff << 
" marble(s).\n";
cout << "Current number of marble(s): " << size << 	"\n\n";
			}
			else {
/* prompt user to enter a number */
				do {   
					cout << "Enter number of marble(s) to draw: ";
					cin >> youTakeOff;
		    	} while(youTakeOff<=0 || youTakeOff>size/2);
	 	    	size -= youTakeOff;
                cout << "Current number of marble(s): " << size << "\n\n";
			}
			whoseTurn = whoseTurn==0 ? 1 : 0;
	    }   
    }
/* deal with the case when computer plays smart */	
	else {
		cout << "The computer is playing smart.\n";
	    while (size!=1) {
	   		if (whoseTurn==0) {
		 		if (deadNum(size)) {
/* draw a random legal number of marbles */
		   			compTakeOff = 1 + rand() % (size / 2);
		    		size -= compTakeOff;
		    		cout << "Computer takes off " << compTakeOff;
					cout << " marble(s).\n";
		    		cout << "Current number of marble(s): " << size 							<< "\n\n";
		    	}
		    	else {
/* use the strategy */
					compTakeOff = compute(size);
		        	size -= compTakeOff;
		        	cout << "Computer takes off " << compTakeOff;
cout << " marble(s).\n";
                    cout << "Current number of marble(s): " << size 							<< "\n\n";
		    	}
			}
			else {
				do {
		    		cout << "Enter number of marble(s) to draw: ";
					cin >> youTakeOff;
		    	} while (youTakeOff <= 0 || youTakeOff > size / 2);
		    	size -= youTakeOff;
cout << "Current number of marble(s): " << size << 	"\n\n";
			}
			whoseTurn = whoseTurn==0 ? 1 : 0;
		}
	}
	if (whoseTurn == 1)
		cout << "The computer wins!" << endl;
	else
		cout << "You win!" << endl;
    	return 0;
}

/*
precondition: n should be a positive integer
postcondition: return true if n is 1 less than any power of 2; return false otherwise
*/
bool deadNum(int n) {
	int i = -1;
	while((int)pow(2.0,++i) < n)
;
	return ((int)pow(2.0, i)==n+1);
}

/*
precondition: n should be a positive integer 
postcondition: return the number of marbles smart computer should draw
*/
int compute(int n) {
	int i = -1;
	while((int)pow(2.0,++i) < n)
;
	i--;
	return n - ((int)pow(2.0, i) - 1);
}

After we run it a couple of times, it seems to work perfectly when computer is playing stupid. It, however, does not work property when computer is playing smart. When the current number of marbles is down to 2 and it’s computer’s turn, it takes away 2 marbles.

Let's debug!
You can insert several print statements before each function call and you will find that compute() is responsible for this bug. If n is 2, i turns out to be 1, and i-- gives 0. So the function returns 2, and computer draws 2 marbles.

This function does not work when n equals 2. Let’s fix it by simply handling it as an exception. Here is the new version of compute():

/*
preconditions: n should be a positive integer 
postconditions: returns the number of marbles smart computer should draw
exceptions: when n is 2, return 1
*/
int compute(int n) {
	if(n==2)
		return 1;
	int i = -1;
	while((int)pow(2.0,++i) < n)
;
	i--;
	return n - ((int)pow(2.0, i) - 1);
}

Now everything works perfectly; however, this program contains redundant code, so it’s possible to reduce its code size. Your program could be shorter and cleaner than mine.

Note that the program does not do any error checking.
If you enter a letter when a number is expected, the program runs into a loop. You can fix it by using <stdlib.h>’s atoi() to convert a char array to an int. If atoi() returns 0, then either an error has occurred or the user enters 0.

You will have plenty of opportunities to sharpen your error-checking skills in the coming programming exercises.

Next let’s solve a world famous puzzle - the eight queen’s puzzle!
◀ The Game of Nim - Step 3▶ Exercise #3: Solve The Eight Queens Puzzle