The Two Egg Problem • Hacker News Board

Re: The Two Egg Problem

#11

Post by chris_wot » Sat, Jul 21, 2012, 3:04 PM UTC

columbo wrote: post #8

chris_wot wrote: post #6

Earlier quoted context omitted.

"There are no tricks, gotchas or other devious ruses. Don’t rat-hole with issues related to terminal velocity, potential energy or wind resistance. This is a math puzzle plain and simple." Not within the rules!

"There are no tricks, gotchas or other devious ruses. Don’t rat-hole with issues related to terminal velocity, potential energy or wind resistance. This is a math puzzle plain and simple." Not out of the rules either (according to what you just posted). At some point you need to crush an egg. If the rules are implying that you can only do X and we are only looking for solution Y then why are we even talking about thi…

"This is a math puzzle, plain and simple" is the give away.

Re: The Two Egg Problem

#12

Post by Confusion » Sat, Jul 21, 2012, 3:13 PM UTC

What isn't explained, is why the solution that 'make(s) solutions to all possible answers the same depth' is also the solution that minimizes the average number of attempts needed for many (sets of) eggs. The motivation given is to reduce the worst case. That doesn't explain why there isn't perhaps a solution with a worse worst case, but a lower average number of drops.

Re: The Two Egg Problem

#13

Post by JeanPierre » Sat, Jul 21, 2012, 3:22 PM UTC

From the text:

We now have all the information to compute the optimal two egg solution.

While I prefer to read about algorithms and strategies in the fashion the author writes, I'm a bit sad that there's is no proof (or informal reasoning) why this is the optimal solution. Does anyone have a paper or some reasoning which will make me believe that this is the optimal solution?

Re: The Two Egg Problem

#14

Post by slig » Sat, Jul 21, 2012, 3:39 PM UTC

Lots of interesting stuff in that blog, be sure to check it.

Re: The Two Egg Problem

#15

Post by btilly » Sat, Jul 21, 2012, 3:48 PM UTC

Confusion wrote: post #12

What isn't explained, is why the solution that 'make(s) solutions to all possible answers the same depth' is also the solution that minimizes the average number of attempts needed for many (sets of) eggs. The motivation given is to reduce the worst case. That doesn't explain why there isn't perhaps a solution with a worse worst case, but a lower average number of drops.

Indeed it is not obvious. For example there are clearly cases where there are solutions with the same worst case and different worst cases. And in the slight variation where the cost of dropping an egg is the height at which you drop it, the solutions that reduce worst cost and average cost tend to be different.

Re: The Two Egg Problem

#16

Post by antidoh » Sat, Jul 21, 2012, 3:48 PM UTC

dsr_ wrote: post #2

The blog author is very smart. However, he is not very clever. From my experience in the real world, I know that an unprotected egg will smash when dropped from one story, guaranteed. No need to go up 14 or 27 or even two stories. (I also know that it is possible to devise protective enclosures to keep an egg from breaking when dropped from 6 stories. The Society of Women Engineers often sponsors competitions. Been t…

Suspension of disbelief: https://en.wikipedia.org/wiki/Suspension_of_disbelief

"This is a math puzzle plain and simple."

You're being asked to accept that it's possible for an egg, or some other fragile object like, say, a baby, to survive a drop from the first or any other floor, and proceed to solve the math problem.

Re: The Two Egg Problem

#17

Post by kbgrant » Sat, Jul 21, 2012, 4:01 PM UTC

I was asked this question at a Google interview in 2006. At that time I worked it out mathematically as the author has here. Only afterwards did I realize that it is a simple Dynamic Programming problem.

Let f(y) be the number of drops required with y floors remaining. At a drop from floor x, either the egg breaks and you must test all floors from 1 to x-1, or else the egg does not break and you have reduced to a smaller sub-problem with y-x floors. So the number of drops required is 1 (for the current drop) plus the max of either x-1 or f(y-x). We simply minimize this value over all potential floors x from 1 to y.

Here is a solution in C++: https://gist.github.com/3156157

Re: The Two Egg Problem

#18

Post by lunchbox » Sat, Jul 21, 2012, 4:04 PM UTC

An issue with this puzzle is that the objective is not clearly stated upfront. The author should make it clear from the outset that the goal is to minimize the number of drops in the worst case, rather than to minimize the average case, especially since optimizing the average case is (in my experience) more common in optimization problems. He asks in parentheses what the worst case is, but that just sounds like a side question:

> The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution? (And what is the worst case for the number of drops it will take?)

Then in the solution he says:

> Problems where the solution lays lower down the building are taking less drops than when the solution lays higher up. We need to come up with a strategy that makes things more uniform.

It is not explained why it has to be more uniform.

A more minor issue with this puzzle is that for the sake of thoroughness, the author should say is that the number of floors required to break the egg follows a uniform distribution (i.e., every floor is an equally likely candidate).

Re: The Two Egg Problem

#19

Post by benihana » Sat, Jul 21, 2012, 4:10 PM UTC

dsr_ wrote: post #5

misnome wrote: post #3

Earlier quoted context omitted.

Yeah. I dropped an egg from the kitchen counter and it broke. Ergo, first floor it would break. Except of course, the article doesn't mention what the landing surface is, or whether it is what we think of as an egg, or some hypothetical super-egg. This would seem to be discounted by the "There are no tricks, gotchas or other devious ruses" clause, however. If the point of the article is to make it purely a mathematic…

All it would take to remove the real-world problem would be to change the object from an egg to a ball made of a material of unknown strength and toughness. Poor specifications lie at the root of many a programming problem.

Yes but this isn't a programming problem. It's a math thought experiment.

The real thing I'm wondering is why are you making a big deal about this? You obviously have the mental capacity to come up with the concept that it's a special material, why can't you just pretend that's what it is and not make a big pedantic joke about it? What is added to this discussion by pointing out something we all know - that eggs break when you drop them from shoulder height.

Re: The Two Egg Problem

#20

Post by numlocked » Sat, Jul 21, 2012, 4:14 PM UTC

I was asked this question in a google interview earlier this year. Neither I nor the interviewer got past the "every 10 floors" approach (though I did make it through that round of interviews!). Interesting to see there was more meat on that bone.