I came across this neat problem and wanted to hear your solution for it. No cheating.
You have two identical light bulbs, and a 100 story building. You want to find out from which story (if any) the light bulbs will break when dropped. Come up with an algorithm that minimizes the maximum drops (keeping in mind that once a light bulb breaks, you can't reuse it). Once you've done that, try to find the general solution!
start at 50 then go up one (51). Then go to 1 below (49). if it doesn't break at 51 go higher and skip 49. If it breaks at 51 then go to 49 and if it breaks go lower if not then its 50.
Ehh, I think I have it.
Assuming the breaking threshhold has an even chance to be at any floor 1-100, drop the first at floor 50 for optimal efficiency. Keep record of tested and untested floors.
If the last bulb broke, drop the current bulb halfway between the last tested floor and either the closest tested floor below the last one or (if there are no tested floors below the last tested floor), floor 1. Round to nearest floor if necessary.
If the last bulb survived, drop the current bulb halfway between the last tested floor and either the closest tested floor above the last one or (if there are no tested floors above the last tested floor), floor 100. Round to nearest floor if necessary.
Iterate algorithm until the current floor for testing is the same as the last tested floor. If the bulb survived the drop from this floor, this floor is the maximum height the bulb will survive. If the bulb did not survive the drop from this floor, the floor below it is the maximum height the bulb will survive.
I think I overdid it just a bit, but I hope it makes sense.
--
It sort of pintpoints the value you're looking for and the accuracy increases for each test, but this experiment would necessitate accuracy to the one's place.
eg 50 > 75 > 62.5 > 68.25 > ...
Whether you go up or down is as random as the number you're targeting is. (:
0rac343: I'm not sure your algorithm is fully specified. Are you saying drop it at the fifty, and if it breaks, drop it at the 49, otherwise drop it at the 51? What if both bulbs break? Then you're out of bulbs.
Progbeard: That's what's called binary search, and, unfortunately, it doesn't work. If you dropped it at the 50 and it broke, you'd then drop it at 25. If the break threshold is actually 24, your second bulb will break. You will then not have any bulbs.
Go up from floor 1 by tens, say, dropping one light bulb. The first time the bulb breaks, go to the last step where it didn't break, and go up by ones. The more light bulbs you have, the bigger the steps you can take; if you had three, for instance, you could divide the search space in half at floor 50 with the first bulb first.
That is right, so what's the maximum tries it will take in that case, and what's the general solution for n bulbs and m floors?
merthsoft wrote:
That is right, so what's the maximum tries it will take in that case, and what's the general solution for n bulbs and m floors?
So for two bulbs and 100 floors, best case is bulb one breaks on floor 11 and bulb two breaks on floor 2, a total of three tries. The worst case would be bulb one does not break by floor 91, which is nine tries so far, then you should drop it at 95, ten tries, and if it did break, you'd have to try at 92 and 93, so if it didn't break, 94 is the solution, twelve total tries. But if you tried to 91, and it broke at 91 after nine tries, then go from 82, and the second breaks at 90, which is eighteen. Therefore the worst is 18 for this scenario. I'll get back to you with the general case.
Start at the first floor and drop a lightbulb. If it doesn't break, drop a lightbulb from the next power of 2 floor (2,4,8,16,32,64) and repeat until it breaks. Then, divide the floor you last tested the lightbulb on by 2 and start dropping the other lightbulb from that floor. If it doesn't break, drop it from the next floor and repeat until it breaks.
Edit: ninja'd >_<
Souvik's solution is a lot like mine. I'd really like to see the three battle it out for experimental prob.
Maybe I didn't understand the problem. :\
Aren't you trying to find the maximum floor a bulb can be survive a drop from in the least amount of drops?
--
If your goal is to find the threshold between breaking and not breaking, you'd have to drop a bulb from a random floor and hope that bulb is on that threshold (1/100 chance) and then drop a bulb above or below that and hope the outcome is the opposite (1/2 chance, 1/1 chance on floors 100 and 1)...so...there's something I'm not getting. Stupid question, but is there realism in that bulbs have an exponentially increased chance to break as you go up? If so then I feel stupid.
Keep in mind you only have two bulbs, so once you've broken two, you've got none left!
Souvik: your worst case is it breaks at 64 and not at 63, so you had to do 7+31 = 38 drops.
merthsoft wrote:
That is right, so what's the maximum tries it will take in that case, and what's the general solution for n bulbs and m floors?
{with quick edit to make it easy to test against other implementations}
Code: #!/usr/bin/env python
from random import randint
from sys import argv
def closest(n):
return int(round(n))
def findBreakingPoint(n,m,b):
low = 0.
work = 0
for i in range(1,n+1):
broken = False
print "i=%d Step=%d" % (i,(m ** ((n-i)/float(n))))
while not broken and closest(low) < m:
next = low + (m ** ((n-i)/float(n)))
work += 1
if closest(next) >= b:
broken = True
print "Broke at",next
else:
low = next
print "Held at",low
if not broken:
print "Something went wrong, m=%d, n=%d, b=%d, low=%f" % (m,n,b,low)
print "Found break point between %d and %d in %d steps" % (low,next,work)
if __name__ == '__main__':
n = int(argv[1]) #lightbulbs
m = int(argv[2]) #floors
b = int(argv[3]) if len(argv) > 3 else randint(1,m)
print "Break point at",b
findBreakingPoint(n,m,b)
Explain it in English for our non-python reading members
I'm starting from floor 0 (which doesn't count as a drop, since it's resting on the ground) because it makes the edge cases easier. For i in [1,n], increment your current floor by m^((n-i)/n)) (or the nth root of m raised to n-i). When your ith bulb breaks, you go back one step, and increment i.
For m=100, n=2, this replicates Kerm's solution but properly handles the edge case on the top floor.
Yeah, I forgot to mention the top case until I was describing my worst-case calculations, unfortunately; thanks for that. And of course good job on the code.
This is all a moot point since I know from experience a lightbulb will break from less than 5 feet of free-fall.
DShiznit wrote:
This is all a moot point since I know from experience a lightbulb will break from less than 5 feet of free-fall.
I'd say closer to three feet, personally. 
Luckily we're dealing with special resilient lightbulbs that consistently break at a sudden threshold of impact force.
Oh, interview questions... anyhoot, here's an adaptation of the egg/lightbulb problem.
You have two identical lightbulbs, and a 100 story building. You want to find out from which story (if any) the lightbulbs will break when dropped. Unfortunately, you're a CS major, so you're physically incapable of walking up 100 stories - how can you minimize the average/expected distance you traverse? You may start from any floor.
But does being a CS major have to do with being physically fit? I'm fit and a CS major. I find this question offensive. Also, do we have to take into account retrieving the unbroken lightbulb each time?>
KermMartian wrote:
But does being a CS major have to do with being physically fit? I'm fit and a CS major. I find this question offensive. Also, do we have to take into account retrieving the unbroken lightbulb each time?>
What the world thinks of CS majors
http://1.bp.blogspot.com/_dJylj_lumkc/Sw6be8EdSQI/AAAAAAAAAEk/zO1YVpaoKzQ/s1600/really-fat-guy-on-computer.jpg (may want eye bleach)
The truth about CS majors
