Throwing eggs from a building

10

1

This is exercise problem 1.4.24 from Robert Sedgewick's Algorithms 4th Edition.

Suppose that you have an N-story building and plenty of eggs. Suppose also that
an egg is broken if it is thrown off floor F or higher, and unhurt otherwise.
First, devise a strategy to determine the value of F such that the number of
broken eggs is ~lgN when using ~lgN throws, then find a way to reduce the cost to
~2lgF.

While the lgN solution is easy to think up, I totally have no idea about the 2lgF solution. Anyway, we are not given the value of F, so where the ground of 2lgF solution is?

Can anyone give some light on this question? Thanks.

Guibao Wang

Posted 2013-07-01T12:36:15.557

Reputation: 125

it's a search problem given an ordered set. maybe that helps :). – Randy – 2013-07-01T12:38:08.553

Hay Randy, any links or further reading? – Guibao Wang – 2013-07-01T12:39:39.103

Do binary search on the building, drop from n/2 floor, if it is broken, then go down which is n/4 and so one. So u may break at most lgN eggs and will get to that point in lgN steps – Elbek – 2013-07-01T12:41:40.287

possible duplicate of Generalised Two-Egg Puzzle

– David Eisenstat – 2013-08-03T00:39:11.277

Answers

15

logN: start at the top, always cut search space in half -> binary search

2 * logF start at 1, next 2, 4, 8 (i.e., 2^i), once the egg breaks (after log F steps) do binary search in the smaller search space (range < F and hence number of searches < log F) --> exponential search

b.buchhold

Posted 2013-07-01T12:36:15.557

Reputation: 2 844

Nice explanation, very useful. @timothy-shields your solution's good as well, thanks very much. – Guibao Wang – 2013-07-01T12:54:02.447

And how does that determine the value of F? – Pavel – 2015-04-30T09:32:48.070

I don't understand how in the lgN part we get lgN broken eggs with lgN throws, if we keep dividing we get to the 1st floor at the end, but what if F = 7 and N = 8? we don't get lgN broken eggs.

In the 2lgF part I don't understand how we get 2lgF broken eggs either, sounds like you just do 2lgF steps but your amount of broken eggs is 1. – Pavel – 2015-04-30T09:53:34.540

Ohh, okay, sorry, I thought that the point of the exercise was to achieve the given number of broken eggs, but it's actually to find F, thanks. I get really confused with these exercises, most of the time I don't understand what they ask. – Pavel – 2015-04-30T09:58:13.467

4

The lg(F) solution is to do 1, 2, 4, 8, ... until the first egg breaks at 2^(k+1), then do a binary search in the range 2^K to 2^(k+1).

Another alternative is to carry out the same process until the first egg breaks at 2^(k+1) then start over except adding 2^k to each height: 2^k + 1, 2^k + 2, 2^k + 4, 2^k + 8, .... You can keep repeating this process to keep reducing the size of the range you do exponential search in.

Timothy Shields

Posted 2013-07-01T12:36:15.557

Reputation: 47 592