348 Design Tic-Tac-Toe

Design a Tic-tac-toe game that is played between two players on anxngrid.

You may assume the following rules:

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

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

3. 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) permove()operation?

The Idea: The primary challenge about this problem is to achieve an O(n) move operation (as opposed to naively scanning through the matrix every time.) To achieve this, want we do is only validate the row, col and diagonal (if applicable) on the coordinate a move that the player made. This works because even previous move was a non-winning move and a winning move could only come from having made the current move.

Complexity: O(4n) move operation, and O(1) extra space

class TicTacToe:
    def __init__(self, n):
        """
        Initialize your data structure here.
        :type n: int
        """
        self.board = [[0 for _ in range(n)] for _ in range(n)]
        self.n = n

    def validate_row(self, row, player):
        for cell in self.board[row]:
            if cell != player:
                return False
        return True

    def validate_col(self, col, player):
        for row in range(0, self.n):
            if self.board[row][col] != player:
                return False
        return True

    def is_diagonal(self, row, col):
        return row == col or row + col == self.n - 1

    def validate_diagonal(self, player):
        y_neg_x = True
        for d in range(0, self.n):
            if self.board[d][d] != player:
                y_neg_x = False
                break

        y_x = True
        for i, j in zip(range(self.n - 1, -1, -1), range(0, self.n)):
            if self.board[i][j] != player:
                y_x = False
                break
        return y_x or y_neg_x

    def move(self, row, col, player):
        """
        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.
        :type row: int
        :type col: int
        :type player: int
        :rtype: int
        """

        self.board[row][col] = player
        if self.validate_row(row, player) or self.validate_col(col, player):
            return player
        elif self.is_diagonal(row, col) and self.validate_diagonal(player):
            return player
        else:
            return 0

# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)

obj1 = TicTacToe(2)
print(obj1.move(0,1,1))
print(obj1.move(1,1,2))
print(obj1.move(1,0,1))

obj2 = TicTacToe(3)
print(obj2.move(0,0,1))
print(obj2.move(0,2,2))
print(obj2.move(2,2,1))
print(obj2.move(1,1,2))
print(obj2.move(2,0,1))
print(obj2.move(1,0,2))
print(obj2.move(2,1,1))