Skip to content

Instantly share code, notes, and snippets.

@cdchris12
Forked from raylu/Makefile
Last active May 23, 2016 17:18
Show Gist options
  • Save cdchris12/788b3a80ac1ff53daee9d5179c280df2 to your computer and use it in GitHub Desktop.
Save cdchris12/788b3a80ac1ff53daee9d5179c280df2 to your computer and use it in GitHub Desktop.
Go question
#!/usr/bin/env python
# Go is a 2 player board game with simple rules. Two players alternate turns
# placing stones on a grid. If a stone is surrounded on 4 sides by stones of
# the opponent, it is captured. If a group of stones are surrounded, they are
# captured.
# See http://en.wikipedia.org/wiki/Rules_of_Go#Capture for a visual explanation.
# Below is an implementation of a Go board. Please write some code in the
# move() method to check for captures and output something when a capture
# occurs. The sample moves represent a capture of two black stones.
from copy import deepcopy
from test import *
EMPTY = 0
BLACK = 1
WHITE = 2
RED = 3
class Board(object):
def __init__(self):
self.board = [[EMPTY] * 19 for _ in xrange(19)] # 2d 19x19 matrix of 0's
# End def
def __str__(self):
s = ''
for row in self.board:
if s:
s += '\n'
# End if
for sq in row:
if sq:
s += str(sq)
else:
s += '_'
# End if/else block
# End for
# End for
return s
# End def
def move(self, color, row, col, test=False):
self.board[row][col] = color
if not test:
print "Row %s, col %s was set to %s." % (row, col, "white" if color == WHITE else "black")
# End if
self.checkNewMove(row, col, color, test)
# End def
def checkNewMove(self, row, col, color, test=False):
new_board = deepcopy(self.board) # Make a copy of the board, just so we won't have to do as much cleaning when we are done
other_color = BLACK if color == WHITE else WHITE
for a in [(0,+1),(0,-1),(+1,0),(-1,0)]:
ret, checked = self.search(row + a[0], col + a[1], other_color, new_board)
if ret: # If we have an enclosure,
checked = set(checked)
for spot in checked:
if not test:
print "Removing tile at row %s, col %s because it was enclosed!!" % (spot[0], spot[1])
self.board[spot[0]][spot[1]] = EMPTY # Remove all the enclosed tiles
# End for
# End if
# End for
# This for loop of if statements is going to do a rudimentary check for each of the 4
# directions a move could touch. Then, we're going to do a search for possible
# enclosures. It is possible for a single piece to enclose three or even four
# sets of squares, so we should check all four touched squares every time.
del new_board # This isn't specifically required, as Python will automatically garbage
# collect this object, but no harm in forcing its hand a bit early.. :-)
# End def
def search(self, row, col, color, new_board):
other_color = BLACK if color == WHITE else WHITE
checked = []
for a in [(0,+1),(0,-1),(+1,0),(-1,0),]:
if new_board[row + a[0]][col + a[1]] == color: # Mark this spot as contiguous
new_board[row + a[0]][col + a[1]] = RED
checked.append( (row + a[0], col + a[1]) ) # Keep track of the spots we've marked as part of this collection
ret, new_checked = self.search(row + a[0], col + a[1], color, new_board) # Use recursion to check cells until we're done
if ret:
for item in new_checked: checked.append(item)
else:
return ( (False, []) )
# End if/else block
elif new_board[row + a[0]][col + a[1]] == EMPTY: # This search is fruitless, as we have discovered an empty space
return ( (False, []) )
# End else/if block
# End for
if checked == []: # This coveres the single enclosed tile case
checked.append( (row,col) )
# End if
return ( (True, checked) )
# End def
# End class
def main():
'''b = Board()
b.move(BLACK, 4, 4)
b.move(BLACK, 4, 5)
b.move(WHITE, 3, 4)
b.move(WHITE, 3, 5)
b.move(WHITE, 4, 3)
b.move(WHITE, 4, 6)
b.move(WHITE, 5, 4)
b.move(WHITE, 5, 5)
print b'''
runTestSuite()
# End def
if __name__ == "__main__":
main()
# End if
#!/usr/bin/env python
# This is the test suite for my go implementation.
from go import *
def runTestSuite():
results = []
results.append( singleEnclosure() )
results.append( doubleEnclosure() )
results.append( quadEnclosure() )
results.append( connDoubleQuadEnclosure() )
results.append( emptySpace() )
if False not in results:
print "-----ALL TESTS PASSED!!-----"
else:
print "-----TESTING FAILED!!-----"
# End if/else block
# End def
def singleEnclosure():
b = Board()
print "Test capturing a single enclosure:"
b.move(BLACK, 4, 4, True)
b.move(BLACK, 5, 3, True)
b.move(WHITE, 5, 4, True)
b.move(BLACK, 5, 5, True)
b.move(BLACK, 6, 4, True)
try:
assert b.board[5][4] == EMPTY
except AssertionError, e:
print b
print "FAIL!!!!\n"
return False
else:
print b
print "PASS!!!!\n"
return True
# End try/except block
# End def
def doubleEnclosure():
b = Board()
print "Test capturing a double enclosure:"
b.move(BLACK, 4, 4, True)
b.move(BLACK, 4, 5, True)
b.move(BLACK, 5, 3, True)
b.move(WHITE, 5, 4, True)
b.move(WHITE, 5, 5, True)
b.move(BLACK, 5, 6, True)
b.move(BLACK, 6, 4, True)
b.move(BLACK, 6, 5, True)
try:
assert b.board[5][4] == EMPTY
assert b.board[5][5] == EMPTY
except AssertionError, e:
print b
print "FAIL!!!!\n"
return False
else:
print b
print "PASS!!!!\n"
return True
# End try/except block
# End def
def quadEnclosure():
b = Board()
print "Test capturing a quad enclosure:"
b.move(BLACK, 4, 4, True)
b.move(BLACK, 4, 5, True)
b.move(BLACK, 5, 3, True)
b.move(WHITE, 5, 4, True)
b.move(WHITE, 5, 5, True)
b.move(BLACK, 5, 6, True)
b.move(BLACK, 6, 3, True)
b.move(WHITE, 6, 4, True)
b.move(WHITE, 6, 5, True)
b.move(BLACK, 6, 6, True)
b.move(BLACK, 7, 4, True)
b.move(BLACK, 7, 5, True)
try:
assert b.board[5][4] == EMPTY
assert b.board[5][5] == EMPTY
assert b.board[6][4] == EMPTY
assert b.board[6][5] == EMPTY
except AssertionError, e:
print b
print "FAIL!!!!\n"
return False
else:
print b
print "PASS!!!!\n"
return True
# End try/except block
# End def
def connDoubleQuadEnclosure():
b = Board()
print "Test capturing a connecting double quad enclosure:"
b.move(BLACK, 4, 4, True)
b.move(BLACK, 4, 5, True)
b.move(BLACK, 5, 3, True)
b.move(WHITE, 5, 4, True)
b.move(WHITE, 5, 5, True)
b.move(BLACK, 5, 6, True)
b.move(BLACK, 5, 7, True)
b.move(BLACK, 6, 3, True)
b.move(WHITE, 6, 4, True)
b.move(WHITE, 6, 5, True)
b.move(WHITE, 6, 6, True)
b.move(WHITE, 6, 7, True)
b.move(BLACK, 6, 8, True)
b.move(BLACK, 7, 4, True)
b.move(BLACK, 7, 5, True)
b.move(WHITE, 7, 6, True)
b.move(WHITE, 7, 7, True)
b.move(BLACK, 7, 8, True)
b.move(BLACK, 8, 6, True)
b.move(BLACK, 8, 7, True)
try:
assert b.board[5][4] == EMPTY
assert b.board[5][5] == EMPTY
assert b.board[6][4] == EMPTY
assert b.board[6][5] == EMPTY
assert b.board[6][6] == EMPTY
assert b.board[6][7] == EMPTY
assert b.board[7][6] == EMPTY
assert b.board[7][7] == EMPTY
except AssertionError, e:
print b
print "FAIL!!!!\n"
return False
else:
print b
print "PASS!!!!\n"
return True
# End try/except block
# End def
def emptySpace():
b = Board()
print "Verifying empty space will not trigger capture:"
b.move(BLACK, 4, 4, True)
b.move(BLACK, 4, 5, True)
b.move(BLACK, 5, 3, True)
b.move(WHITE, 5, 4, True)
#b.move(WHITE, 5, 5, True)
b.move(BLACK, 5, 6, True)
b.move(BLACK, 6, 3, True)
b.move(WHITE, 6, 4, True)
b.move(WHITE, 6, 5, True)
b.move(BLACK, 6, 6, True)
b.move(BLACK, 7, 4, True)
b.move(BLACK, 7, 5, True)
try:
assert b.board[5][4] == WHITE
assert b.board[6][4] == WHITE
assert b.board[6][5] == WHITE
except AssertionError, e:
print b
print "FAIL!!!!\n"
return False
else:
print b
print "PASS!!!!\n"
return True
# End try/except block
# End def
if __name__ == "__main__":
runTestSuite()
# End if
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment