Assignment Week 12

Imported Code

Project Code

queenArray = [[]] nQueens = 0 def deepcopy(array): if not isinstance(array, list): return array newArray = [] for x in range(len(array)): newArray.append(deepcopy(array[x])) return newArray def printArray(printNo): for row in range(nQueens): #print(" -" * nQueens) outStr = "|" for col in range(nQueens): outStr += queenArray[printNo][row][col] outStr += "|" outStr = outStr.replace("x", " ") print outStr #print(" -" * nQueens) def placeQueen(row): if row >= nQueens: return True for col in range(nQueens): if queenArray[row][row][col] != "x": queenArray[row + 1] = deepcopy(queenArray[row]) queenArray[row + 1][row][col] = "Q" if checkQueen(row + 1, col): return True return False def checkQueen(row, col): offset = 0 for i in range(row, nQueens): offset += 1 if queenArray[row][i][col] == "Q": return False else: queenArray[row][i][col] = "x" if not (col - offset) < 0: if queenArray[row][i][col - offset] == "Q": return False else: queenArray[row][i][col - offset] = "x" if not (col + offset) >= nQueens: if queenArray[row][i][col + offset] == "Q": return False else: queenArray[row][i][col + offset] = "x" return placeQueen(row) def solveNQueens(N): global queenArray, nQueens queenArray = [[]] nQueens = N for i in range(nQueens): queenArray[0].append([]) queenArray.append([]) for j in range(nQueens): queenArray[0][i].append(" ") if placeQueen(0): printArray(nQueens) else: print("No solution possible!")

Commands

solveNQueens(8)

Output

Imported Code

Project Code

def mileage(m, d): for i in range(1, len(d)): d[-i] = d[-i] - d[-i-1] currGas = m for i in range(len(d)): if d[i] > currGas: currGas = m print("Stop at gas station " + i.__str__()) currGas -= d[i] #Runtime efficiency is O(n) #Proof of correctness - # The definition of most efficient is 'fewest stops' # We assume that this solution is not the most efficient # Therefore, at some point, the algorithm has enforced a stop where none is necessary # This requires that there be a station within the mileage of the car that nonetheless we ignore and stop before # However, for each station, we check to see whether we can reach the next station before deciding to stop # Therefore, we cannot, by the enforcement of the algorithm, stop before we have to # Therefore, the algorithm has not enforced an unnecessary stop # Therefore our assumption is wrong, and this is the most efficient algorithm

Commands

mileage(300, [175, 295, 355, 450, 660, 810])

Output

Imported Code

Project Code

string = ['', ''] maxCount = 0 count = 0 placeHolder = 0 def findNextMatch(char): global placeHolder, count while placeHolder < (len(string[1])): if string[1][placeHolder] == char: count += 1 placeHolder += 1 return True placeHolder += 1 return False def eachSubstr(counter=0, checkString=''): global placeHolder, count, maxCount if counter == len(string[0]): count = 0 placeHolder = 0 check = False for char in checkString: check = findNextMatch(char) if check: maxCount = max(count, maxCount) return eachSubstr(counter + 1, checkString) eachSubstr(counter + 1, checkString + string[0][counter]) def commonSubstring(string1, string2): global string, maxCount, count, placeHolder string = ['', ''] maxCount = 0 count = 0 placeHolder = 0 string[0] = string1 string[1] = string2 eachSubstr() print("Maximum length of the common subsequence is " + maxCount.__str__())

Commands

commonSubstring("acegikmoqsuwy", "adgjmpsvy")

Output

Imported Code

Project Code

firstValue = 0 def _findMaxValue(checkArray): if len(checkArray) == 1: print("Max value is " + checkArray[0].__str__()) return middle = len(checkArray) // 2 if checkArray[middle] > firstValue: _findMaxValue(checkArray[middle:]) else: _findMaxValue(checkArray[:middle]) def findMaxValue(checkArray): global firstValue firstValue = checkArray[0] _findMaxValue(checkArray)

Commands

findMaxValue([5,6,7,8,9,0,1,2,3,4])

Output