algoadvance

You are given an array moves where each element represents a move made by players in a game of Tic Tac Toe on a 3x3 board. The moves array contains elements in the form [row, col]:

• There are two players: Player A and Player B. Player A always plays first.
• Player A and B take turns making moves.
• The board initially is empty.
• The winner is the first player who places three of their marks (‘A’ or ‘B’) in a row, column, or diagonal.
• If all cells of the board are filled and no player has won, the game is declared a draw.
• If there are still moves to be played, return “Pending”.

The output should be “A” if Player A wins, “B” if Player B wins, “Draw” if no one wins and all cells are filled, and “Pending” if the game is still ongoing.

Clarifying Questions

1. Can a move be duplicated in the input array?
   • No, each move in the input array is unique and valid.
2. Is the input always a valid sequence of moves for a Tic Tac Toe game?
   • Yes, the input array always represents a valid sequence of moves in a Tic Tac Toe game.
3. Should we consider the order of the moves to determine the correct player making each move?
   • Yes, Player A goes first and players alternate turns.

Code

def tictactoe(moves):
    # Initialize the board as a 3x3 grid
    board = [["" for _ in range(3)] for _ in range(3)]
    
    # Fill the board based on the moves
    for i, (r, c) in enumerate(moves):
        if i % 2 == 0:  # Player A's move
            board[r][c] = 'A'
        else:  # Player B's move
            board[r][c] = 'B'
    
    # Function to check for a winning condition
    def check_winner(player):
        # Check rows, columns, and both diagonals
        for row in board:
            if all(cell == player for cell in row):
                return True
        for col in range(3):
            if all(board[row][col] == player for row in range(3)):
                return True
        if all(board[i][i] == player for i in range(3)):
            return True
        if all(board[i][2 - i] == player for i in range(3)):
            return True
        return False
    
    # Check if A or B has won
    if check_winner('A'):
        return "A"
    if check_winner('B'):
        return "B"
    
    # If no one has won, check if the board is full
    if len(moves) == 9:
        return "Draw"
    
    # If there are remaining moves, return pending
    return "Pending"

Strategy

1. Initialize the Board:
   • Create a 3x3 board initialized with empty strings where each cell represents a possible move.
2. Simulate the Moves:
   • Iterate over the moves and mark the board using ‘A’ for Player A and ‘B’ for Player B based on the move index.
3. Check for Win Condition:
   • Implement a helper function check_winner to determine if a player has three marks in any row, column, or diagonal.
4. Determine the Result:
   • If Player A wins, return “A”.
   • If Player B wins, return “B”.
   • If all moves are exhausted and no winner is found, return “Draw”.
   • If there are still potential moves left, return “Pending”.

Time Complexity

• Initialization: Creating the board takes O(1), as it’s a fixed 3x3 grid.
• Simulate Moves: Processing each move is O(1), and for N moves, it is O(N).
• Check Winner: Checking rows, columns, and diagonals involves constant-time checks, as the board size is fixed at 3x3, leading to O(1) operations.

Thus, the overall time complexity is ( O(N) ), where ( N ) is the number of moves.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?