Created
June 10, 2022 14:33
-
-
Save jacinator/cd5172366564b638112ff2fd04815b15 to your computer and use it in GitHub Desktop.
Determine if a connect four board is completed
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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