The lightblub problem - cost testing framework.

costtest.py

# 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))

output

Function Name      		 Climb 	 Desc 	 Break 	 Cost
simpleClimbSearch 		 0 	 0 	 0 	 0.0
simpleBinarySearch 		 0 	 0 	 0 	 0.0
pessimistSearch 		 0 	 0 	 0 	 0.0
advPessimistSearch 		 0 	 0 	 0 	 0.0
simpleClimbSearch 		 0 	 0 	 10 	 10.0
simpleBinarySearch 		 0 	 0 	 10 	 31.6
pessimistSearch 		 0 	 0 	 10 	 26.5
advPessimistSearch 		 0 	 0 	 10 	 9.9
simpleClimbSearch 		 0 	 1 	 0 	 49.5
simpleBinarySearch 		 0 	 1 	 0 	 36.44
pessimistSearch 		 0 	 1 	 0 	 37.46
advPessimistSearch 		 0 	 1 	 0 	 49.49
simpleClimbSearch 		 0 	 1 	 10 	 59.5
simpleBinarySearch 		 0 	 1 	 10 	 68.04
pessimistSearch 		 0 	 1 	 10 	 63.96
advPessimistSearch 		 0 	 1 	 10 	 544.49
simpleClimbSearch 		 0 	 3 	 0 	 148.5
simpleBinarySearch 		 0 	 3 	 0 	 109.32
pessimistSearch 		 0 	 3 	 0 	 112.38
advPessimistSearch 		 0 	 3 	 0 	 148.47
simpleClimbSearch 		 0 	 3 	 10 	 158.5
simpleBinarySearch 		 0 	 3 	 10 	 140.92
pessimistSearch 		 0 	 3 	 10 	 138.88
advPessimistSearch 		 0 	 3 	 10 	 643.47
simpleClimbSearch 		 1 	 0 	 0 	 50.5
simpleBinarySearch 		 1 	 0 	 0 	 37.43
pessimistSearch 		 1 	 0 	 0 	 38.45
advPessimistSearch 		 1 	 0 	 0 	 49.5
simpleClimbSearch 		 1 	 0 	 10 	 60.5
simpleBinarySearch 		 1 	 0 	 10 	 69.03
pessimistSearch 		 1 	 0 	 10 	 64.95
advPessimistSearch 		 1 	 0 	 10 	 59.4
simpleClimbSearch 		 1 	 1 	 0 	 100.0
simpleBinarySearch 		 1 	 1 	 0 	 73.87
pessimistSearch 		 1 	 1 	 0 	 75.91
advPessimistSearch 		 1 	 1 	 0 	 99.97
simpleClimbSearch 		 1 	 1 	 10 	 110.0
simpleBinarySearch 		 1 	 1 	 10 	 105.47
pessimistSearch 		 1 	 1 	 10 	 102.41
advPessimistSearch 		 1 	 1 	 10 	 120.87
simpleClimbSearch 		 1 	 3 	 0 	 199.0
simpleBinarySearch 		 1 	 3 	 0 	 146.75
pessimistSearch 		 1 	 3 	 0 	 150.83
advPessimistSearch 		 1 	 3 	 0 	 198.95
simpleClimbSearch 		 1 	 3 	 10 	 209.0
simpleBinarySearch 		 1 	 3 	 10 	 178.35
pessimistSearch 		 1 	 3 	 10 	 177.33
advPessimistSearch 		 1 	 3 	 10 	 693.95
simpleClimbSearch 		 3 	 0 	 0 	 151.5
simpleBinarySearch 		 3 	 0 	 0 	 112.29
pessimistSearch 		 3 	 0 	 0 	 115.35
advPessimistSearch 		 3 	 0 	 0 	 148.5
simpleClimbSearch 		 3 	 0 	 10 	 161.5
simpleBinarySearch 		 3 	 0 	 10 	 143.89
pessimistSearch 		 3 	 0 	 10 	 141.85
advPessimistSearch 		 3 	 0 	 10 	 158.4
simpleClimbSearch 		 3 	 1 	 0 	 201.0
simpleBinarySearch 		 3 	 1 	 0 	 148.73
pessimistSearch 		 3 	 1 	 0 	 152.81
advPessimistSearch 		 3 	 1 	 0 	 153.81
simpleClimbSearch 		 3 	 1 	 10 	 211.0
simpleBinarySearch 		 3 	 1 	 10 	 180.33
pessimistSearch 		 3 	 1 	 10 	 179.31
advPessimistSearch 		 3 	 1 	 10 	 177.73
simpleClimbSearch 		 3 	 3 	 0 	 300.0
simpleBinarySearch 		 3 	 3 	 0 	 221.61
pessimistSearch 		 3 	 3 	 0 	 227.73
advPessimistSearch 		 3 	 3 	 0 	 299.91
simpleClimbSearch 		 3 	 3 	 10 	 310.0
simpleBinarySearch 		 3 	 3 	 10 	 253.21
pessimistSearch 		 3 	 3 	 10 	 254.23
advPessimistSearch 		 3 	 3 	 10 	 337.95