// Author:  Dave Wessels
// File:    tttSolitaire.cpp
// Purpose: A solitaire game based on tic tac toe.
//
//          The computer secretly fills in X's and O's in all 9 positions
//          of a tic tac toe board, such that either X or O has won.
//          The player's objective is then to turn over 8 of the 9 squares
//          one at a time, WITHOUT revealing a 3-in-a-row.
//
//          Variant: the player tries to reveal a 3-in-a-row in as few
//          moves as possible.
//
//          The 9 board positions are labelled 1-9 for the purposes of 
//          selecting positions:
//
//             1 | 2 | 3 
//            ---+---+---
//             4 | 5 | 6
//            ---+---+---
//             7 | 8 | 9

#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <ctime>
#include <cstring>


// A tic tac toe board is stored as an array of 9 characters,
//   stored in row-major order (i.e. all of row 1, then all of row 2,
//   then all of row 3).
const int BoardSize = 10;
typedef char Board[BoardSize];

// There are 148 possible starting boards to select from,
// Squares on a 3-in-a-row are shown with uppercase W,
//    other squares are shown in lowercase w
const int NumBoards = 148;
Board BoardList[NumBoards] =
   {
      // 12 combinations where the winner has one line and one extra
          // 6 with the \ diagonal
          "OoxxOxxxO",  //  
          "OxoxOxxxO",  //  
          "OxxoOxxxO",  //  
          "OxxxOoxxO",  //  
          "OxxxOxoxO",  //  
          "OxxxOxxoO",  //  
          // 6 with the / diagonal
          "oxOxOxOxx",  //  
          "xoOxOxOxx",  //  
          "xxOoOxOxx",  //  
          "xxOxOoOxx",  //  
          "xxOxOxOox",  //  
          "xxOxOxOxo",  //  
       // 22 combinations where the winner has a double-line
          // 5 with the top row
          "OOOOxxOxx",  // top and left
          "OOOxOxxOx",  // top and midcol
          "OOOxxOxxO",  // top and right   
          "OOOxOxxxO",  // top and \ diagonal
          "OOOxOxOxx",  // top and / diagonal
          // 5 with the middle row
          "OxxOOOOxx",  // mid and left
          "xOxOOOxOx",  // mid and midcol
          "xxOOOOxxO",  // mid and right
          "OxxOOOxxO",  // mid and \ diagonal
          "xxOOOOOxx",  // mid and / diagonal
          // 5 with the bottom row
          "OxxOxxOOO",  // bot and left
          "xOxxOxOOO",  // bot and midcol
          "xxOxxOOOO",  // bot and right
          "OxxxOxOOO",  // bot and \ diagonal
          "xxOxOxOOO",  // bot and / diagonal
          // 4 with the \ diagonal but no row
          "OxxOOxOxO",  //  \  and left
          "OOxxOxxOO",  //  \  and midcol
          "OxOxOOxxO",  //  \  and right
          "OxOxOxOxO",  //  \  and / diagonal
          // 3 with the / diagonal but no row or \ diagonal
          "OxOOOxOxx",  //  /  and left
          "xOOxOxOOx",  //  /  and midcol
          "xxOxOOOxO",  //  /  and right
       // 40 combinations where the winner has a single line plus 2 extras
          // 4 with the top row
          "OOOoxxxox",  //  
          "OOOoxxxxo",  //  
          "OOOxxooxx",  //  
          "OOOxxoxox",  //  
          // 4 with the middle row
          "oxxOOOxox",  //  
          "xxoOOOxox",  //  
          "xoxOOOoxx",  //  
          "xoxOOOxxo",  //  
          // 4 with the bottom row
          "xoxoxxOOO",  //  
          "oxxxxoOOO",  //  
          "xxooxxOOO",  //  
          "xoxxxoOOO",  //  
          // 4 with the right column
          "xoOoxOxxO",  //  
          "xoOxxOoxO",  //  
          "xxOoxOxoO",  //  
          "oxOxxOxoO",  //  
          // 4 with the middle column
          "xOooOxxOx",  //  
          "xOxoOxxOo",  //  
          "oOxxOoxOx",  //  
          "xOxxOooOx",  //  
          // 4 with the left column
          "xoOoxOxxO",  //  
          "xoOxxOoxO",  //  
          "xxOoxOxoO",  //  
          "oxOxxOxoO",  //  
          // 8 with the \ diagonal
          "OxxoOxxoO",  //  
          "OxooOxxxO",  //  
          "OoxoOxxxO",  //  
          "OoxxOxoxO",  //  
          "OxxxOooxO",  //  
          "OoxxOoxxO",  //  
          "OxoxOxxoO",  //  
          "OxxxOoxoO",  //  
          // 8 with the / diagonal
          "oxOxOxOox",  //  
          "oxOxOoOxx",  //  
          "xoOoOxOxx",  //  
          "xxOoOxOox",  //  
          "xxOoOxOxo",  //  
          "xoOxOoOxx",  //  
          "xoOxOxOxo",  //  
          "xxOxOoOox",  //  

      // 12 combinations where the winner has one line plus one extra
          // 6 xith the \ diagonal
          "XxooXoooX",  //  
          "XoxoXoooX",  //  
          "XooxXoooX",  //  
          "XoooXxooX",  //  
          "XoooXoxoX",  //  
          "XoooXooxX",  //  
          // 6 xith the / diagonal
          "xoXoXoXoo",  //  
          "oxXoXoXoo",  //  
          "ooXxXoXoo",  //  
          "ooXoXxXoo",  //  
          "ooXoXoXxo",  //  
          "ooXoXoXox",  //  
       // 22 combinations where the winner has a double-line
          // 5 xith the top row
          "XXXXooXoo",  // top and left
          "XXXoXooXo",  // top and midcol
          "XXXooXooX",  // top and right   
          "XXXoXoooX",  // top and \ diagonal
          "XXXoXoXoo",  // top and / diagonal
          // 5 xith the middle row
          "XooXXXXoo",  // mid and left
          "oXoXXXoXo",  // mid and midcol
          "ooXXXXooX",  // mid and right
          "XooXXXooX",  // mid and \ diagonal
          "ooXXXXXoo",  // mid and / diagonal
          // 5 xith the bottom row
          "XooXooXXX",  // bot and left
          "oXooXoXXX",  // bot and midcol
          "ooXooXXXX",  // bot and right
          "XoooXoXXX",  // bot and \ diagonal
          "ooXoXoXXX",  // bot and / diagonal
          // 4 xith the \ diagonal but no row
          "XooXXoXoX",  //  \  and left
          "XXooXooXX",  //  \  and midcol
          "XoXoXXooX",  //  \  and right
          "XoXoXoXoX",  //  \  and / diagonal
          // 3 xith the / diagonal but no row or \ diagonal
          "XoXXXoXoo",  //  /  and left
          "oXXoXoXXo",  //  /  and midcol
          "ooXoXXXoX",  //  /  and right
       // 40 combinations where the winner has a single line plus 2 extras
          // 4 xith the top row
          "XXXxoooxo",  //  
          "XXXxoooox",  //  
          "XXXooxxoo",  //  
          "XXXooxoxo",  //  
          // 4 xith the middle row
          "xooXXXoxo",  //  
          "ooxXXXoxo",  //  
          "oxoXXXxoo",  //  
          "oxoXXXoox",  //  
          // 4 xith the bottom row
          "oxoxooXXX",  //  
          "xooooxXXX",  //  
          "ooxxooXXX",  //  
          "oxoooxXXX",  //  
          // 4 xith the right column
          "oxXxoXooX",  //  
          "oxXooXxoX",  //  
          "ooXxoXoxX",  //  
          "xoXooXoxX",  //  
          // 4 xith the middle column
          "oXxxXooXo",  //  
          "oXoxXooXx",  //  
          "xXooXxoXo",  //  
          "oXooXxxXo",  //  
          // 4 xith the left column
          "oxXxoXooX",  //  
          "oxXooXxoX",  //  
          "ooXxoXoxX",  //  
          "xoXooXoxX",  //  
          // 8 xith the \ diagonal
          "XooxXooxX",  //  
          "XoxxXoooX",  //  
          "XxoxXoooX",  //  
          "XxooXoxoX",  //  
          "XoooXxxoX",  //  
          "XxooXxooX",  //  
          "XoxoXooxX",  //  
          "XoooXxoxX",  //  
          // 8 xith the / diagonal
          "xoXoXoXxo",  //  
          "xoXoXxXoo",  //  
          "oxXxXoXoo",  //  
          "ooXxXoXxo",  //  
          "ooXxXoXox",  //  
          "oxXoXxXoo",  //  
          "oxXoXoXox",  //  
          "ooXoXxXxo",  //  
   };

// plays 1 game of lowBall or highBall, returns the player score
// (the number of boxes visible when 3-in-a-row first becomes visible)
int playGame();

// return true if all three characters are identical
//    false otherwise
bool identical(char a, char b, char c);

// asks the player if they want to play again,
//    returns true if yes, false if no
bool playAgain();

// initializes the random number generator
void initCentral();

// display the game rules and program behaviour
void displayRules();

// pick a random game board from BoardsList
//    initialize the contents of b appropriately
void initBoard(Board b);

// initialize the board mask (determines which squares are currently
//    hidden or revealed, initially all hidden)
void initMask(Board m);

// return true if the game is over, false otherwise
//    based on the underlying game board and the 
//    mask of which squares have been revealed
bool gameOver(Board board, Board mask);

// get and apply a player move given the underlying board
//     and current mask (updates mask)
void playerMove(Board board, Board mask);

// display the current mask, with the underlying board
//    showing through on previously selected squares
void displayBoard(Board board, Board mask);

// get the next non-whitespace character from standard input
char makeChoice(); 

// display the game stats to date for either lowBall or highBall
//    (most recent game score, average score, number of games,
//     best score to date, special message if this was new best)
void displayGameResults(int recentScore, int totalScore, int bestScore, int numGames, bool lowBall);

// display the end-of-the-session stats for both lowBall and highBall
void displayFinalResults(int overallLowScore, int numLowGames, int lowScore,
                         int overallHighScore, int numHighGames, int highScore);

// after the game is over, displays the entire underlying board
//   and the player's final version of the board
void displayFullBoard(Board board, Board mask);

// let the player chose whether they wish to play lowBall or highBall
// return true if lowBall, false if highBall
bool pickGameType();

int main()
{
   int overallHighScore = 0;
   int overallLowScore = 0;
   int highScore = 0;
   int lowScore = 10;
   int numHighGames = 0;
   int numLowGames = 0;
   initCentral();
   displayRules();
   do {
      bool lowBall = pickGameType();
      int score = playGame();
      if (lowBall) {
         overallLowScore += score;
         numLowGames++;
         displayGameResults(score, overallLowScore, lowScore, numLowGames, lowBall);
         if (score < lowScore) {
            lowScore = score;
         }
      } else {
         overallHighScore += score;
         numHighGames++;
         displayGameResults(score, overallHighScore, highScore, numHighGames, lowBall);
         if (score > highScore) {
            highScore = score;
         }
      }
   } while (playAgain());
   displayFinalResults(overallLowScore, numLowGames, lowScore, overallHighScore, numHighGames, highScore);
}

// plays 1 game of lowBall or highBall, returns the player score
// (the number of boxes visible when 3-in-a-row first becomes visible)
int playGame()
{
   bool quit = false;
   int score = 0;
   Board board, mask;
   initBoard(board);
   initMask(mask);
   do {
      playerMove(board, mask);
      if (gameOver(board, mask)) {
         quit = true;
      }
      score++;
   } while (!quit);
   displayFullBoard(board, mask);
   return score;
}

// initializes the random number generator
void initCentral()
{
   srand(time(NULL));
}

// pick a random game board from BoardsList and 
//    initialize the contents of b appropriately
void initBoard(Board b)
{
   // pick a random board and copy the contents to b
   int bnum = rand() % NumBoards;
   strncpy(b, BoardList[bnum], BoardSize);
}

// initialize the board mask (determines which squares are currently
//    hidden or revealed, initially all hidden)
void initMask(Board m)
{
   char bchar = '1';
   for (int p = 0; p < BoardSize; p++) {
       m[p] = bchar;
       bchar++;
   }
   m[BoardSize-1] = '\0';
}

// display the current mask, with the underlying board
//    showing through on previously selected squares
void displayBoard(Board board, Board mask)
{
   // determine what should be visible to the player
   Board view;
   for (int p = 0; p < BoardSize; p++) {
       if (isdigit(mask[p])) {
          view[p] = mask[p];
       } else {
          view[p] = toupper(board[p]);
       }
   }
   view[BoardSize-1] = '\0';
   // display the tic tac toe board layout,
   //    with the view showing in the 'holes'
   printf("+---+---+---+\n");
   printf("| %c | %c | %c |\n", view[0], view[1], view[2]);
   printf("+---+---+---+\n");
   printf("| %c | %c | %c |\n", view[3], view[4], view[5]);
   printf("+---+---+---+\n");
   printf("| %c | %c | %c |\n", view[6], view[7], view[8]);
   printf("+---+---+---+\n\n");
}

// asks the player if they want to play again,
//    returns true if yes, false if no
bool playAgain()
{
   printf("Enter Y to play again, or N to quit\n");
   char resp = makeChoice();
   if (toupper(resp) == 'Y') {
      return true;
   } else if (toupper(resp) == 'N') {
      return false;
   } else {
      printf("*** %c was not a valid response, please try again\n", resp);
      return playAgain();
   }
}

// let the player chose whether they wish to play lowBall or highBall
// return true if lowBall, false if highBall
bool pickGameType()
{
   printf("Enter L to play lowBall, or H to play highBall\n");
   char resp = makeChoice();
   if (toupper(resp) == 'L') {
      return true;
   } else if (toupper(resp) == 'H') {
      return false;
   } else {
      printf("*** %c was not a valid response, please try again\n", resp);
      return pickGameType();
   }
}

// display the game rules and program behaviour
void displayRules()
{
   printf("*****************************\n");
   printf("*** Tic Tac Toe Solitaire ***\n");
   printf("*****************************\n");
   printf("Tic tac toe is played as follows:\n\n");
   printf("The AI fills in all 9 positions of a standard tic tac toe board with X's or O's\n");
   printf("    in a manner which guarantees exactly one of the two sides has at least one\n");
   printf("    3-in-a-row, either vertically, horizontally, or diagonally\n");
   printf("One of the two sides will have 5 positions, the other will have 4 positions\n");
   printf("You, the player, then select one board position at a time, revealing squares\n");
   printf("    until at least one 3-in-a-row has been revealed\n");
   printf("The number of squares you revealed is your score for that game\n");
   printf("\nIn the lowBall version of the game, you are trying for the lowest score possible (3)\n");
   printf("    I.e. you are trying to reveal a winner as soon as possible\n");
   printf("In  the highBall version of the game, you are trying for the highest score possible (9)\n");
   printf("   I.e. you are trying to delay revealing a winner as long as possible\n\n");
   printf("You will be allowed to play as many games as you like, with the option to switch\n");
   printf("   between lowBall and highBall at the start of each game\n");
   printf("Your best scores and average scores will be tracked separately for lowBall and highBall\n");
}

// get the next non-whitespace character from standard input
char makeChoice()
{
   char c;
   do {
      c = fgetc(stdin);
   } while (isspace(c));
   return c;
}

// get and apply a player move given the underlying board
//     and current mask (updates mask)
// lowBall identifies whether the player is playing
//     the lowBall or highBall version of the game
void playerMove(Board board, Board mask)
{
   bool valid = false;
   do {
      displayBoard(board, mask);
      printf("Select an un-revealed position (1-9) from the board:");
      char move = makeChoice();
      int pos = move - '1';   // mask is 0-based, the player view of numbering is '1'-based
      if (!isdigit(move)) {
         printf("%c is not a position in 1-9, please try again\n", move);
      } else if (move == '0') {
         printf("0 is not a position in 1-9, please try again\n");
      } else if (!isdigit(mask[pos])) {
         printf("Position %c has already been taken, please try again\n", move);
      } else {
         // a valid move, wipe out the covering digit in the corresponding mask position
         mask[pos] = ' '; 
         valid = true;
      }
   } while (!valid);
}

// after the game is over, displays the entire underlying board
//   and the player's final version of the board
void displayFullBoard(Board board, Board mask)
{
   // determine what should be visible to the player
   Board view;
   for (int p = 0; p < BoardSize; p++) {
       if (isdigit(mask[p])) {
          view[p] = mask[p];
       } else {
          view[p] = toupper(board[p]);
       }
   }
   view[BoardSize-1] = '\0';
   // display the tic tac toe board layout,
   //    with the view showing in the 'holes'
   printf("Your final board    The original board\n");
   printf(" +---+---+---+        +---+---+---+\n");
   printf(" | %c | %c | %c |        | %c | %c | %c |\n", view[0], view[1], view[2], board[0], board[1], board[2]);
   printf(" +---+---+---+        +---+---+---+\n");
   printf(" | %c | %c | %c |        | %c | %c | %c |\n", view[3], view[4], view[5], board[3], board[4], board[5]);
   printf(" +---+---+---+        +---+---+---+\n");
   printf(" | %c | %c | %c |        | %c | %c | %c |\n", view[6], view[7], view[8], board[6], board[7], board[8]);
   printf(" +---+---+---+        +---+---+---+\n\n");
}

// return true if the game is over, false otherwise
//    based on the underlying game board and the 
//    mask of which squares have been revealed
bool gameOver(Board board, Board mask)
{
   // determine what should be visible to the player
   Board view;
   for (int p = 0; p < BoardSize; p++) {
       if (isdigit(mask[p])) {
          view[p] = mask[p];
       } else {
          view[p] = toupper(board[p]);
       }
   }
   view[BoardSize-1] = '\0';

   // the game is over if the view contains a row, column, or diagonal of 3 identical entries
   if (identical(view[0], view[1], view[2])) return true; // check row 1
   if (identical(view[3], view[4], view[5])) return true; // check row 2
   if (identical(view[6], view[7], view[8])) return true; // check row 3
   if (identical(view[0], view[3], view[6])) return true; // check col 1
   if (identical(view[1], view[4], view[7])) return true; // check col 2
   if (identical(view[2], view[5], view[8])) return true; // check col 3
   if (identical(view[0], view[4], view[8])) return true; // check down diag 
   if (identical(view[2], view[4], view[6])) return true; // check up diag
   return false;
}

// return true if all three characters are identical
//    false otherwise
bool identical(char a, char b, char c)
{
   return ((a == b) && (b == c));
}

// display the game stats to date for either lowBall or highBall
//    (most recent game score, average score, number of games,
//     best score to date, special message if this was new best)
void displayGameResults(int recentScore, int totalScore, int bestScore, int numGames, bool lowBall)
{
   printf("--------------------------------------\n");
   printf("You have played %d games of ", numGames);
   if (lowBall) {
      printf("lowBall\n");
   } else {
      printf("highBall\n");
   }
   printf("Your score on this game was %d", recentScore);
   if (((lowBall) && (recentScore < bestScore)) || ((!lowBall) && (recentScore > bestScore))) {
      printf(", A NEW BEST SCORE!\n");
   } else if (recentScore == bestScore) {
      printf(", that matches your best score so far!\n");
   } else {
      printf("\n");
   }
   printf("Your average score to date is %.3f\n", (totalScore / (1.0 * numGames)));
   printf("--------------------------------------\n");
}

// display the end-of-the-session stats for both lowBall and highBall
void displayFinalResults(int overallLowScore, int numLowGames, int lowScore,
                         int overallHighScore, int numHighGames, int highScore)
{
   printf("\n*********************************************************\n");
   printf("****************   FINAL RESULTS   **********************\n");
   printf("*********************************************************\n");
   if (numLowGames > 0) {
      printf("You have played %d games of lowBall\n", numLowGames);
      printf("    with a best score of %d, and an average score of ", lowScore);
      printf("%.3f\n", (overallLowScore / (1.0 * numLowGames)));
      if (numHighGames > 0) {
         printf("------------------------------------------------\n");
      }
   }
   if (numHighGames > 0) {
      printf("You have played %d games of highBall\n", numHighGames);
      printf("    with a best score of %d, and an average score of ", highScore);
      printf("%.3f\n", (overallHighScore / (1.0 * numHighGames)));
   }
   printf("*********************************************************\n");
   printf("*********************************************************\n\n");
}