Last active
December 23, 2019 18:41
-
-
Save slanterns/af35b17dc5f198b2969359dc09d8998c to your computer and use it in GitHub Desktop.
This file contains hidden or 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
| import math | |
| class Tboard(object): | |
| def __init__(self, data): | |
| self.data = data | |
| self.complete = False | |
| self.rotateCnt = 0 | |
| self.mirrored = False | |
| self.impo = False | |
| def hash(self): | |
| return sum([self.data[i] * (2 ** i) for i in range(9)]) | |
| def fold(self): | |
| return [[self.data[3 * i + j] for j in range(3)] for i in range(3)] | |
| def foldRev(self): | |
| return [[self.data[3 * j + i] for j in range(3)] for i in range(3)] | |
| def flatten(self, foldedList): | |
| return [foldedList[i][j] for i in range(3) for j in range(3)] | |
| def judgeLine(self, line): | |
| return all([(True if i == 1 else False) for i in line]) | |
| def judge(self): | |
| foldBoard = self.fold() | |
| foldRevBoard = self.foldRev() | |
| resultList = [any([self.judgeLine(line) for line in foldBoard]), | |
| any([self.judgeLine(line) for line in foldRevBoard]), | |
| self.judgeLine([self.data[4 * i] for i in range(3)]), | |
| self.judgeLine([self.data[2 * (i + 1)] for i in range(3)])] | |
| return any(resultList) | |
| def mirror(self): | |
| temp = self.fold() | |
| tempMirroredFolded = [[temp[i][2 - j] for j in range(3)] for i in range(3)] | |
| tempMirroredFoldedFlattened = Tboard(self.flatten(tempMirroredFolded)) | |
| tempMirroredFoldedFlattened.mirrored = not self.mirrored | |
| tempMirroredFoldedFlattened.rotateCnt = self.rotateCnt | |
| return tempMirroredFoldedFlattened | |
| def rotate(self): | |
| temp = self.fold() | |
| tempMirroredRotated = [[temp[2 - j][i] for j in range(3)] for i in range(3)] | |
| tempMirroredRotatedFlattened = Tboard(self.flatten(tempMirroredRotated)) | |
| tempMirroredRotatedFlattened.rotateCnt = self.rotateCnt + 1 | |
| tempMirroredRotatedFlattened.mirrored = self.mirrored | |
| return tempMirroredRotatedFlattened | |
| game = {'A':Tboard([0] * 9), 'B':Tboard([0] * 9), 'C':Tboard([0] * 9)} | |
| def parseable(cStr): | |
| return True | |
| def check(game): | |
| for lable in game.keys(): | |
| if game[lable].judge(): | |
| game[lable].complete = True | |
| def printBlock(board, num): | |
| if board[num] == 0: | |
| return num | |
| else: | |
| return 'X' | |
| def move(lable, number): | |
| if (not game[lable].complete) and game[lable].data[number] == 0: | |
| game[lable].data[number] = 1 | |
| return True | |
| return False | |
| def cusPrint(game): | |
| (a, b, c) = (game['A'], game['B'], game['C']) | |
| print " ".join(('' if a.complete else 'A') + ('' if b.complete else 'B') + ('' if c.complete else 'C')) | |
| for i in range(3): | |
| if not a.complete: | |
| print printBlock(a.data, 3 * i + 0), printBlock(a.data, 3 * i + 1), printBlock(a.data, 3 * i + 2), | |
| if not b.complete or not c.complete: | |
| print '', | |
| if not b.complete: | |
| print printBlock(b.data, 3 * i + 0), printBlock(b.data, 3 * i + 1), printBlock(b.data, 3 * i + 2), | |
| if not c.complete: | |
| print '', | |
| if not c.complete: | |
| print printBlock(c.data, 3 * i + 0), printBlock(c.data, 3 * i + 1), printBlock(c.data, 3 * i + 2), | |
| return | |
| def decode(hashC): | |
| tempL = [] | |
| for _ in range(9): | |
| tempL.append(hashC % 2) | |
| hashC = hashC // 2 | |
| return Tboard(tempL) | |
| def match1(tb): | |
| if f1(tb.hash()): | |
| return (tb, f1(tb.hash())) | |
| if f1(tb.rotate().hash()): | |
| return (tb.rotate(), f1(tb.rotate().hash())) | |
| if f1(tb.rotate().rotate().hash()): | |
| return (tb.rotate().rotate(), f1(tb.rotate().rotate().hash())) | |
| if f1(tb.rotate().rotate().rotate().hash()): | |
| return (tb.rotate().rotate().rotate(), f1(tb.rotate().rotate().rotate().hash())) | |
| if f1(tb.mirror().hash()): | |
| return (tb.mirror(), f1(tb.mirror().hash())) | |
| if f1(tb.mirror().rotate().hash()): | |
| return (tb.mirror().rotate(), f1(tb.mirror().rotate().hash())) | |
| if f1(tb.mirror().rotate().rotate().hash()): | |
| return (tb.mirror().rotate().rotate(), f1(tb.mirror().rotate().rotate().hash())) | |
| if f1(tb.mirror().rotate().rotate().rotate().hash()): | |
| return (tb.mirror().rotate().rotate().rotate(), f1(tb.mirror().rotate().rotate().rotate().hash())) | |
| def match2(tb): | |
| if f2(tb.hash()): | |
| return (tb, f2(tb.hash())) | |
| if f2(tb.rotate().hash()): | |
| return (tb.rotate(), f2(tb.rotate().hash())) | |
| if f2(tb.rotate().rotate().hash()): | |
| return (tb.rotate().rotate(), f2(tb.rotate().rotate().hash())) | |
| if f2(tb.rotate().rotate().rotate().hash()): | |
| return (tb.rotate().rotate().rotate(), f2(tb.rotate().rotate().rotate().hash())) | |
| if f2(tb.mirror().hash()): | |
| return (tb.mirror(), f2(tb.mirror().hash())) | |
| if f2(tb.mirror().rotate().hash()): | |
| return (tb.mirror().rotate(), f2(tb.mirror().rotate().hash())) | |
| if f2(tb.mirror().rotate().rotate().hash()): | |
| return (tb.mirror().rotate().rotate(), f2(tb.mirror().rotate().rotate().hash())) | |
| if f2(tb.mirror().rotate().rotate().rotate().hash()): | |
| return (tb.mirror().rotate().rotate().rotate(), f2(tb.mirror().rotate().rotate().rotate().hash())) | |
| def undo(ttb, solution): | |
| tsolu = decode(solution) | |
| if (ttb.rotateCnt % 4) == 0: | |
| tsolu = tsolu | |
| elif (ttb.rotateCnt % 4) == 1: | |
| tsolu = tsolu.rotate().rotate().rotate() | |
| elif (ttb.rotateCnt % 4) == 2: | |
| tsolu = tsolu.rotate().rotate() | |
| elif (ttb.rotateCnt % 4) == 3: | |
| tsolu = tsolu.rotate() | |
| if ttb.mirrored: | |
| tsolu = tsolu.mirror() | |
| return tsolu | |
| def getNextStep1(tb): | |
| (ttb, solution) = match1(tb) | |
| tsolu = undo(ttb, solution) | |
| dif = tsolu.hash() - tb.hash() | |
| nextStep = int(math.log(dif, 2)) | |
| return nextStep | |
| def getNextStep2(tb): | |
| (ttb, solution) = match2(tb) | |
| tsolu = undo(ttb, solution) | |
| dif = tsolu.hash() - tb.hash() | |
| nextStep = int(math.log(dif, 2)) | |
| return nextStep | |
| def rest(game): | |
| return sum([(0 if game[lable].complete else 1) for lable in game.keys()]) | |
| def f1(hash): | |
| if hash == 1: | |
| return 257 | |
| if hash == 2: | |
| return 130 | |
| if hash == 259: | |
| return 387 | |
| if hash == 261: | |
| return 325 | |
| if hash == 134: | |
| return 198 | |
| if hash == 138: | |
| return 170 | |
| if hash == 17: | |
| return 21 | |
| if hash == 18: | |
| return 82 | |
| if hash == 149: | |
| return 157 | |
| if hash == 90: | |
| return 346 | |
| if hash == 29: | |
| return 157 | |
| if hash == 161: | |
| return 417 | |
| if hash == 419: | |
| return 427 | |
| if hash == 426: | |
| return 427 | |
| if hash == 114: | |
| return 370 | |
| return False | |
| def f2(hash): | |
| if hash == 257: | |
| return 273 | |
| if hash == 130: | |
| return 146 | |
| if hash == 3: | |
| return 7 | |
| if hash == 5: | |
| return 7 | |
| if hash == 417: | |
| return 433 | |
| if hash == 17: | |
| return 273 | |
| if hash == 18: | |
| return 146 | |
| if hash == 160: | |
| return 161 | |
| if hash == 33: | |
| return 161 | |
| if hash == 163: | |
| return 167 | |
| if hash == 165: | |
| return 167 | |
| if hash == 177: | |
| return 433 | |
| return False | |
| def main(): | |
| cusPrint(game) | |
| move('A', 4) # Our first step | |
| print("Player 1: A4") | |
| cusPrint(game) | |
| impoDetered = False | |
| while True: | |
| p2LastMove = () | |
| while True: # Opponent's turn | |
| tStr = raw_input("Player 2: ") | |
| if not parseable(tStr): | |
| print "Invalid move, please input again" | |
| else: | |
| (lable, number) = (tStr[0], int(tStr[1])) | |
| if not move(lable, number): | |
| print "Invalid move, please input again" | |
| else: | |
| p2LastMove = (lable, number) | |
| break | |
| check(game) | |
| if rest(game) == 0: | |
| print "Player 1 wins game" | |
| break | |
| cusPrint(game) | |
| # Our turn | |
| if game[p2LastMove[0]].hash() == 2 ** p2LastMove[1]: # p2 moves to an empty board | |
| move(('B' if p2LastMove[0] == 'C' else 'C'), 4) | |
| print "Player 1: " + ('B' if p2LastMove[0] == 'C' else 'C') + "4" | |
| cusPrint(game) | |
| if rest(game) == 2 and (not impoDetered): | |
| restGameLables = [lable for lable in game.keys() if not game[lable].complete] | |
| if (game[restGameLables[0]].hash() == 16) ^ (game[restGameLables[1]].hash() == 16): | |
| game[restGameLables[(0 if game[restGameLables[0]].hash() == 16 else 1)]].impo = True | |
| impoDetered = True | |
| continue | |
| if rest(game) == 2 and (not impoDetered): | |
| restGameLables = [lable for lable in game.keys() if not game[lable].complete] | |
| if (game[restGameLables[0]].hash() == 16) ^ (game[restGameLables[1]].hash() == 16): | |
| game[restGameLables[(0 if game[restGameLables[0]].hash() == 16 else 1)]].impo = True | |
| impoDetered = True | |
| if rest(game) == 3: | |
| nextStep = getNextStep2(game[p2LastMove[0]]) | |
| move(p2LastMove[0], nextStep) | |
| print "Player 1: " + p2LastMove[0] + str(nextStep) | |
| check(game) | |
| cusPrint(game) | |
| if rest(game) == 2 and (not impoDetered): | |
| restGameLables = [lable for lable in game.keys() if not game[lable].complete] | |
| if (game[restGameLables[0]].hash() == 16) ^ (game[restGameLables[1]].hash() == 16): | |
| game[restGameLables[(0 if game[restGameLables[0]].hash() == 16 else 1)]].impo = True | |
| impoDetered = True | |
| elif rest(game) == 2: | |
| if game[p2LastMove[0]].impo: | |
| nextStep = getNextStep1(game[p2LastMove[0]]) | |
| move(p2LastMove[0], nextStep) | |
| print "Player 1: " + p2LastMove[0] + str(nextStep) | |
| check(game) | |
| cusPrint(game) | |
| else: | |
| nextStep = getNextStep2(game[p2LastMove[0]]) | |
| move(p2LastMove[0], nextStep) | |
| print "Player 1: " + p2LastMove[0] + str(nextStep) | |
| check(game) | |
| cusPrint(game) | |
| else: | |
| (restGameLable,) = [lable for lable in game.keys() if not game[lable].complete] | |
| nextStep = getNextStep1(game[restGameLable]) | |
| move(restGameLable, nextStep) | |
| print "Player 1: " + restGameLable + str(nextStep) | |
| check(game) | |
| cusPrint(game) | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment