// New Tic Tac Toe
// A variation of the basic game of tic tac toe

#include <iostream>
#include <string>
#include <vector>

using namespace std;

//global constants
const char X = 'X';
const char O = 'O';
const char EMPTY = ' ';
const char NO_ONE = 'N';

// function prototypes
void Instructions();
char AskYesNo(string question);
int AskNumber(string question, int high, int low = 1);
char HumanPiece();
char SwitchPiece(char piece);
void DisplayBoard(const vector<char>& board);
char Winner(const vector<char>& board);
bool IsLegal(const vector<char>& board, int move);
int HumanMove(const vector<char>& board, char player);
int ComputerMove(const vector<char> board, char computer);
void AnnounceWinner(char winner, char player, char computer);

// main function
int main()
{
    int turn=0;
    int current_move;
    const int NUM_PIECES = 6;
    const int NUM_SQUARES = 9;
    vector<int> move(NUM_PIECES,10);
    vector<char> board(NUM_SQUARES, EMPTY);
    
    Instructions();
    char human = HumanPiece();
    char computer = SwitchPiece(human);
    char current_player = X;
    DisplayBoard(board);
    
    while (Winner(board) == NO_ONE)
    {
          if (current_player == human)
          {
             current_move = HumanMove(board, human);
             if (move[turn%NUM_PIECES] < 10)
                board[move[turn%NUM_PIECES]] = EMPTY;
             move[turn%NUM_PIECES] = current_move;
             board[current_move] = human;
             turn++;
          }
          else
          {
              current_move = ComputerMove(board, computer);
              if (move[turn%NUM_PIECES] < 10)
                 board[move[turn%NUM_PIECES]] = EMPTY;
              move[turn%NUM_PIECES] = current_move;
              board[current_move] = computer;
              turn++;
          }
          DisplayBoard(board);
          current_player = SwitchPiece(current_player);
    }
    
    AnnounceWinner(Winner(board), computer, human);
    
    system("PAUSE");
    
    
    
    return 0;
}

// function definitions
void Instructions()
{
     cout << "Welcome to the new and improved Tic Tac Toe!\n\n";
     cout << "This game is a little bit more complicated than the original.\n";
     cout << "First of all each player can have only three pieces on the board,\n";
     cout << "for a total of just 6 pieces.\n\n";
     cout << "On the turn after you place your third piece, the first piece\n";
     cout << "that you place will be taken out and you will have to place it\n";
     cout << "somewhere else and not in the same spot.\n\n";
     
     cout << "You can make your move by entering a number 1 - 9.  The number\n";
     cout << "corresponds to the desired board position, as illustrated:\n\n";
     
     cout << "             1 | 2 | 3\n";
     cout << "            -----------\n";
     cout << "             4 | 5 | 6\n";
     cout << "            -----------\n";
     cout << "             7 | 8 | 9\n\n";
     
     cout << "Let's get started!\n";
}

char AskYesNo(string question)
{
     char response;
     do
     {
          cout << question << " (y/n): ";
          cin >> response;
     }while (response != 'y' && response != 'n');
     
     return response;
}

int AskNumber(string question, int high, int low)
{
    int number;
    do
    {
        cout << question << " (" << low << " - " << high << "): ";
        cin >> number;
    }while (number > high || number < low);
    
    return number;
}

char HumanPiece()
{
     char go_first = AskYesNo("Do you want to move first?");
     if (go_first == 'y')
     {
        cout << "\nThen take the first move.\n";
        return X;
     }
     else
     {
         cout << "\nAlright, I will go first.\n";
         return O;
     }
}

char SwitchPiece(char piece)
{
     if (piece == X)
        return O;
     else
         return X;
}

void DisplayBoard(const vector<char>& board)
{
     cout << "\n\t" << board[0] << " | " << board[1] << " | " << board[2];
     cout << "\n\t" << board[3] << " | " << board[4] << " | " << board[5];
     cout << "\n\t" << board[6] << " | " << board[7] << " | " << board[8];
     cout << "\n\n";
}

char Winner(const vector<char>& board)
{
     // all possible winning rows
     const int WINNING_ROWS[8][3] = { {0, 1, 2}, {3, 4, 5},
                                    {6, 7, 8}, {0, 3, 6},
                                    {1, 4, 7}, {2, 5, 8},
                                    {0, 4, 8}, {2, 4, 6} };
     
     const int TOTAL_ROWS = 8;
     
     // if any winning row has three values that are the same (and not EMPTY),
     // then we have a winner
     for(int row = 0; row < TOTAL_ROWS; ++row)
     {
             if ( (board[WINNING_ROWS[row][0]] != EMPTY) &&
                  (board[WINNING_ROWS[row][0]] == board[WINNING_ROWS[row][1]]) &&
                  (board[WINNING_ROWS[row][1]] == board[WINNING_ROWS[row][2]]) )
             {
                  return board[WINNING_ROWS[row][0]];
             }
     }
     
     
     // since nobody has won, the game is not over
     return NO_ONE;
}

bool IsLegal(int move, const vector<char>& board)
{
     return (board[move] == EMPTY);
}

int HumanMove(const vector<char>& board, char player)
{
    int move = AskNumber("Where will you move?", (board.size()));
    while(!IsLegal(move-1,board))
    {
         cout << "\nSorry, you cannot move there.\n";
         move = AskNumber("Where will you move?", (board.size()));
    }
    cout << "Ok.\n";
    return move-1;
}

int ComputerMove(vector<char> board, char computer)
{
    cout << "I shall take square number ";
    
    // if coumputer can win on next move, make that move
    for(int move = 0; move < board.size(); ++move)
    {
            if (IsLegal(move, board))
            {
                  board[move] = computer;
                  if (Winner(board) == computer)
                  {
                        cout << move + 1 << endl;
                        return move;
                  }
                  // done checking this move, undo it
                  board[move] = EMPTY;
            }
    }
    
    // if human can win on next move, block that move
    char human = SwitchPiece(computer);
    for(int move = 0; move < board.size(); ++move)
    {
            if(IsLegal(move,board))
            {
                  board[move] = human;
                  if (Winner(board) == human)
                  {
                       cout << move + 1 << endl;
                       return move;
                  }
                  // done checking this move, undo it
                  board[move] = EMPTY;
            }
    }
    
    // the best moves to make, in order
    const int BEST_MOVES[] = {4, 0, 2, 6, 8, 1, 3, 5, 7};
    // since no one can win on next move, pick the best open square
    for(int i = 0; i < board.size(); ++i)
    {
            int move = BEST_MOVES;
            if (IsLegal(move,board))
            {
                   cout << move + 1 << endl;
                   return move;
            }
    }
}

void AnnounceWinner(char winner, char computer, char human)
{
     if (winner == computer)
     {
                cout << winner << "'s won!\n";
                cout << "Good game.  Practice some more and then play me again\n";
     }
     
     else
     {
          cout << winner << "'s won!\n";
          cout << "Wow!  You got lucky.  Let's have a rematch soon.\n";
     }
}

struct board {  char data[9];  char& operator[](int x) { return data[x]; }  const char& operator[](int x) const { return data[x]; }  // You don't need to write a copy constructor, etc. for this;  // an array member will get bitwise-copied over. However you  // *would* need it if you used a pointer as a data member  // (and you'd also have to make some allocation for it to point at).}

int AskNumber(string question, int high, int low){    int number;    do    {        cout << question << " (" << low << " - " << high << "): ";        cin >> number;    }while (number > high || number < low);        return number;}

int AskNumber(string question, int high, int low){    int number;    do    {        cout << question << " (" << low << " - " << high << "): ";        // grab the whole line of input        string input;        getline(cin, input);        // and wrap it up in a new stringstream for parsing        stringstream ss;        ss.str(input); // assign the input line to the stringstream's buffer    } while (!(ss >> number) || number > high || number < low);    // if we couldn't read a number at all, loop, implicitly trashing the    // old stringstream object. Otherwise, if the number was invalid, we    // do the same. If both those checks are ok, we break the loop and return    // our 'good' value :)    return number;}

class Board {  // the data storage goes here; now it's private.  public:  // We won't provide an operator[]. Instead, we'll have a placement method  // that is checked:  void place(int where, char what) {    if (isLegal(where)) { storage[where] = what; }  }  bool isLegal(int where) const; // check if it's possible to move there.  // The other option is to hide isLegal(), and have place() return the  // value it got from its isLegal() call (so that it then becomes a   // success code).  void display() const; // output the board.}// Note the const-correctness in there. All our parameters are primitives being // passed by value, so constness is not really valuable there. In order to// inform C++ about which functions may change the board, though, we use the// const keywords in the function signatures. Note their placement: 'const'// there means "the data pointed to by the this-pointer is const".// Now for example, we can rewrite the HumanMove():// We'll actually make the move at this point, since that's easy to do.// Also that way we'll actually use the 'player' parameter. Some compilers// will give you warnings about unused parameters; you can normally shut them// up by not giving the parameter a name. (Sometimes that's useful when working// with someone else's API.)// I'll also use a do-while loop to remove the repetition of prompting...void makeHumanMove(const Board& board, char player) {    do {      // We'll subtract right away upon getting the value; that's cleaner      int move = AskNumber("Where will you move?", (board.size()));    } while(!board.IsLegal(move) &&             cout << "\nSorry, you cannot move there.\n");    // That part requires a bit of explanation for the uninitiated.    // If the move is legal, C++'s short-circuit evaluation will skip the cout,     // and the loop just breaks (because the while condition is false).     // If illegal, C++ does the cout and evaluates the result. Recall that     // "cout << foo" is an *expression*; it has a type and value (a reference     // to the cout object itself; that's how chaining "cout << foo << bar"     // works), and can be interpreted as a boolean (for ostreams, the object     // evaluates true iff the stream is "ok" for further writing). Assuming no     // catastrophic failures, the cout expression should thus always evaluate     // true, so the whole thing is true, and the loop continues.    // Complicated, yes, but considered fairly idiomatic too. A lot of the    // language design actually seems to revolve around making it possible to     // do things like this and have them be useful. :\    // Finally, make the move.    board.place(move, player);}

int AskNumber(string question, int high, int low){    int number;    do    {        cout << question << " (" << low << " - " << high << "): ";        string input;        getline(cin,input);        stringstream ss;        ss.str(input);    }while (!(ss >> number) || number > high || number < low);        return number;}