Author |
Topic: Egg Dropping (Read 33392 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 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 |
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 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
wu::riddles Administrator
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 |
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 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 |
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 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 |
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 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 |
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 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 |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print