Find Winner on a Tic Tac Toe Game

class GameResult {
public:
    string determineWinner(vector<vector<int>>& actions) {
        int boardSize = 3;
        vector<int> rowSums(boardSize), colSums(boardSize);
        int majorDiagSum = 0;
        int minorDiagSum = 0;
        int currentPlayer = 1;
        
        for (vector<int> action : actions) {
            int rowIdx = action[0];
            int colIdx = action[1];
            
            rowSums[rowIdx] += currentPlayer;
            colSums[colIdx] += currentPlayer;
            
            if (rowIdx == colIdx) {
                majorDiagSum += currentPlayer;
            }
            if (rowIdx + colIdx == boardSize - 1) {
                minorDiagSum += currentPlayer;
            }
            
            if (abs(rowSums[rowIdx]) == boardSize || abs(colSums[colIdx]) == boardSize || 
                abs(majorDiagSum) == boardSize || abs(minorDiagSum) == boardSize) {
                return currentPlayer == 1 ? "A" : "B";
            }
            
            currentPlayer *= -1;
        }

        return actions.size() == boardSize * boardSize ? "Draw" : "Pending";
    }
};

The program defines a class GameResult in C++ to determine the outcome of a Tic Tac Toe game. The function determineWinner is given, accepting a series of player actions and returns the game result as a string. Here's how it works:

• Initiate board size to 3 (standard Tic Tac Toe).
• Use vectors rowSums and colSums to track cumulative scores for rows and columns, respectively, while majorDiagSum and minorDiagSum track the major and minor diagonal scores.
• Use the currentPlayer variable starting with player A (represented by 1) and switches between A and B (or 1 and -1, respectively) after each move.
• Iterate through each 'action', updating relevant sums for the action’s row and column. Include checks for diagonal moves.
• After each move, check for absolute values of rowSums[rowIdx], colSums[colIdx], majorDiagSum, and minorDiagSum equaling the board size to declare a winner.
• If no winner is found and all board positions are filled, the game is a "Draw"; otherwise, it's "Pending" if moves are still available.
• Player A or B is returned as the winner based on the current state of currentPlayer.

This efficient implementation uses simple integer arrays for state tracking and evaluates the board’s condition with each move, allowing quick determination of the game's status.

class Game {
    public String checkWinner(int[][] plays) {
        int boardSize = 3;
        int[] horizontal = new int[boardSize], vertical = new int[boardSize];
        int primaryDiagonal = 0, secondaryDiagonal = 0;
        int currentPlayer = 1;
        
        for (int[] play : plays) {
            int x = play[0], y = play[1];
            
            horizontal[x] += currentPlayer;
            vertical[y] += currentPlayer;
            
            if (x == y) {
                primaryDiagonal += currentPlayer;
            }
            if (x + y == boardSize - 1) {
                secondaryDiagonal += currentPlayer;
            }
            
            if (Math.abs(horizontal[x]) == boardSize || Math.abs(vertical[y]) == boardSize ||
                Math.abs(primaryDiagonal) == boardSize || Math.abs(secondaryDiagonal) == boardSize) {
                return currentPlayer == 1 ? "A" : "B";
            }
            
            currentPlayer *= -1;
        }
        
        return plays.length == boardSize * boardSize ? "Draw" : "Pending";
    }
}

The solution implements a function to determine the winner of a Tic Tac Toe game or check if the game is still pending or has resulted in a draw. The function accepts an array of plays, where each play indicates the row and column indices marked by the current player.

Here’s a breakdown of how the code operates:

1. Initial setup includes defining the size of the board and initializing counters for horizontal, vertical, and diagonal checks. These counters track the sum of values assigned to moves made by players 'A' and 'B'.

2. A loop iterates through each play:

   • Updates counters for rows and columns based on the player's move.
   • Updates diagonals if the move is made on either diagonal.
   • After each move, checks if the absolute value of any counter equals the board size, which would indicate that a player has won. If a player wins, it returns 'A' if the sum corresponds to player 1 and 'B' for player -1.
   • Flips the current player indicator after each play.

3. After processing all plays:

   • Determines if the game is a 'Draw' (when all cells are filled and no winner) or 'Pending' (if not all cells are filled and no winner yet).

The logic utilizes a constant space approach with O(n) time complexity per move checking, ensuring efficient checking even as the number of moves scales. This approach effectively handles game status updates in real-time for a standard 3x3 Tic Tac Toe board.

class Game:
    def find_winner(self, moves: List[List[int]]) -> str:
        board_size = 3
        row_counts, col_counts = [0] * board_size, [0] * board_size
        diagonal1 = diagonal2 = 0
        current_player = 1

        for x, y in moves:
            row_counts[x] += current_player
            col_counts[y] += current_player

            if x == y:
                diagonal1 += current_player
            if x + y == board_size - 1:
                diagonal2 += current_player

            if any(abs(line) == board_size for line in (row_counts[x], col_counts[y], diagonal1, diagonal2)):
                return "A" if current_player == 1 else "B"

            current_player *= -1

        return "Draw" if len(moves) == board_size * board_size else "Pending"

The given Python code defines a class Game with a method find_winner to determine the winner of a Tic Tac Toe game based on a list of moves. The method first initializes variables for the size of the board, as well as counters for rows, columns, and both diagonals. It represents players with 1 and -1, alternating between them after each move.

Here's a summary of how the solution operates:

• The method takes the list moves, with each move represented as a list [x, y] where x and y denote the row and column positions on the board respectively.
• After each move, the corresponding row and column counters are updated based on the current player.
• If the row or column matches the diagonal criteria (x == y or x + y == board_size - 1), the diagonal counters are also updated.
• Following each move, the method checks if the absolute value of any line’s (row, column, or diagonal) count equals the board size. Such a condition indicates a win by completing a line, diagonally, horizontally, or vertically.
• The method determines the winner after the condition is met, returning "A" for player 1 and "B" for player -1.
• If all moves are made and no winner is determined, the result could either be “Draw” if the board is full, or “Pending” if moves are still possible within the grid space.

Each game move alters state tracking, facilitating optimal determination of game status efficiently after each play.