Instantly share code, notes, and snippets.

# spion/costtest.py

Created July 14, 2012 19:40
Show Gist options
• Save spion/3112995 to your computer and use it in GitHub Desktop.
The lightblub problem - cost testing framework.
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
 # Original problem: # If you have 20 lightbulbs which break at certain height # and a 100 floor bulding, how will you find the maximum # height at which the lightbulbs can withstand the fall? # Modified problem: # For a given cost of climbing one floor (climbCost), # descending one floor (descentCost) and breaking a # lightbulb (breakCost), find the optimal algorithm # that determines the maximum floor # Writing an algorithm: # Write a function f(throw, height, climbCost, descentCost, breakCost) # where: # * throw : testing function. throw(floor) returns true if the # lightbulb didnt break, otherwise returns false. # * height: height of the building, in floors # * climbCost: cost of climbing one floor # * descentCost: cost of going down one floor # * breakCost: cost of breaking a bulb # note: floors start at 0 and end at height - 1 # Test the function using test(f, height, climbCost, descentCost, breakCost) # It will output the average cost of finding the height at which stuff breaks from itertools import product; def test(algorithm, height, climbCost, descentCost, breakCost): cost = 0 location = 0 def makeTestFn(expectedFloor): def testFn(newFloor): # will return true if lamp survives test nonlocal cost, location if (newFloor > expectedFloor): cost += breakCost isClimb = newFloor - location > 0 cost += abs(newFloor - location) * (climbCost if isClimb else descentCost) location = newFloor return newFloor <= expectedFloor return testFn for floor in range(height): result = algorithm(makeTestFn(floor), height, climbCost, descentCost, breakCost) if not(result == floor): raise Exception("Invalid algorithm, wrong result. Expected " + str(floor) + " but got " + str(result)) return cost / height; def simpleClimbSearch(throw, height, climbCost, descentCost, breakCost): floor = 0 while (throw(floor)): floor += 1 return floor - 1 def simpleBinarySearch(throw, height, cl, desc, brk): minF = 0 maxF = height - 1 while (minF < maxF): floor = int(0.5 + (minF + maxF) / 2) if throw(floor): minF = floor else: maxF = floor - 1 return maxF def pessimistSearch(throw, height, cl, desc, brk): minF = 0 oldminF = minF maxF = height - 1 oldmaxF = maxF while (minF < maxF): oldmaxF = maxF oldminF = minF floor = int(minF + 1 + (maxF - minF) / 3) t = throw(floor) if t: minF = floor else: maxF = floor - 1 return maxF def advPessimistSearch(throw, height, cl, desc, brk): minF = 0 oldminF = minF maxF = height - 1 oldmaxF = maxF fac = (desc * height / 4 + 0.1) / (cl * height / 4 + brk + 0.1) if fac > 1: fac = 1 while (minF < maxF): oldmaxF = maxF oldminF = minF floor = int(minF + max(1, (maxF - minF) * fac)) t = throw(floor) if t: minF = floor else: maxF = floor - 1 return maxF fns = [simpleClimbSearch, simpleBinarySearch, pessimistSearch, advPessimistSearch] climbCosts = [0, 1, 3] descentCosts = [0, 1, 3] breakCosts = [0, 10] print("Function Name \t\t Climb \t Desc \t Break \t Cost") for c, d, b, f in product(climbCosts, descentCosts, breakCosts, fns): print(f.__name__, "\t\t", c, "\t", d, "\t", b, "\t", test(f, 100, c, d, b))
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