Skip to content

Instantly share code, notes, and snippets.

@jacinator
Created June 10, 2022 14:33
Show Gist options
  • Save jacinator/cd5172366564b638112ff2fd04815b15 to your computer and use it in GitHub Desktop.
Save jacinator/cd5172366564b638112ff2fd04815b15 to your computer and use it in GitHub Desktop.
Determine if a connect four board is completed
class Cell:
ADJACENT = [
(x, y)
for x in range(-1, 2)
for y in range(-1, 2)
if x or y
]
EMPTY = '_'
BLACK = 'B'
WHITE = 'W'
def __init__(self, row, col):
self.row = row
self.col = col
self.cells = {}
self.value = self.EMPTY
def sequence(self, board, direction, *, r=3, v=None):
# An empty cell won't match a sequence of values and always
# means the sequence cannot be completed.
if self.value == self.EMPTY:
return False
# The value, if provided, will be the value of the preceding
# cell in the sequence. If this cell's value doesn't match the
# sequence cannot be completed.
if v and self.value != v:
return False
# If the recursion has reached a depth of four without any
# issues being found the sequence is four matching cells.
if not r:
return True
# Populate the adjacent cell in the current direction if it
# hasn't previously been calculated.
if direction not in self.cells:
# Get the relative values for the current direction and use
# those to modify the current cell's row and col. The
# result is the row and col for the adjacent cell.
row, col = self.ADJACENT[direction]
pos = (self.row + row), (self.col + col)
# Retrieve the position from the board. If the position is
# out of bounds the board will return `None`.
next_ = self.cells[direction] = board[pos]
if next_ is not None:
# Populate the reverse relationship direction on the
# other cell to prevent ever having to perform the
# inverse calculation.
next_.cells[7 - direction] = self
else:
# Retrieve the next, adjacent cell since the current one
# isn't enough to complete the sequence.
next_ = self.cells[direction]
# If the next cell in the sequence is out-of-bounds the
# sequence cannot be completed.
if next_ is None:
return False
# At this point the current cell matches the sequence, but
# isn't enough to complete the sequence. Check the next cell.
return next_.sequence(board, direction, r=r-1, v=self.value)
class Board:
ROWS = range(6)
COLS = range(7)
def __init__(self):
self.grid = [[Cell(row, col) for col in self.COLS] for row in self.ROWS]
def __bool__(self):
return any((
# Retrieve the cell and check if it starts a sequence of
# matching values.
self[(row, col)].sequence(self, direction)
# Loop over the first three rows and four columns. The
# remaining rows and columns don't need to be checked
# because they will hit the edge of the board before they
# can complete a sequence.
for row in self.ROWS[:-3]
for col in self.COLS[:-3]
# Loop over the directions which should be checked. We only
# need to check half of the values since the other half are
# already checked by the preceeding cells.
for direction in range(4, 8)
))
def __contains__(self, pos):
if not isinstance(pos, (list, tuple)):
raise TypeError("'pos' must be a list or tuple")
if len(pos) != 2:
raise ValueError("'pos' must contain exactly two values")
if any((not isinstance(x, int) for x in pos)):
raise TypeError("'pos' must contain two integers")
row, col = pos
return row in self.ROWS and col in self.COLS
def __getitem__(self, pos):
if pos in self:
row, col = pos
return self.grid[row][col]
def __setitem__(self, pos, value):
if pos not in self:
raise ValueError(f"{pos} is not within the board")
row, col = pos
self.grid[row][col].value = value
def render(self):
return '\n'.join((' '.join((x.value for x in y)) for y in self.grid))
if __name__ == '__main__':
board = Board()
board[(0, 0)] = board[(1, 1)] = board[(2, 2)] = board[(3, 3)] = Cell.BLACK
print(board.render())
print('>>>', bool(board))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment