[19.2] Won a tic-tac-toe game

1. Example

O won = > 
row 0 => matrix[0][0] ='O'
               matrix[0][1] ='O'
               matrix[0][2] ='O'  => return 'O'
row 1 => matrix[1][0] ='X'
               matrix[1][1] ='X'
               matrix[1][2] =''     => return EMPTY
row 2 => matrix[2][0] ='X'
               matrix[2][1] =''     => return EMPTY
               matrix[2][2] ='' 

OOO
XX
X

2. Implementation
1. Call Once                :

2. Call Multiple Times: amortizing the cost by designing your own data storage system for the tic-tac-board

// Approach#1 : If hasWon is called many times
// There are only 3^9, or about twenty thousand tic-tac-toe boards
// every cell has O, X or empty choices. There are 9 cells and so there
// are 3^9 boards
// We can represent our tic-tac-toe board as an int, with each digit 
// representing a piece (0 menas Empty, 1 means Red, 2 means Blue)
// We set up a hashtable or array in advance with all possible boards
// as keys, and the values are 0,1 and 2. Our function then is simply 
// this
// OOO
// XX
// 
// => O Won= > O means 1
int hasWon(int board)
{
    return winnerHashtable[board];
}

// Approach#2: If hasWon is called only once
// check every column, row, diagonal, reverse diagonal, if any of 
// Piece continue
enum Piece{Empty, Red, Blue}
enum Check {Row ,Column, Diagonal, ReverseDiagonal}

Piece getIthColor(Piece[][] board, int RowOrColindex, int offset, Check check)
{
       if ( check == Check.Row ) return board[RowOrColindex][offset];
       else if ( check == Check.column ) return board[offset][RowOrColindex];
       else if ( check == Check.Diagonal ) return board[offset][offset];
       else if ( check == Check.ReverseDiagonal ) return board[offset][board.length -1 - offset];

       return Piece.Empty;
}


Piece getWinner(Piece[][] board, int RowOrColindex, Check check)
{

     // STEP1 : get the first cell's piece
     Piece color = getIthColor(board, RowOrColindex, 0, check);
     if ( color == Piece.Empty ) return Piece.Empty;
     // STEP2 : get the rest cell's piece and compare
offset =1; offset < board.length; offset++)
     {
           if ( color != getIthColor(board, RowOrColindex, offset, check) )
           {
               return Piece.Empty;
           }
     }
     return color;
}


Piece hasWon(Piece[][] board)
{




     int N = board.length;
     Piece winner = Piece.Empty;





     // Case1: check rows and columns
     for (int i = 0; i < N ; i++)
     {
          



            winner = getWinner(board, i , Check.Row);
            if (  winner != Piece.Empty  )
               return winner;





            winner = getWinner(board, i, Check.Column);
            if (  winner != Piece.Empty )
               return winner;




     }






     // Case2: check diagonal
     winner = getWinner(board, -1, Check.Diagonal);
     if (  winner != Piece.Empty  )
        return winner;







     // Case3: check reverse diagonal
     winner = getWinner(board, -1, Check.ReverseDiagonal);
     if (  winner != Piece.Empty )
         return winner;


      


     return Piece.Empty;




}

3. Similar Ones
1. O(N) with the addition of row and column count arrays( and two sums for the diagonals)
2. A common follow up (or tweak) to this question is to write this code for an NxN board