Last active
April 7, 2018 07:33
-
-
Save lxjhk/55f7e8a96a8db234db08d194fe13e7e6 to your computer and use it in GitHub Desktop.
CS170Midterm2-Proof of correctness
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
import random | |
import sys | |
sys.setrecursionlimit(1000) | |
N = 60 # Size of the Chess Board | |
chessBoard = [] # Chess Board Array | |
################### | |
# Helper functions# | |
################### | |
# Memoization decorator | |
class Memoize: | |
def __init__(self, f): | |
self.f = f | |
self.memo = {} | |
print("Memoize Initialisation Called for ", f) | |
def __call__(self, *args): | |
if not args in self.memo: | |
self.memo[args] = self.f(*args) | |
return self.memo[args] | |
# Generate | |
def generateG(): | |
for i in range(N*N): | |
chessBoard.append(random.randint(-6,5)) | |
def G(i,j): | |
return chessBoard[(i - 1)*10 + j] | |
# Printing the chessboard values | |
def printChessBoard(): | |
print("\n\n++++++++++++++ CHESSBOARD ++++++++++++++") | |
for i in range(N): | |
for j in range(N): | |
print('{message: >2}'.format(message=G(i,j)) , end=" ") | |
print("") | |
print("================= CHESSBOARD END =================\n") | |
##################################################################### | |
############### | |
# My Solution # | |
############### | |
# Implementation of my solution | |
@Memoize | |
def TMySolutionRecursion(i, j): | |
if i == j == N: | |
return 0 | |
if i > N or j > N: | |
return 999999 | |
return max(min(G(i,j),G(i,j)+TMySolutionRecursion(i+1,j)), | |
min(G(i,j),G(i,j)+TMySolutionRecursion(i,j+1))) | |
def TMySolution(): | |
k = TMySolutionRecursion(0,0) # Start at 0,0 | |
if k > 0: | |
return 0 # if k > 0, the muminum required is 0 | |
else: | |
return -k # if k < 0, the minimum required is the absolute value of k | |
################## | |
# Given Solution # | |
################## | |
# Implementation of the given solution | |
def TGivenSolution(): | |
return TGivenSolutionRecursion(0,0) | |
@Memoize | |
def TGivenSolutionRecursion(i, j): | |
if i == j == N: | |
return 0 | |
if i > N or j > N: | |
return 999999 | |
return max(min(TGivenSolutionRecursion(i + 1, j), TGivenSolutionRecursion(i, j + 1)) - G(i, j), 0) | |
##################################################################### | |
if __name__ == '__main__': | |
generateG() # Start by generating a new chessboard and fill it with values | |
# Printing the chessboard values | |
printChessBoard() | |
print("\n++++++++++++++ OUTPUT ++++++++++++++") | |
print("Output from my solutino: ", TMySolution(), end="\n") | |
print("Output standard solution: ", TGivenSolution()) | |
print("================= OUTPUT ===============") | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Sample output: