Design Tic-Tac-Toe

Similar Problems:

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

A move is guaranteed to be valid and is placed on an empty block.

Once a winning condition is reached, no more moves is allowed.

A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Example:

Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board. TicTacToe toe = new TicTacToe(3); toe.move(0, 0, 1); -> Returns 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | toe.move(0, 2, 2); -> Returns 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | | toe.move(2, 2, 1); -> Returns 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X| toe.move(1, 1, 2); -> Returns 0 (no one wins) |X| |O| | |O| | // Player 2 makes a move at (1, 1). | | |X| toe.move(2, 0, 1); -> Returns 0 (no one wins) |X| |O| | |O| | // Player 1 makes a move at (2, 0). |X| |X| toe.move(1, 0, 2); -> Returns 0 (no one wins) |X| |O| |O|O| | // Player 2 makes a move at (1, 0). |X| |X| toe.move(2, 1, 1); -> Returns 1 (player 1 wins) |X| |O| |O|O| | // Player 1 makes a move at (2, 1). |X|X|X|

Follow up: Could you do better than O(n^2) per move() operation?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution: Use one dimension array

// https://code.dennyzhang.com/design-tic-tac-toe // Basic Ideas: simulation // // Complexity: Time O(1), Space O(n) type TicTacToe struct { d1 int d2 int rows []int cols []int } /** Initialize your data structure here. */ func Constructor(n int) TicTacToe { return TicTacToe{rows: make([]int, n), cols: make([]int, 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. */ func (this *TicTacToe) Move(row int, col int, player int) int { // player1: -1, player2: 1 v := 1 if player == 1 { v = -1 } // assume move is valid if row == col { this.d1 += v } if row+col == len(this.rows)-1 { this.d2 += v } this.rows[row] += v this.cols[col] += v for _, x := range []int{this.d1, this.d2, this.rows[row], this.cols[col]} { if x*v == len(this.rows) { return player } } return 0 } /** * Your TicTacToe object will be instantiated and called as such: * obj := Constructor(n); * param_1 := obj.Move(row,col,player); */

- Solution: Use two dimension array

// https://code.dennyzhang.com/design-tic-tac-toe // Basic Ideas: simulation // // Complexity: Time O(1), Space O(n) type TicTacToe struct { d1 [2]int d2 [2]int rows [][2]int cols [][2]int } /** Initialize your data structure here. */ func Constructor(n int) TicTacToe { return TicTacToe{rows: make([][2]int, n), cols: make([][2]int, 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. */ func (this *TicTacToe) Move(row int, col int, player int) int { // assume move is valid if row == col { this.d1[player-1]++ } if row+col == len(this.rows)-1 { this.d2[player-1]++ } this.rows[row][player-1]++ this.cols[col][player-1]++ for _, x := range []int{this.d1[player-1], this.d2[player-1], this.rows[row][player-1], this.cols[col][player-1]} { if x == len(this.rows) { return player } } return 0 } /** * Your TicTacToe object will be instantiated and called as such: * obj := Constructor(n); * param_1 := obj.Move(row,col,player); */