#include <iostream.h>
#include <ctype.h>
#include <stdlib.h>


// picks a random number between 0 and "max" inclusive. values
// returned are uniformly distributed (each possible value
// is equally likely).
int pick_random_int_value (int max) {

  // a key point - the 1.0 is a double constant.  this means
  // that "RAND_MAX + 1.0" is double and so on.
  return (int) ((rand() / (RAND_MAX + 1.0)) * (max + 1));

}


// displays instructions for playing the game of Nim
void display_instructions (void) {

  cout << "\nThe game of Nim involves two players and three piles of chips.\n"
       << "The players move alternately.  Each player, in his or her turn,\n"
       << "removes one or more chips from one of the piles.  The player who\n"
       << "removes the last chip wins the game.\n";

}


// returns true if the situation after a move is "safe" (guaranteed
// to produce a win, assuming perfect play)
bool situation_is_safe (int pile1, int pile2, int pile3) {

  // the ^ operator gives a bitwise exclusive OR
  return (pile1 ^ pile2 ^ pile3) == 0;

}


// puts between 10 and 20 (inclusive) chips on each of the three piles
void make_initial_piles (int &pile1, int &pile2, int &pile3) {

  pile1 = 10 + pick_random_int_value(10);
  pile2 = 10 + pick_random_int_value(10);
  pile3 = 10 + pick_random_int_value(10);

}


// displays the current status of the three piles.
void display_piles (int pile1, int pile2, int pile3) {

  cout << "Pile 1: " << pile1 << "  Pile 2: " << pile2
       << " Pile 3: " << pile3 << endl;

}


// removes "chips" chips from pile "pile".
// it is assumed that the move is legal.
void make_move (int &pile1, int &pile2, int &pile3, int pile, int chips) {

  if (pile == 1) {
    pile1 -= chips; return;
  }
  if (pile == 2) {
    pile2 -= chips; return;
  }
  // must be pile 3
  pile3 -= chips;

}


// given the current suituation, selects a computer move.
// it is assumed that there is at least one possible move.
void select_computer_move (int pile1, int pile2, int pile3,
                           int &pile, int &chips) {

  int i;

  // see if we can reach a safe position by removing chips from pile 1
  for (i = 1; i <= pile1; i++) {
    if (situation_is_safe (pile1 - i, pile2, pile3)) {
      pile = 1; chips = i; return;
    }
  }

  // see if we can reach a safe position by removing chips from pile 2
  for (i = 1; i <= pile2; i++) {
    if (situation_is_safe (pile1, pile2 - i, pile3)) {
      pile = 2; chips = i; return;
    }
  }

  // see if we can reach a safe position by removing chips from pile 3
  for (i = 1; i <= pile3; i++) {
    if (situation_is_safe (pile1, pile2, pile3 - i)) {
      pile = 3; chips = i; return;
    }
  }

  // if there are any chips on pile 1, remove 1 chip from this pile
  if (pile1 > 0) {
    pile = 1; chips = 1; return;
  }

  // if there are any chips on pile 2, remove 1 chip from this pile
  if (pile2 > 0) {
    pile = 2; chips = 1; return;
  }

  // there must be chips on pile 3 (see assumption at start of this functioon).
  // remove 1 chip from this pile.
  pile = 3; chips = 1;

}


// obtains a valid human move by repeatedly asking for a move until valid
// input is supplied.  assumes that there is at least one legal move.
void get_human_move (int pile1, int pile2, int pile3, int &pile, int &chips) {

  for (;;) {

    cout << "Please enter pile number and chips to remove: ";
    cin >> pile >> chips;

    if ( (chips > 0) &&
         ( ((pile == 1) && (chips <= pile1)) ||
           ((pile == 2) && (chips <= pile2)) ||
           ((pile == 3) && (chips <= pile3)) ) ) {
      // we have a valid move
      return;
    }

    cout << "**** Invalid pile number or number of chips. ****\n";

  }

}


void play_game (bool computer_to_move) {

  int pile1, pile2, pile3, pile_chosen, chips_removed;

  make_initial_piles (pile1, pile2, pile3);

  // display the initial situation
  cout << "\nInitial Situation:\n";
  display_piles (pile1, pile2, pile3);

  for (;;) {

    if (computer_to_move) {

      select_computer_move (pile1, pile2, pile3, pile_chosen, chips_removed);
      make_move (pile1, pile2, pile3, pile_chosen, chips_removed);
      cout << "The computer has removed " << chips_removed
           << " chips from pile " << pile_chosen << ":\n";
      if ((pile1 + pile2 + pile3) == 0) {
        cout << "The Computer has won!\n";
        return;
      }

    } else { // human to move

      get_human_move (pile1, pile2, pile3, pile_chosen, chips_removed);
      make_move (pile1, pile2, pile3, pile_chosen, chips_removed);
      if ((pile1 + pile2 + pile3) == 0) {
        cout << "Congratulations - you have won!\n";
        return;
      }

    }

    // display the new situation
    display_piles (pile1, pile2, pile3);

    computer_to_move = !computer_to_move; // it's now the other player's turn

  }

}


void main (void) {

   char option;

   randomize ();

   for (;;) {

     // prompt user for and read option
     cout << "\nPlease enter option.\n"
          << "  I = display instructions\n"
          << "  C = play game (computer to move first)\n"
          << "  H = play game (human to move first)\n"
          << "  Q = quit program\n"
          << "Option: ";
     cin >> option;
     cin.ignore (1000, '\n'); // get rid of the rest of the input line

     // I've used a switch statement here just to expose you to this
     // C++ construct.  the effect is equivalent to a multi-way "if".
     switch (toupper(option)) {

     case 'I':

       display_instructions ();
       break; // from switch statement

     case 'C':

       play_game (true);
       break; // from switch statement

     case 'H':

       play_game (false);
       break; // from switch statement

     case 'Q':

       return;

     default: // the equivalent of "else"

       cout << "\nIllegal option ignored.\n";
       break; // from switch statement

     }

   } // end for (;;)

}