wu :: forums « wu :: forums - Egg Dropping » Welcome, Guest. Please Login or Register. Dec 2nd, 2021, 5:22pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: SMQ, towr, Eigenray, Grimbal, william wu, ThudnBlunder, Icarus)    Egg Dropping « Previous topic | Next topic »
 Pages: 1 2 3 Reply Notify of replies Send Topic Print
 Author Topic: Egg Dropping  (Read 32384 times)
Trevor Squires
Guest

 Egg Dropping   « on: Jul 25th, 2002, 4:35am » Quote Modify Remove

I have no math or CS background so I have to express this in the only way I know how, sorry.

Code:
 public int answer(int s) {     int c = 0;     for (int t = 0; t < s; t += c++ + 1);     return c; }

I won't say how I use the answer, lest I spoil it for others (or maybe I'm the only one that found this a challenge).

Is there anything better than this, if so how about a hint (rather than complete spoon feeding)?

Trevor
 « Last Edit: Sep 2nd, 2003, 7:46pm by Icarus » IP Logged
Gamer555
Newbie

Posts: 19
 Re: Egg Drop: any solutions better than this?   « Reply #1 on: Jul 30th, 2002, 9:21am » Quote Modify

Is the famous solution the answer?

50: If breaks, do 25, if not do 75. So on, dictomizing the answer each time...
 IP Logged
Cze-jwin
Guest

 Re: Egg Drop: any solutions better than this?   « Reply #2 on: Jul 30th, 2002, 12:13pm » Quote Modify Remove

what if it breaks on 25..u have to find the exact floor or perhaps should i say the limit of the egg...?
 IP Logged
Chronos
Full Member

Gender:
Posts: 288
 Re: Egg Drop: any solutions better than this?   « Reply #3 on: Aug 15th, 2002, 5:18pm » Quote Modify

A simple answer which is close to optimal:  Drop the first egg from 10, 20, 30, etc. until it breaks.  Say it breaks on 40, but not on 30.  Then, drop the second egg from 31, 32, 33, etc.

The reason that this is not completely optimal:

If the first egg does not break on the first few floors, we've simplified the problem.  If, for instance, the first egg survives the fall from 20 feet, then we've still got two test eggs, but only 80 floors to choose from, and we can now increment by 9s instead of by 10s.  Once we get below 64 floors to choose from, we can increment by 8s, etc.
 IP Logged
tim
Junior Member

Posts: 81
 Re: Egg Drop: any solutions better than this?   « Reply #4 on: Aug 15th, 2002, 5:30pm » Quote Modify

Chronos: Yes, very close.

My thought processes when I was solving it:
How many floors can the building have to always succeed with a maximum of 1 drop? 2 drops? N drops?

More general (and a bit nastier) problem: What if you have K eggs?
 IP Logged
Eric Yeh
Senior Riddler

Gender:
Posts: 318
 Re: Egg Drop: any solutions better than this?   « Reply #5 on: Aug 16th, 2002, 5:55am » Quote Modify

Ye -- that was a problem I posted in the generalization.  Also expand to n floors.
 IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Chronos
Full Member

Gender:
Posts: 288
 Re: Egg Drop: any solutions better than this?   « Reply #6 on: Aug 17th, 2002, 11:21am » Quote Modify

OK, my solution for N floors and two eggs:  For the first egg, increment the floor by the square root of the number of floors remaining, rounded up.  For the second, increment by one at a time.

Now, for more eggs:  We should be able to proceed inductively, since once the first egg is broken, the problem is reduced to the one with one less egg.  But I'm not sure how, in general, to increment the first egg for more than two eggs (for that matter, I'm not certain my solution is optimal for two eggs, and it looks like tim has a better one).  I am, at least, reasonably sure that in the many-floor limit, my solution tends towards optimality.

One thing that we can say for certain about the many-egg case, is that given any number of floors, for a sufficient number of eggs our strategy must turn into a straightforward binary search.
 IP Logged
Pietro
Guest

 Re: Egg Drop: any solutions better than this?   « Reply #7 on: Aug 26th, 2002, 2:50pm » Quote Modify Remove

I think an important point that should be cleared up is whether optimality refers to [/i]average[i] or [/i]worst-case[i] optimality. From the other posts, I assume it's worst-case. I'll write some more about this later.
Trevor, it appears to me that your function answer(s) returns the least integer c such that c(c+1)/2 is greater than or equal to s. An analytic way to express this would be:

c = ceiling( -1/2 + sqrt(2s + 1/4) ).

I'm not sure what algorithm you would use to achieve this number of drops, but I'll be thinking about it over dinner!
 IP Logged
James Fingas
Uberpuzzler

Gender:
Posts: 949
 Re: Egg Drop: any solutions better than this?   « Reply #8 on: Aug 27th, 2002, 8:33am » Quote Modify

I think it's good to consider how we transition from the simple solution (drop egg 1 in 10-floor increments, then drop egg 2 in 1-floor increments) to the suggestions that we use the square root of the number of floors.

The reason that the simpler solution is not optimal is that the worst case is 18 drops: if egg 1 breaks on floor 90, then we may need 9 drops of egg 2 to find out the exact floor for egg 2. Therefore, we can speed things up by going up to floor 18 for the first drop of egg 1, then up 17 more floors for the second drop of egg 1, without changing the worst case. You get a pyramid type of answer, where each drop of egg 1 gets closer to the last drop.

This is one problem where you can generate an optimal answer through composition (this will apply to N eggs as well)
Work from a fixed number of drops and a fixed number of eggs to find out how many floors you can test that way, and then you can compose your answer like this:

maxfloors( int eggs, int drops ) {
if (eggs == 1)  // when there's only one egg, the answer is simple
return drops;

if (eggs >= drops ) // when we have enough eggs, we can do a binary search!
return (1 << drops) - 1;

return maxfloors( eggs, drops - 1 ) //the first egg survives
+ 1 // count the floor we drop the first egg from
+ maxfloors( eggs - 1, drops - 1 ); //the first egg breaks
}

To find out how many drops for an M-story building, you
see if you can do it in 1 drop, then 2 drops, etc. But maybe there's a better way to test ... maybe we can make an algorithm that will work out the best sequence of drops to test to find the minimum number of drops ...
 « Last Edit: Aug 27th, 2002, 8:36am by James Fingas » IP Logged

tim
Junior Member

Posts: 81
 Re: Egg Drop: any solutions better than this?   « Reply #9 on: Aug 27th, 2002, 9:24pm » Quote Modify

Let's write that mathematically rather than computationally:

Let N(d, e) = number of floor distinguishable with d drops and e eggs.
N(d,0) = N(0,e) = 0, since we can't check any floors without available eggs and drops.
N(d+1,e) = 1 + N(d,e) + N(d,e-1), as James has posted.

If you dropped the "1 + " from the last line, this recurrence relation should look suspiciously familiar to anyone who has ever done any work with combinations.  And that's all I'm going to say
 IP Logged
william wu

Gender:
Posts: 1291
 Re: Egg Drop: any solutions better than this?   « Reply #10 on: Aug 30th, 2002, 4:20am » Quote Modify

Cool, same formula I got. James Fingas recently sent me an e-mail challenging me with the question of "how tall a building can you test with N eggs and M drops?" He also attached a cool graph I will reproduce here, scaled down:

The tallest building you can test with e eggs and d drops is defined by the recurrence relationship:

f(e,d) = f(e-1,d-1) + 1 + f(e,d-1)

brief intuitive explanation:

When you drop an egg, you figure out a floor -- that is you figure out if your egg can break on that floor. So that's where the "+1" term comes from.

If that egg cracks, you used up an egg and a drop. That explains the "f(e-1, d-1)" term.

If the egg does not crack, you used up a drop, but you still have the same number of eggs. That explains the "f(e, d-1)" term.

The relation is recursive because after using up your first drop and possibly an egg, the number of floors you can solve is 1 + the optimal number of floors you can test with your remaining resources.

Coincidentally, this dynamic programming problem was recently asked at topcoder.com during a tournament.

 « Last Edit: Aug 30th, 2002, 4:21am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
tim
Junior Member

Posts: 81
 Re: Egg Drop: any solutions better than this?   « Reply #11 on: Sep 1st, 2002, 5:17pm » Quote Modify

The recurrence relation is only a stepping-stone.  There is a closed-form expression:
f(e,d) = C(d,e) + 2^e - 1,
where C(n,k) is the usual combinatorial formula n! / k!(n-k)!.
Obviously it applies only for e <= d.
 IP Logged
AlexH
Full Member

Posts: 156
 Re: Egg Drop: any solutions better than this?   « Reply #12 on: Sep 1st, 2002, 9:54pm » Quote Modify

I'm not sure if you mean 2e-1 or 2e-1 in your formula,  but either way I don't think it matches the recurrence relation. Maybe I've made an error so I'll try to look at it more later.
 IP Logged
AlexH
Full Member

Posts: 156
 Re: Egg Drop: any solutions better than this?   « Reply #13 on: Sep 2nd, 2002, 12:39am » Quote Modify

f(d,e) = SUMi=1 to e C(d,i)

In other words f(d,e) is the number of binary strings of length d containing between 1 and e 1s. This is one of those "retrospectively obvious" problems. Each possible floor must be uniquely identified by the breaking pattern of the eggs, and the best algorithm wouldn't have two breaking patterns which result in the determination of the same floor.
 IP Logged
KT
Guest

 Re: Egg Drop: any solutions better than this?   « Reply #14 on: Sep 4th, 2002, 12:51am » Quote Modify Remove

I enjoy all the deductive reasoning here, but aren't we missing the point that it takes no egg drops to answer the original question? "How high can the egg fall before it breaks?" The egg can fall forever with out breaking.  It only breaks when it LANDS! If the wording of the question is in error than the egg is on the face.
 IP Logged
James Fingas
Uberpuzzler

Gender:
Posts: 949
 Re: Egg Drop: any solutions better than this?   « Reply #15 on: Sep 4th, 2002, 9:05am » Quote Modify

AlexH,

Cool! That's a good way to think about it!

You're off by one, however:
f(d,e) = sumi=1 to eC(d,i) - 1

That is, unless you count "egg doesn't break" as a floor.

The solutions for a given number of eggs are polynomials in the number of drops. For the first few values of d, they mimic the 2d function, as your formula predicts. For 1 egg, you get a linear function, for 2 eggs you get a quadratic, etc. Your formula also tells us that these polynomials can be used to compute partial sums of the rows of Pascal's triangle. Hmm...
 IP Logged

James Fingas
Uberpuzzler

Gender:
Posts: 949
 Re: Egg Drop: any solutions better than this?   « Reply #16 on: Sep 4th, 2002, 9:36am » Quote Modify

KT,
Thank you for your in-depth analysis of the problem. Your solution is only partly correct. Think of interstellar meteorite eggs which enter the earth's atmosphere and burn up. We must consider these eggs to have "broken".
 IP Logged

AlexH
Full Member

Posts: 156
 Re: Egg Drop: any solutions better than this?   « Reply #17 on: Sep 4th, 2002, 12:17pm » Quote Modify

James: The formula is correct as is. The -1 you refer to is already accounted for in the exclusion of i=0 from the summation. The i=0 case occurs when no eggs break and is not counted as a floor.

If we assume that the arithmetic on these numbers is O(1) then sum of combinations can be computed in O(e) which is faster than the O(ed) table. Since the numbers grow quicky it might be better to look at bitwise complexity, which would make the sum of combinations be in general  O(ed log d) versus O(ed2) for the table.
 « Last Edit: Sep 4th, 2002, 12:17pm by AlexH » IP Logged
James Fingas
Uberpuzzler

Gender:
Posts: 949
 Re: Egg Drop: any solutions better than this?   « Reply #18 on: Sep 5th, 2002, 11:35am » Quote Modify

Alex, (sorry, this said "Eric" -- he's too sneaky too, but not to blame in this particular case)

You're too sneaky for me again!

When I said polynomials, I didn't mean polynomial-time. What I meant was:

1) Fix the number of eggs at n.
2) Now express the number of testable floors as a function of the number of drops, d.
3) The solution you get is of the form  andn + an-1dn-1 + ... + a1d + a0
4) The solution also satisfies f(d) = 2d for d <= n.
 « Last Edit: Sep 5th, 2002, 1:31pm by James Fingas » IP Logged

AlexH
Full Member

Posts: 156
 Re: Egg Drop: any solutions better than this?   « Reply #19 on: Sep 5th, 2002, 1:26pm » Quote Modify

Err, Eric?

For clarification: my second paragraph above wasn't actually in response to your comments about the solutions being polynomials in d for any fixed e (they are), I was just making an observation on computation time of the new formula vs the table method.
 IP Logged
James Fingas
Uberpuzzler

Gender:
Posts: 949
 Re: Egg Drop: any solutions better than this?   « Reply #20 on: Sep 5th, 2002, 1:40pm » Quote Modify

AlexH,

Right, I see what you're talking about now. I don't necessarily agree with your solution--doesn't the C(d,e) function take longer to compute than an addition?

I wonder how long it would take to compute the polynomial for the given number of eggs and evaluate it...
 IP Logged

AlexH
Full Member

Posts: 156
 Re: Egg Drop: any solutions better than this?   « Reply #21 on: Sep 5th, 2002, 3:10pm » Quote Modify

The thing is we're computing the sum over i of C(d,i). If arithmetic operations are constant time then we can use
C(d,i+1)=C(d,i)*(d-i)/(i+1)
to compute each new value in constant time.

If we look at the bitwise complexity then we wind up paying a bit extra per stage for the combinations method (since it requires multiplication/division rather than just addition), but this only amounts to a (log d) factor. We're multiplying and dividing large numbers by small numbers (i.e. O(d) numbers), so no advanced multiplication techniques are involved.  This extra O(log d) factor we pay is much smaller than the O(d) factor we save by only computing entries corresponding to our particular value of d.

 IP Logged
continuum
Newbie

Gender:
Posts: 14
 Re: Egg Drop: any solutions better than this?   « Reply #22 on: Sep 18th, 2002, 7:07pm » Quote Modify

Interesting. Given the number of eggs, "maximize the number of floors" is the dual problem of "minimize the number of drops". Mathematics is really elegant.
 IP Logged
Chronos
Full Member

Gender:
Posts: 288
 Re: Egg Drop: any solutions better than this?   « Reply #23 on: Sep 19th, 2002, 11:48am » Quote Modify

No, not given a number of eggs; given a number of eggs and of drops.  If you have a given number of eggs but unlimited drops, you can still find the floor out of any number of floors:  Just start at the bottom and go up one floor at a time.
 IP Logged
James Fingas
Uberpuzzler

Gender:
Posts: 949
 Re: Egg Drop: any solutions better than this?   « Reply #24 on: Sep 19th, 2002, 11:56am » Quote Modify

Yeah,

Mathematics may be beautiful but it is thorny. You can solve the problem three ways:

1) Given floors and drops, find eggs.
2) Given floors and eggs, find drops (as asked).
3) Given drops and eggs, find floors.

The easiest, #3, is the one we solved. To get from #3 to #2 is not necessarily easy, but we consider it doable at least. Once you have a good solution for #3, you can at least look up the solution for #2, even without finding it explicitly.

That's why we didn't bother to go back and solved #2.
 IP Logged