lxjhk/CS170Midterm2.py

## CS170Midterm2.py

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 ===============")

	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 ===============")