Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/348.html
Assume the following rules are for the tic-tac-toe game on an n x n board between two players:
- A move is guaranteed to be valid and is placed on an empty block.
- Once a winning condition is reached, no more moves are allowed.
- A player who succeeds in placing
nof their marks in a horizontal, vertical, or diagonal row wins the game.
Implement the TicTacToe class:
TicTacToe(int n)Initializes the object the size of the boardn.int move(int row, int col, int player)Indicates that the player with idplayerplays at the cell(row, col)of the board. The move is guaranteed to be a valid move, and the two players alternate in making moves. Return0if there is no winner after the move,1if player 1 is the winner after the move, or2if player 2 is the winner after the move.
Example 1:
Input ["TicTacToe", "move", "move", "move", "move", "move", "move", "move"] [[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]] Output [null, 0, 0, 0, 0, 0, 0, 1] Explanation TicTacToe ticTacToe = new TicTacToe(3); Assume that player 1 is "X" and player 2 is "O" in the board. ticTacToe.move(0, 0, 1); // return 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | ticTacToe.move(0, 2, 2); // return 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | | ticTacToe.move(2, 2, 1); // return 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X| ticTacToe.move(1, 1, 2); // return 0 (no one wins) |X| |O| | |O| | // Player 2 makes a move at (1, 1). | | |X| ticTacToe.move(2, 0, 1); // return 0 (no one wins) |X| |O| | |O| | // Player 1 makes a move at (2, 0). |X| |X| ticTacToe.move(1, 0, 2); // return 0 (no one wins) |X| |O| |O|O| | // Player 2 makes a move at (1, 0). |X| |X| ticTacToe.move(2, 1, 1); // return 1 (player 1 wins) |X| |O| |O|O| | // Player 1 makes a move at (2, 1). |X|X|X|
Constraints:
2 <= n <= 100- player is
1or2. 0 <= row, col < n(row, col)are unique for each different call tomove.- At most
n2calls will be made tomove.
Follow-up: Could you do better than O(n2) per move() operation?
Algorithm
The provided Python code defines a class TicTacToe that simulates a game of tic-tac-toe with a board of size n x n. The class is designed to efficiently check if a move by a player results in a win. Here’s a breakdown of the code:
Initialization (__init__ method)
- The constructor initializes four attributes:
self.rowsandself.cols: Arrays of lengthnthat track the cumulative scores of rows and columns, respectively. A positive score favors one player, while a negative score favors the other.self.diagandself.antiDiag: Variables to track the scores of the main diagonal (top-left to bottom-right) and the anti-diagonal (top-right to bottom-left), respectively.self.n: Stores the size of the board.
The move Method
- This method is dynamically defined within the
__init__method and is attached to the class instance. It’s used to make a move on the board and checks if this move wins the game. - Parameters:
rowandcol: Indicate the position of the move.player: Indicates the player making the move.playeris either 1 or 2.
delta: A value calculated based on the player making the move. Ifplayeris 1,deltais 1; ifplayeris 2,deltais -1. This approach allows using a single set of counters for both players, where one player increases the counters and the other decreases them.- The method updates the
rows,cols,diag, andantiDiagcounters based on the move. For the diagonal counters, it addsdeltaonly if the move is on the respective diagonal. - After updating the counters, the method checks if any of them equals
n * deltaor-n * delta(depending on the player). Such a value indicates that a player has filled an entire row, column, or diagonal, thus winning the game. - The method returns the player number if they win with this move or
0if the game continues.
Key Points
- The design efficiently checks for a win condition without iterating through the board after every move, leveraging arithmetic to track the state of the game.
- It abstracts the game’s state into numerical counters, allowing for quick win condition checks.
- This implementation supports only two players and assumes correct input for each move.
On python’s and operation
In Python, the expression 1+1==2 and delta involves both a comparison operation and a logical AND operation. When delta = -1, here’s how Python evaluates this expression:
-
Comparison: The expression starts with
1+1==2. Python evaluates1+1to get2, and then checks if2is equal to2. Since this is true, the comparison1+1==2evaluates toTrue. -
Logical AND: The
andoperator in Python performs a logical AND operation. It evaluates to True if both sides of theandare truthy, and False otherwise. A truthy value is any value that is not consideredFalseor empty in a Boolean context. Non-zero numbers, including negative numbers, are considered truthy. -
Evaluation with
delta: Sincedelta = -1, the right side of theandis-1. In Python,-1is considered a truthy value because it’s not zero.
Putting it all together, 1+1==2 evaluates to True, and since -1 is truthy, the whole expression 1+1==2 and delta evaluates to the value of delta because of how the and operator works:
- if the first value is
True, it returns the second value. This behavior is part of Python’s short-circuit evaluation. - The
andoperator returns the first falsy value it encounters or the last value if none are falsy. Since the comparison isTrue, theandoperator returnsdelta.
Therefore, when delta = -1, the expression 1+1==2 and delta evaluates to -1.
Code
-
public class Design_Tic_Tac_Toe { int[][] matrix; /** * Initialize your data structure here. */ public Design_Tic_Tac_Toe(int n) { matrix = new int[n][n]; } /** * Player {player} makes a move at ({row}, {col}). * * @param row The row of the board. * @param col The column of the board. * @param player The player, can be either 1 or 2. * @return The current winning condition, can be either: * 0: No one wins. * 1: Player 1 wins. * 2: Player 2 wins. */ public int move(int row, int col, int player) { int[] rows = new int[3]; int[] cols = new int[3]; int[] diag = new int[2]; int val = player == 1 ? 1: -1; rows[row] += val; // assumption: valid input, no override for same location cols[col] += val; if (row == col) { diag[0] += val; } if (row + col == 2) { diag[1] += val; } if (Math.abs(rows[row]) == 3 || Math.abs(cols[col]) == 3 || Math.abs(diag[0]) == 3 || Math.abs(diag[1]) == 3) { return player; } return 0; } public int move_naive_solution(int row, int col, int player) { matrix[row][col] = player; //check row boolean win = true; for (int i = 0; i < matrix.length; i++) { if (matrix[row][i] != player) { win = false; break; } } if (win) return player; //check column win = true; for (int i = 0; i < matrix.length; i++) { if (matrix[i][col] != player) { win = false; break; } } if (win) return player; //check back diagonal win = true; for (int i = 0; i < matrix.length; i++) { if (matrix[i][i] != player) { win = false; break; } } if (win) return player; //check forward diagonal win = true; for (int i = 0; i < matrix.length; i++) { if (matrix[i][matrix.length - i - 1] != player) { win = false; break; } } if (win) return player; return 0; } } ############ class TicTacToe { private int n; private int[][] counter; /** Initialize your data structure here. */ public TicTacToe(int n) { counter = new int[2][(n << 1) + 2]; this.n = n; } /** Player {player} makes a move at ({row}, {col}). @param row The row of the board. @param col The column of the board. @param player The player, can be either 1 or 2. @return The current winning condition, can be either: 0: No one wins. 1: Player 1 wins. 2: Player 2 wins. */ public int move(int row, int col, int player) { counter[player - 1][row] += 1; counter[player - 1][col + n] += 1; if (row == col) { counter[player - 1][n << 1] += 1; } if (row + col == n - 1) { counter[player - 1][(n << 1) + 1] += 1; } if (counter[player - 1][row] == n || counter[player - 1][col + n] == n || counter[player - 1][n << 1] == n || counter[player - 1][(n << 1) + 1] == n) { return player; } return 0; } } /** * Your TicTacToe object will be instantiated and called as such: * TicTacToe obj = new TicTacToe(n); * int param_1 = obj.move(row,col,player); */ -
// OJ: https://leetcode.com/problems/design-tic-tac-toe/ // Time: O(N) // Space: O(N^2) class TicTacToe { private: vector<vector<int>> board; int n; int status(int row, int col) { int p = board[row][col]; bool win = true; for (int i = 0; i < n && win; ++i) { if (board[row][i] != p) win = false; } if (win) return p; win = true; for (int i = 0; i < n && win; ++i) { if (board[i][col] != p) win = false; } if (win) return p; if (row == col) { win = true; for (int i = 0; i < n && win; ++i) { if (board[i][i] != p) win = false; } if (win) return p; } if (row + col == n - 1) { win = true; for (int i = 0; i < n && win; ++i) { if (board[i][n - 1 - i] != p) win = false; } if (win) return p; } return 0; } public: TicTacToe(int n) : n(n) { board = vector<vector<int>>(n, vector<int>(n)); } int move(int row, int col, int player) { board[row][col] = player; return status(row, col); } }; -
''' >>> delta = 1 >>> 1+1==2 True >>> 1+1==2 and delta 1 >>> >>> >>> delta = -1 >>> 1+1==2 and delta -1 >>> >>> delta = -100 >>> 1+1==2 and delta -100 >>> >>> delta = -100 >>> 1+1==99 and delta False >>> ''' class TicTacToe(object): def __init__(self, n): self.rows = [0] * n self.cols = [0] * n self.diag = self.antiDiag = 0 self.n = n def move(row, col, player): delta = 3 - player * 2 self.rows[row] += delta self.cols[col] += delta self.diag += (row == col and delta) self.antiDiag += (row + col == self.n - 1 and delta) if delta * self.n in [self.rows[row], self.cols[col], self.diag, self.antiDiag]: return player return 0 self.move = move # Your TicTacToe object will be instantiated and called as such: # obj = TicTacToe(n) # param_1 = obj.move(row,col,player) ############ class TicTacToe: def __init__(self, n: int): """ Initialize your data structure here. """ self.n = n self.counter = [[0] * ((n << 1) + 2) for _ in range(2)] def move(self, row: int, col: int, player: int) -> int: """ Player {player} makes a move at ({row}, {col}). @param row The row of the board. @param col The column of the board. @param player The player, can be either 1 or 2. @return The current winning condition, can be either: 0: No one wins. 1: Player 1 wins. 2: Player 2 wins. """ n = self.n self.counter[player - 1][row] += 1 self.counter[player - 1][col + n] += 1 if row == col: self.counter[player - 1][n << 1] += 1 if row + col == n - 1: self.counter[player - 1][(n << 1) + 1] += 1 if ( self.counter[player - 1][row] == n # taking full row or self.counter[player - 1][col + n] == n # full col or self.counter[player - 1][n << 1] == n # full diag or self.counter[player - 1][(n << 1) + 1] == n # full anti diag ): return player return 0 # Your TicTacToe object will be instantiated and called as such: # obj = TicTacToe(n) # param_1 = obj.move(row,col,player)