Top research firm, Herp & Derp Inc., have been impressed by your problem solving skills this week and decide to hire you to help them solve a problem. They give you two identical eggs and access to a 100 story building. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that's it for that egg.
If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.
How can Herp & Derp Inc. minimize the number of egg drops it takes to find the solution?
Comments:
Anonymous - 10 years, 8 months ago
Since there are no special conditions that make these eggs any stronger than an every day egg, I don't see any other option other than 1 egg dropped at the first floor. The egg will break, so all other 99 floors will yield the same results.
reply permalink
Anonymous - 10 years, 8 months ago
Ah, the pedantic solution. Simple to arrive at, yet completely missing the point of the exercise.
reply permalink
Max Burstein - 10 years, 8 months ago
Could be a chocolate egg or a plastic egg that you hold candy in. In either case what strategy would you employ to minimize the number of drops?
reply permalink
Pegleg - 10 years, 8 months ago
I'll take a crack at it, no pun intended. So I think one approach would be to implement a type of binary search. You would start in the middle and drop the first egg, you would then know if it breaks you have eliminated half of the sample size, else it survives you eliminated the other half. Depending on which you would start in the middle point of the your range, I.E [1-49] or [51-100] and then follow this pattern till you find the floor it doesn't break on and the one it does.
I'd provide more writeup but not enough time today :-X Let me know what you think
reply permalink
Hueho - 10 years, 8 months ago
I thought about a binary search as well, the main problem is that we have only 2 eggs, so after the second egg breaking we wouldn't have found the optimal solution yet.
reply permalink
Pegleg - 10 years, 8 months ago
Ah did not see we only have two eggs :(
reply permalink
Max Burstein - 10 years, 8 months ago
That's definitely a good start. A binary search is essentially that. The issue is that you only have 2 eggs. So if it breaks on floor 50 you have to start at 1 and go all the way up to 49 (worst case scenario of 50 drops). I think you can get it better ;)
reply permalink
toph - 10 years, 8 months ago
The best I can think of is n/3 + 1.
Drop the egg on the 3rd floor. If it breaks, drop the 2nd egg on the 2nd floor. If it breaks, the answer is 1, if it survives the answer is 2.
If the egg on the 3rd floor survives, move up three floors and repeat.
reply permalink
Hartley - 10 years, 8 months ago
Using a binary search algo is on the right track but you've gotta realized that picking "half" (ie 50) as your starting point might not be optimal. Because if the egg breaks at floor 50, then you might need up to 49 more drops (starting at floor 1) to find the right floor.
On the other end of the spectrum if you were to pick "3" as your jump size, as another commenter said, then you'd be able to do the "secondary" search quickly once you find a floor where the first egg breaks, but the "primary" jumps up the tower would be small and slow.
In the worst case, the number of drops you'll end up using is given by a function like this, where Jump Size is the number of floors you skip by on your "primary" drops:
of drops = (# of floors / Jump Size) + Jump Size -1
Optimizing this equation for a 100 floor building, you'll find that the best Jump Size to use is 10 floors. That is, start at floor 10 and keep going up by 10 floors at a time until the first egg breaks. Then, go back to one more than the last floor it was safe on and work your way up one floor at a time.
This lets you discover the exact floor the egg will break on in the least amount of steps. In the worst case, it'll take you 19 drops to get it if it breaks on floor 99, and fewer if the egg breaks on another floor.
reply permalink
Hartley - 10 years, 8 months ago
Yikes, forgot about Markdown formatting. That big line is supposed to say "# of drops..." and not be an h1 title.
reply permalink
annoyed - 10 years, 8 months ago
Yeah. We really need the ability to edit comments...
reply permalink
Carlos - 10 years, 8 months ago
No one seems to have got has low as i did, so here'my though process:
Basically, i think that we have to find the best worst case scenario, so let's go:
We can drop the first egg from the 50th floor and then the other from 1 to 49 or from 51 to 100. That gives us a 50 drops worst case scenario;
We can drop 1 egg every 4 floors and then check the other 3 remaining floors with the other egg. That would be a 27 drops worst case scenario, not good enough... What about 10 drops... and then check the remaining 9 possibilities with the other egg. That would be 19 worst case scenario, that's pretty good.
I think that the best way to handle this problem is to maintain the same number of possibilities with every single number 1 egg drop. Math is definitely not my strong point, i would have to do some research but, if we were to do something like this (and i'm sure there's a formula to explain this): 100 - 1 - 2 - 3 - ... - 14 and we stop at 14 because the result is negative, we get the floor we need to start at, it's the floor 14, and then, we test it, if it doesn't break we go to floor 14 + 13, if it doesn't break, we go to floor 14 + 13 + 12 and so on. The point of this is that we get the (maybe) best worst case scanrio, 14.
At the 14th floor, if it breaks, we have 13 more chances, making a total of 13+1; if it doesn't break, we go to floor 27, if it breaks, we have 12 more chances, making a total of 12+2; if it doesn't break, we go to floor 39, if it breaks, we have 11 more chances, making a total of 11+3, and so on...
I'm not positive that this is the best solution but, i think that this is the best i can do."
reply permalink
Max Burstein - 10 years, 8 months ago
If I understand correctly what you're trying to say I believe you have the correct answer. Nice job!
If you or anyone else is interested in the math behind it checkout http://datagenetics.com/blog/july22012/index.html
reply permalink
Carlos - 10 years, 8 months ago
Ah yes, this makes a lot more sense than my crappy explanation. Basically that's what i was trying to say :D Have a nice weekend!
reply permalink
robert - 10 years, 8 months ago
Try drop the first egg at floor 2, 5, 8, 11, ... if it does not break.
If the first egg breaks at N floor (N is one of 2, 5, 8, ...), then drop another egg at N-2, if it breaks the answer is N-3, otherwise continue drop it at N-1, if it breaks, the answer is N-2, otherwise the answer is N-1.
In another words, after the first egg beaks at the Nth floor (N is 2, 5, 8, 11, ...), we can use another egg to determine the highest floor which should be one of N-3, N-2, N-1 from which an egg being dropped can not break.
reply permalink
Mre64 - 10 years, 6 months ago
The way I see it, there is no way an eggs is going to survive a 1 story fall let alone 99 stories. So we can begin to agree that unless there is some really really soft grass at the bottom, we are going to waste some eggs. So what you can do is go have a good breakfast while you still have two eggs.
ALSO, I think to minimize the amount of eggs being wasted, you should employ a binary search. check at 49 and 50, if it breaks go 24, if not go 75. do what the binary search is intended to do and stop beings so cheap, eggs don't cost that much.
reply permalink
Mre64 - 10 years, 6 months ago
The way I see it, there is no way an eggs is going to survive a 1 story fall let alone 99 stories. So we can begin to agree that unless there is some really really soft grass at the bottom, we are going to waste some eggs. So what you can do is go have a good breakfast while you still have two eggs.
ALSO, I think to minimize the amount of eggs being wasted, you should employ a binary search. check at 49 and 50, if it breaks go 24, if not go 75. do what the binary search is intended to do and stop beings so cheap, eggs don't cost that much.
reply permalink