Design a TicTacToe

Problem

348. Design Tic-Tac-Toe

Naive solution

Time complexity for move: O(n²)

Space complexity: O(n²)

class TicTacToe:def __init__(self, n: int):
"""
Initialize your data structure here.
"""
self.rows = [[None]*n for _ in range(n)]
self.cols = [[None]*n for _ in range(n)]
self.diag = [None]*n
self.anti_diag = [None]*n
self._moves = 0
self.n = n

def win(self, player):
for row in self.rows:
if set(row)=={player}:return True
for col in self.cols:
if set(col)=={player}:return True
if set(self.diag)=={player} or set(self.anti_diag)=={player}:return True
return False
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.
"""
self._moves +=player
self.rows[row][col] = player
self.cols[col][row] = player
if row==col:self.diag[row]=player
if row+col==self.n-1:self.anti_diag[row]=player
if self._moves<self.n:return 0
return player if self.win(player) else 0
if self._moves>self.n**2:
return 0
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)
Runtime: 2884 ms, faster than 5.12% of Python3 online submissions for Design Tic-Tac-Toe.Memory Usage: 16.5 MB, less than 16.67% of Python3 online submissions for Design Tic-Tac-Toe.

Can we do better?

Yes

Code is from here

class TicTacToe(object):

def __init__(self, n):
self.row, self.col, self.diag, self.anti_diag, self.n = [0] * n, [0] * n, 0, 0, n

def move(self, row, col, player):
offset = player * 2 - 3
self.row[row] += offset
self.col[col] += offset
if row == col:
self.diag += offset
if row + col == self.n - 1:
self.anti_diag += offset
if self.n in [self.row[row], self.col[col], self.diag, self.anti_diag]:
return 2
if -self.n in [self.row[row], self.col[col], self.diag, self.anti_diag]:
return 1
return 0

runtime

Runtime: 92 ms, faster than 55.68% of Python3 online submissions for Design Tic-Tac-Toe.Memory Usage: 16.3 MB, less than 16.67% of Python3 online submissions for Design Tic-Tac-Toe.

Rewrite the code

class TicTacToe:def __init__(self, n: int):
"""
Initialize your data structure here.
"""
self.rows = [0]*n
self.cols = [0]*n
self.diag, self.anti_diag = 0, 0
self.n = n
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.
"""
offset = 1 if player==1 else -1
self.rows[row] += offset
self.cols[col] += offset
if row==col:self.diag += offset
if row+col == self.n-1:self.anti_diag += offset
possible_win_locations = [self.rows[row], self.cols[col], self.diag, self.anti_diag]
if offset*self.n in possible_win_locations:
return player
return 0
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)

It has a similar runtime

Runtime: 80 ms, faster than 96.82% of Python3 online submissions for Design Tic-Tac-Toe.Memory Usage: 16.2 MB, less than 16.67% of Python3 online submissions for Design Tic-Tac-Toe.

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

CS 373 Fall 2020: Samantha Tuapen

Functions in Python

Aurora or Aurora Serverless v2, Which Is More Cost-Effective?

Gherkin: A retrospective

Tutorial-3-(My Experiences)-Dynamic Programming

How Much Does it Cost to Develop an App for Truckers (Features, Development Process, Cost, etc.)

Updating Task-1 using EFS instead of EBS.

Commit-meant Issues!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Alodonor: Availability of Blood Donor Feature on Alodokter Application (UI/UX Case Study)

How has Criterion Evolved and Embraced OTT?

Zomato Restaurant Recommendation System

[NLP] Custom NER Tagging