################################################# # hw10.py # # Your name: # Your andrew id: ################################################# import cs112_f22_week10_linter import math import os import copy import decimal ################################################# # Helper functions ################################################# def almostEqual(d1, d2, epsilon=10**-7): # note: use math.isclose() outside 15-112 with Python version 3.5 or later return (abs(d2 - d1) < epsilon) def roundHalfUp(d): # Round to nearest with ties going away from zero. rounding = decimal.ROUND_HALF_UP # See other rounding options here: # https://docs.python.org/3/library/decimal.html#rounding-modes return int(decimal.Decimal(d).to_integral_value(rounding=rounding)) ################################################# # Functions for you to write ################################################# class Tree(): def __init__(self, nodeValue): pass def getNodeValue(self): return 42 def getChildren(self): return 42 def addChild(self, childTree): pass def __str__(self): return "42" def getStringHelper(self, depth=0): # Use this as needed to help implement __str__ return "42" def getTotalNumNodes(self): return 42 def getHeight(self): return 42 def createFullTree(height, numChildren, valueForAllNodes): return 42 class GameTree(Tree): def __init__(self, nodeValue, myTurn): pass def isMyTurn(self): return True def __str__(self): return "42" def getStringHelper(self, depth=0): # Use this as needed to help implement __str__ return "42" class NimGameTree(GameTree): def __init__(self, numPieces, myTurn): pass def knightsTour(rows, cols): return 42 ################################################# # Test Functions ################################################# def testTree(): print('Testing Tree class....') tree = Tree("purple") assert(type(tree) == Tree) assert(isinstance(tree, Tree)) assert(tree.getNodeValue() == "purple") assert(tree.getChildren() == []) assert(tree.getTotalNumNodes() == 1) assert(str(tree) == """purple\n""") childTree1 = Tree("yellow") assert(tree.addChild(childTree1) == None) assert(len(tree.getChildren()) == 1) assert(tree.getChildren()[0] is childTree1) childTree2 = Tree("red") grandChildTree21 = Tree("purple") childTree2.addChild(grandChildTree21) tree.addChild(childTree2) childTree3 = Tree("green") assert(tree.addChild(childTree3) == None) assert(len(tree.getChildren()) == 3) assert(tree.getTotalNumNodes() == 5) expectedStr = """purple **yellow **red ****purple **green """ assert(str(tree) == expectedStr) assert(tree.getHeight() == 2) assert(tree.getChildren()[0].getHeight() == 0) assert(tree.getChildren()[1].getHeight() == 1) print('Passed!') def testCreateFullTree(): print('Testing createFullTree()....') numChildren = 2 height = 0 value = 99 tree = createFullTree(height, numChildren, value) assert(type(tree) == Tree) assert(tree.getNodeValue() == value) children = tree.getChildren() assert(children == []) assert(tree.getTotalNumNodes() == 1) assert(tree.getHeight() == 0) assert(str(tree) == """99\n""") numChildren = 2 height = 1 value = 99 tree = createFullTree(height, numChildren, value) assert(type(tree) == Tree) assert(tree.getNodeValue() == value) children = tree.getChildren() assert(len(children) == 2) assert(tree.getTotalNumNodes() == 3) assert(tree.getHeight() == 1) assert(type(children[0]) == Tree) assert(type(children[1]) == Tree) assert(str(tree) == """99\n**99\n**99\n""") numChildren = 3 height = 2 value = 88 tree = createFullTree(height, numChildren, value) assert(type(tree) == Tree) assert(tree.getNodeValue() == value) children = tree.getChildren() assert(len(children) == numChildren) assert(type(children[numChildren-1]) == Tree) assert(tree.getTotalNumNodes() == 1+numChildren+numChildren**2) assert(tree.getHeight() == height) assert(str(tree) == """88 **88 ****88 ****88 ****88 **88 ****88 ****88 ****88 **88 ****88 ****88 ****88 """) numChildren = 2 height = 6 value = 99 tree = createFullTree(height, numChildren, value) children = tree.getChildren() assert(len(children) == numChildren) assert(tree.getTotalNumNodes() == 2**(height+1)-1) assert(tree.getHeight() == height) # print(tree) print('Passed!') def testGameTree(): print('Testing GameTree class....') tree = GameTree("purple", False) assert(type(tree) == GameTree) assert(isinstance(tree, GameTree)) assert(isinstance(tree, Tree)) assert(tree.getNodeValue() == "purple") assert(tree.isMyTurn() == False) assert(tree.getChildren() == []) assert(str(tree) == """purple, myTurn=False\n""") move1Tree = GameTree("yellow", True) assert(tree.addChild(move1Tree) == None) assert(len(tree.getChildren()) == 1) assert(tree.getChildren()[0] is move1Tree) move2Tree = GameTree("red", True) move2Child = GameTree("purple", False) move2Tree.addChild(move2Child) tree.addChild(move2Tree) expectedStr = """purple, myTurn=False **yellow, myTurn=True **red, myTurn=True ****purple, myTurn=False """ assert(str(tree) == expectedStr) assert(tree.getHeight() == 2) assert(tree.getChildren()[0].getHeight() == 0) assert(tree.getChildren()[1].getHeight() == 1) board = [ ['X', 'O', 'O'], ['O', 'X', 'X'], [' ', ' ', ' '] ] ticTacToe = GameTree(board, True) for i in range(3): childBoard = copy.deepcopy(board) childBoard[2][i] = 'X' child = GameTree(childBoard, False) for j in range(3): if i != j: grandchildBoard = copy.deepcopy(childBoard) grandchildBoard[2][j] = 'O' grandchild = GameTree(grandchildBoard, True) child.addChild(grandchild) ticTacToe.addChild(child) expectedStr = \ """[['X', 'O', 'O'], ['O', 'X', 'X'], [' ', ' ', ' ']], myTurn=True **[['X', 'O', 'O'], ['O', 'X', 'X'], ['X', ' ', ' ']], myTurn=False ****[['X', 'O', 'O'], ['O', 'X', 'X'], ['X', 'O', ' ']], myTurn=True ****[['X', 'O', 'O'], ['O', 'X', 'X'], ['X', ' ', 'O']], myTurn=True **[['X', 'O', 'O'], ['O', 'X', 'X'], [' ', 'X', ' ']], myTurn=False ****[['X', 'O', 'O'], ['O', 'X', 'X'], ['O', 'X', ' ']], myTurn=True ****[['X', 'O', 'O'], ['O', 'X', 'X'], [' ', 'X', 'O']], myTurn=True **[['X', 'O', 'O'], ['O', 'X', 'X'], [' ', ' ', 'X']], myTurn=False ****[['X', 'O', 'O'], ['O', 'X', 'X'], ['O', ' ', 'X']], myTurn=True ****[['X', 'O', 'O'], ['O', 'X', 'X'], [' ', 'O', 'X']], myTurn=True """ resultStr = str(ticTacToe) assert(resultStr == expectedStr) print('Passed!') def testNimGameTree(): print('Testing NimGameTree() class....') tree = NimGameTree(3, True) # print(tree) assert(type(tree) == NimGameTree) assert(isinstance(tree, NimGameTree)) assert(isinstance(tree, GameTree)) assert(isinstance(tree, Tree)) assert(tree.getNodeValue() == 3) assert(tree.isMyTurn() == True) children = tree.getChildren() assert(len(tree.getChildren()) == 2) take1Child = children[0] take2Child = children[1] assert(type(take1Child) == NimGameTree) assert(type(take2Child) == NimGameTree) assert(take1Child.getNodeValue() == 2) assert(take2Child.getNodeValue() == 1) assert(len(take2Child.getChildren()) == 1) assert(take2Child.getHeight() == 1) assert(take1Child.getHeight() == 2) assert(tree.getHeight() == 3) expectedStr = """1, myTurn=False **0, myTurn=True """ assert(str(take2Child) == expectedStr) expectedStr = """3, myTurn=True **2, myTurn=False ****1, myTurn=True ******0, myTurn=False ****0, myTurn=True **1, myTurn=False ****0, myTurn=True """ assert(str(tree) == expectedStr) tree = NimGameTree(5, False) assert(tree.getHeight() == 5) assert(len(tree.getChildren()) == 2) assert(tree.getChildren()[1].getHeight() == 3) expectedStr = """5, myTurn=False **4, myTurn=True ****3, myTurn=False ******2, myTurn=True ********1, myTurn=False **********0, myTurn=True ********0, myTurn=False ******1, myTurn=True ********0, myTurn=False ****2, myTurn=False ******1, myTurn=True ********0, myTurn=False ******0, myTurn=True **3, myTurn=True ****2, myTurn=False ******1, myTurn=True ********0, myTurn=False ******0, myTurn=True ****1, myTurn=False ******0, myTurn=True """ assert(str(tree) == expectedStr) tree = NimGameTree(11, True) expectedStr = """11, myTurn=True **10, myTurn=False ****9, myTurn=True ******8, myTurn=False ********7, myTurn=True **********6, myTurn=False ************5, myTurn=True **************4, myTurn=False ****************3, myTurn=True ******************2, myTurn=False ********************1, myTurn=True **********************0, myTurn=False ********************0, myTurn=True ******************1, myTurn=False ********************0, myTurn=True ****************2, myTurn=True ******************1, myTurn=False ********************0, myTurn=True ******************0, myTurn=False **************3, myTurn=False ****************2, myTurn=True ******************1, myTurn=False ********************0, myTurn=True ******************0, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ************4, myTurn=True **************3, myTurn=False ****************2, myTurn=True ******************1, myTurn=False ********************0, myTurn=True ******************0, myTurn=False ****************1, myTurn=True ******************0, myTurn=False **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **********5, myTurn=False ************4, myTurn=True **************3, myTurn=False ****************2, myTurn=True ******************1, myTurn=False ********************0, myTurn=True ******************0, myTurn=False ****************1, myTurn=True ******************0, myTurn=False **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True ********6, myTurn=True **********5, myTurn=False ************4, myTurn=True **************3, myTurn=False ****************2, myTurn=True ******************1, myTurn=False ********************0, myTurn=True ******************0, myTurn=False ****************1, myTurn=True ******************0, myTurn=False **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True **********4, myTurn=False ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ******7, myTurn=False ********6, myTurn=True **********5, myTurn=False ************4, myTurn=True **************3, myTurn=False ****************2, myTurn=True ******************1, myTurn=False ********************0, myTurn=True ******************0, myTurn=False ****************1, myTurn=True ******************0, myTurn=False **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True **********4, myTurn=False ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ********5, myTurn=True **********4, myTurn=False ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False **********3, myTurn=False ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ************1, myTurn=True **************0, myTurn=False ****8, myTurn=True ******7, myTurn=False ********6, myTurn=True **********5, myTurn=False ************4, myTurn=True **************3, myTurn=False ****************2, myTurn=True ******************1, myTurn=False ********************0, myTurn=True ******************0, myTurn=False ****************1, myTurn=True ******************0, myTurn=False **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True **********4, myTurn=False ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ********5, myTurn=True **********4, myTurn=False ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False **********3, myTurn=False ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ************1, myTurn=True **************0, myTurn=False ******6, myTurn=False ********5, myTurn=True **********4, myTurn=False ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False **********3, myTurn=False ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ************1, myTurn=True **************0, myTurn=False ********4, myTurn=True **********3, myTurn=False ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ************1, myTurn=True **************0, myTurn=False **********2, myTurn=False ************1, myTurn=True **************0, myTurn=False ************0, myTurn=True **9, myTurn=False ****8, myTurn=True ******7, myTurn=False ********6, myTurn=True **********5, myTurn=False ************4, myTurn=True **************3, myTurn=False ****************2, myTurn=True ******************1, myTurn=False ********************0, myTurn=True ******************0, myTurn=False ****************1, myTurn=True ******************0, myTurn=False **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True **********4, myTurn=False ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ********5, myTurn=True **********4, myTurn=False ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False **********3, myTurn=False ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ************1, myTurn=True **************0, myTurn=False ******6, myTurn=False ********5, myTurn=True **********4, myTurn=False ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False **********3, myTurn=False ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ************1, myTurn=True **************0, myTurn=False ********4, myTurn=True **********3, myTurn=False ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ************1, myTurn=True **************0, myTurn=False **********2, myTurn=False ************1, myTurn=True **************0, myTurn=False ************0, myTurn=True ****7, myTurn=True ******6, myTurn=False ********5, myTurn=True **********4, myTurn=False ************3, myTurn=True **************2, myTurn=False ****************1, myTurn=True ******************0, myTurn=False ****************0, myTurn=True **************1, myTurn=False ****************0, myTurn=True ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False **********3, myTurn=False ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ************1, myTurn=True **************0, myTurn=False ********4, myTurn=True **********3, myTurn=False ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ************1, myTurn=True **************0, myTurn=False **********2, myTurn=False ************1, myTurn=True **************0, myTurn=False ************0, myTurn=True ******5, myTurn=False ********4, myTurn=True **********3, myTurn=False ************2, myTurn=True **************1, myTurn=False ****************0, myTurn=True **************0, myTurn=False ************1, myTurn=True **************0, myTurn=False **********2, myTurn=False ************1, myTurn=True **************0, myTurn=False ************0, myTurn=True ********3, myTurn=True **********2, myTurn=False ************1, myTurn=True **************0, myTurn=False ************0, myTurn=True **********1, myTurn=False ************0, myTurn=True """ resultStr = str(tree) assert(resultStr == expectedStr) print('Passed!') def testKnightsTour(): print('Testing knightsTour()....') def checkDims(rows, cols, ok=True): T = knightsTour(rows, cols) s = f'knightsTour({rows},{cols})' if (not ok): if (T is not None): raise Exception(f'{s} should return None') return True if (T is None): raise Exception(f'{s} must return a {rows}x{cols}' + ' 2d list (not None)') if ((rows != len(T)) or (cols != (len(T[0])))): raise Exception(f'{s} must return a {rows}x{cols} 2d list') d = dict() for r in range(rows): for c in range(cols): d[ T[r][c] ] = (r,c) if (sorted(d.keys()) != list(range(1, rows*cols+1))): raise Exception(f'{s} should contain numbers' + ' from 1 to {rows*cols}') prevRow, prevCol = d[1] for step in range(2, rows*cols+1): row,col = d[step] distance = abs(prevRow - row) + abs(prevCol - col) if (distance != 3): raise Exception(f'{s}: from {step-1} to {step}' + ' is not a legal move') prevRow, prevCol = row,col return True assert(checkDims(4, 3)) assert(checkDims(4, 4, ok=False)) assert(checkDims(4, 5)) assert(checkDims(3, 4)) assert(checkDims(3, 6, ok=False)) assert(checkDims(3, 7)) assert(checkDims(5, 5)) print('Passed!') ################################################# # testAll and main ################################################# def testAll(): testTree() testCreateFullTree() testGameTree() testNimGameTree() testKnightsTour() def main(): cs112_f22_week10_linter.lint() testAll() if (__name__ == '__main__'): main()