LeetCode: Design Tic-Tac-Toe

Posted on May 14, 2018February 14, 2020 by braindenny

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);
 */

Post Views: 8