-
-
Save cdchris12/788b3a80ac1ff53daee9d5179c280df2 to your computer and use it in GitHub Desktop.
Go question
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
#!/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 |
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
#!/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