I saw this problem on a mock interview I spectated online, and decided to take a stab at it. The problem as stated originally asked to find if a given player had won a standard game of tic-tac-toe. However, the code below goes for a more general case where: the matrix size is variable, and the number of markers in a row to win is also variable.
If \$n\$ = height of the board, the solution below is \$O(k * N^2)\$, where \$k\$ is the number of markers needed in a row to win. The gist of the approach is to loop through every position and check downward or forward if it is the starting point of a solution.
One clear issue here is that the information gained from a failed traversal isn't stored. For example, if on the first row we have xxo, breaking the traversal on the 'o' doesn't prevent us from calling "test_forward" even though it will clearly fail on the next index.
What are potential improvements that could be implemented made here?
tests = {'a': [['x','x','o'],
['-','o','x'],
['-','-','x']]}
def test_forward(board, i, j, player, num_needed):
# Check for 3 in a row horizontally (forward)
for k in range(1, num_needed):
if board[i][j+k] != player:
return False
return True
def test_down(board, i, j, player, num_needed):
# Check for 3 in a row vertically (downward)
for k in range(1, num_needed):
if board[i+k][j] != player:
return False
return True
def test_diag_forward(board, i, j, player, num_needed):
# Check for 3 in a row diagonally down and right
for k in range(1, num_needed):
if board[i+k][j+k] != player:
return False
return True
def test_diag_backward(board, i, j, player, num_needed):
# Check for 3 in a row diagonally down and left
for k in range(1, num_needed):
if board[i+k][j-k] != player:
return False
return True
def check_neighbors(board, dimension, i, j, player, num_needed):
if board[i][j] != player:
return False
# Avoid array out of bounds
searchable_space = dimension - num_needed
if j <= searchable_space:
won_forward = test_forward(board, i, j, player, num_needed)
if won_forward:
return True
if i <= searchable_space:
won_down = test_down(board, i, j, player, num_needed)
if won_down:
return True
if j <= searchable_space and i <= searchable_space:
won_diag_forward = test_diag_forward(board, i, j, player, num_needed)
if won_diag_forward:
return True
if j >= num_needed - 1 and i <= searchable_space:
won_diag_backward = test_diag_backward(board, i, j, player, num_needed)
if won_diag_backward:
return True
return False
# Loop through every square and check if it is the starting point of a solution
def has_winner(board, player, num_needed):
dimension = len(board[0])
for i in range(dimension):
for j in range(dimension):
result = check_neighbors(board, dimension, i, j, player, num_needed)
if result == True:
return result
else:
continue
return result
print has_winner(tests['a'], 'x', 3)
