Author 
Topic: Egg Dropping (Read 29047 times) 

Trevor Squires
Guest

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 2^{nd}, 2003, 7:46pm by Icarus » 
IP Logged 



Gamer555
Newbie
Posts: 19


Re: Egg Drop: any solutions better than this?
« Reply #1 on: Jul 30^{th}, 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 



Czejwin
Guest


Re: Egg Drop: any solutions better than this?
« Reply #2 on: Jul 30^{th}, 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 15^{th}, 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 15^{th}, 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 16^{th}, 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 17^{th}, 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 manyfloor limit, my solution tends towards optimality. One thing that we can say for certain about the manyegg 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 26^{th}, 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]worstcase[i] optimality. From the other posts, I assume it's worstcase. 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 27^{th}, 2002, 8:33am » 
Quote Modify

I think it's good to consider how we transition from the simple solution (drop egg 1 in 10floor increments, then drop egg 2 in 1floor 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 Mstory 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 27^{th}, 2002, 8:36am by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



tim
Junior Member
Posts: 81


Re: Egg Drop: any solutions better than this?
« Reply #9 on: Aug 27^{th}, 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,e1), 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
wu::riddles Administrator
Gender:
Posts: 1291


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

Cool, same formula I got. James Fingas recently sent me an email 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(e1,d1) + 1 + f(e,d1) 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(e1, d1)" 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, d1)" 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 30^{th}, 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 1^{st}, 2002, 5:17pm » 
Quote Modify

The recurrence relation is only a steppingstone. There is a closedform expression: f(e,d) = C(d,e) + 2^e  1, where C(n,k) is the usual combinatorial formula n! / k!(nk)!. 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 1^{st}, 2002, 9:54pm » 
Quote Modify

I'm not sure if you mean 2^{e}1 or 2^{e1} 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 2^{nd}, 2002, 12:39am » 
Quote Modify

f(d,e) = SUM_{i=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 4^{th}, 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 4^{th}, 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) = sum_{i=1 to e}C(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 2^{d} 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 
Doc, I'm addicted to advice! What should I do?



James Fingas
Uberpuzzler
Gender:
Posts: 949


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

KT, Thank you for your indepth 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 
Doc, I'm addicted to advice! What should I do?



AlexH
Full Member
Posts: 156


Re: Egg Drop: any solutions better than this?
« Reply #17 on: Sep 4^{th}, 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(ed^{2}) for the table.

« Last Edit: Sep 4^{th}, 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 5^{th}, 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 polynomialtime. 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 a_{n}d^{n} + a_{n1}d^{n1} + ... + a_{1}d + a_{0} 4) The solution also satisfies f(d) = 2^{d} for d <= n.

« Last Edit: Sep 5^{th}, 2002, 1:31pm by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



AlexH
Full Member
Posts: 156


Re: Egg Drop: any solutions better than this?
« Reply #19 on: Sep 5^{th}, 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 5^{th}, 2002, 1:40pm » 
Quote Modify

AlexH, Right, I see what you're talking about now. I don't necessarily agree with your solutiondoesn'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 
Doc, I'm addicted to advice! What should I do?



AlexH
Full Member
Posts: 156


Re: Egg Drop: any solutions better than this?
« Reply #21 on: Sep 5^{th}, 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)*(di)/(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 18^{th}, 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 19^{th}, 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 19^{th}, 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 
Doc, I'm addicted to advice! What should I do?



