Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

# puzzle

Sameer Jamal
Ranch Hand
Posts: 1870
I am in a 100-story building. I have with me two glass balls. I know that if I throw the ball out of the window it will never brakes if the floor number is less than X and it will always brakes is the floor number is equal or greater than X. Assuming that I can reuse the balls which didn't brake, find X in a minimum number of throws.

Peter Kristensson
Ranch Hand
Posts: 118
I'm would never need more than 19 throws.
2 throws are always needed with my method.
[ July 25, 2002: Message edited by: Peter Kristensson ]

Shura Balaganov
Ranch Hand
Posts: 664
The simplest way is throwing one ball from every third floor, i.e. 3rd, 6th, 9th, etc. That'll give a max of 33 throws. Not very efficient, I guess, but, perhaps, it is the shortest walk...
Shura

Jim Yingst
Wanderer
Sheriff
Posts: 18671
I can do it in 14 drops (or less).

Neil Laurance
Ranch Hand
Posts: 183
Is this just a binary search, where you always throw from the middle floor of your range. 2**7 is 128, so it should take 7 throws?
An example to find the case where the floor = 1:
1 -> 100. Throw from 50. 49 possible left
1 -> 49. Throw from 25. 24 possible left.
1 -> 24. Throw from 13. 12 possible left.
1 -> 12. Throw from 7. 6 possible left.
1 -> 6. Throw from 4. 3 possible left.
1 -> 3. Throw from 2. 1 possible left.
Throw from 1.
Or have I got this totally wrong?

[ July 25, 2002: Message edited by: Neil Laurance ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Neil - what you're missing is that if the ball breaks at some point, you no longer can perform a binary search through the remaining possibilities. If at step 1 you drop from floor 50 and it breaks, the only way you can then test all the remaining floors and guarantee that you will get an answer is if you test each remaining floor one at a time, starting at 1. You've only got one ball left at this point, and once it breaks you can't test anything more. So you've got to test lower floors before upper floors, or risk losing the chance to test any more at all.

Neil Laurance
Ranch Hand
Posts: 183
Aha. A tougher puzzle. I was hoping for an inexhaustible supply of balls

Neil Laurance
Ranch Hand
Posts: 183
14 as well. Based on square roots.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
So, how many drops would be required if there were three glass balls? I get 9.

Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
Jim, does your ball always hit the ground?

Jim Yingst
Wanderer
Sheriff
Posts: 18671
I assumed so. From Sameer's original problem statement, it doesn't really seem to matter, does it? You throw a ball out the window, and it either breaks or doesn't break, depending on how X compares to your current floor. The reason for breakage is unspecified. However "it broke because it was traveling too fast when it hit the ground" seems like a reasonable default assumtion. Why do you ask? (And why is this conversation "hidden"?)

Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
Well, in case it's a part of your solution, I did not want to give a clue if nobody explicitely asked for it.
"From Sameer's original problem statement, it doesn't really seem to matter, does it?" - it depends. We could put an intermediate surface, say, on the third floor with a small slope toward the ground and throw a ball out of 5th. So it goes 2 floors, perhaps breaks, if not, it goes 3 more floors - and again either breaks or not. I can solve the whole problem with only one throw then. Of course, it will be very well prepared throw...
Back to your less-than-optimal solution. On average each your throw defines 7 floors. It is a constant factor, or you somehow reuse information from previous attempts? The former doesn't look feasible, but I would be happy to mistake...
[ July 25, 2002: Message edited by: Mapraputa Is ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Cute. But of course the problem statement does not specify exactly when the balls break. Perhaps the city is testing a new missile defense system which vaporizes unidentified objects falling down on the city starting above a certain altitude. In which case the ball might be destroyed the moment it's thrown outside the building above floor X. Which would make your alleged one-throw solution rather difficult.
Seriously, no such hypercreative distortions of reality are necessary for this problem. At least, not to solve the problem within 14 throws.
On average each your throw defines 7 floors. It is a constant factor,
No.
or you somehow reuse information from previous attempts?
Yes. (What, you think I would ignore perfectly good data from previous efforts? :roll: )
The former doesn't look feasible, but I would be happy to mistake...
See, now we can both be happy.

Sameer Jamal
Ranch Hand
Posts: 1870
Here is the solution
Suppose we have a strategy with N throws. Then the floor is defined by two numbers: the throw, when the first ball brakes, and the throw, when the second ball brakes. The sum of those two numbers should be less or equal to N. Hence the number of floors we can distinguish is the number of different pairs of such numbers, which is equal to N(N+1)/2. This number should be more than 99. Hence, we need at least 14 throws(Jim u got it).
Now we would like to build a strategy. To decide the floor for our first throw we observe that if the ball brakes we need to decide between the leftover floors in 13 steps. Which means to maximize our choices for the case when it doesn't brake we need to use all the opportunities. That is we should throw the ball from the 14th floor first. If it brakes we use the second ball starting from the first floor up.
Second throw should be from the 14 + 13 = 27th floor. And so on.

Neil Laurance
Ranch Hand
Posts: 183
Please stop posting these puzzles. I didn't sleep a wink last night

Varun Khanna
Ranch Hand
Posts: 1400
living in 100 story building and doing all this ???

Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
Hey, Sameer, do not post solution so fast! We lost only one night sleep! (Kidding. I *was* sleeping, but when woke up couldn't go sleep again. ) Couldn't figure how Jim came to his flawed 14-steps solution:
Perhaps the city is testing a new missile defense system which vaporizes unidentified objects falling down on the city starting above a certain altitude. In which case the ball might be destroyed the moment it's thrown outside the building above floor X.
In this case it's one-throw solution also. You just throw the ball up, no down, and watch near which floor it gets vaporizes.
Seriously, it's a good puzzle. It takes to think what is *really* being asked, to abstract from floors and balls falling down. Of course now I am at both Sameer and Jim, and I suspect not only I... Hm...
[ July 26, 2002: Message edited by: Mapraputa Is ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
In this case it's one-throw solution also. You just throw the ball up, no down, and watch near which floor it gets vaporizes.
Note that the way I phrased it, the missile defense system only targets unidentified objects falling down on the city. So your one-throw solution won't work, as the ball can pass all floors on the way up, only to be vaporized when it reverses direction.
If you're disappointed that Sameer posted his solution too quickly, you can always try answering the followup question I posed: how many drops would be required if there were three glass balls, rather than two?

Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
Note that the way I phrased it, the missile defense system only targets unidentified objects falling down on the city. So your one-throw solution won't work, as the ball can pass all floors on the way up, only to be vaporized when it reverses direction.
Well, you did not leave me any chance but to resort to methodical balls throwing...
If you're disappointed that Sameer posted his solution too quickly, you can always try answering the followup question I posed: how many drops would be required if there were three glass balls, rather than two?
The most difficult part was to abandon monotonically creeping solutions as it wouldn't move us anywhere besides 3 floors per throw. A jump from 2 glass balls to 3 glass balls isn't as mentally radical, or so I believe... Pick any floor, and if the glass ball is broken we have the previous problem with floor number substituted for 100...

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Well, if you have a working solution for 8 drops then that's better than my solution. (See inviso-text at the end of my original 3-ball question above.) But I'm skeptical that such a solution really exists.
[ July 29, 2002: Message edited by: Jim Yingst ]

Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
Like if I care what the right answer + 1 is! :roll:
By the way, where this crazy n(n+1)/2 formula came from?
Doing reverse engineering, there are a lot of possible combinations, like checking every 5th floor with the first ball (20 times in worst case) and then in case of positive result checking 3 more... As I understand, the trick is to keep the sum of actual (already made) and potential (possible needed) throws constant. Since actual attempts are incremented on each step, potential should be decremented - number of floors should be reduced by 1 on every next step. So if the floor where we started is n, then it would be
n + (n-1) + (n-2) + ... + 2 + 1 >= 100
And sum of this series is n(n+1)/2 from where Yingst got his 14 (unless he simply went to the nearest skyscraper with a bunch of glass balls...)
Now if we want to apply the same technique to the 3 balls case (this part is "invisible" for this unlikely occasion someone is still throwing balls...)

We want to decrement number of floors on each attempts also, but now when we have two balls left, we do not have to test each floor, we can reuse the formula from previous case. Instead of 1, 2, 3 ... we use its result on 1, 2, 3 etc. summing up until we get more than 100:
1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 = 120
So we first go to the 36th floor, where in the worst case we will have to make 8 throws (and Jim thoughtfully added one already made attempt - which, of course, only proves that he is arrogant, ignorant and didn't read all/his own posts in this thread ) , then if it doesn't work, we go to the 36+28=64th floor etc.

I am waiting in full trepidation for James Yingst's denunciation of this algorithm... :roll:
[ July 30, 2002: Message edited by: Mapraputa Is ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
So, your first drop is from the 36th floor, right? Let's say it breaks. You now have 2 balls and 7 drops left. How do you proceed?

Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
I would go on the 8th floor, then on the 15th etc. and if I run out of attempts, I'll borrow one from you
Um, now I re-read my post and it looks like I disagree with your final "9" verdict. This is untrue, I wrote all my philippics assuming you are right, otherwise I wouldn't write them. Sorry for confusion (if there is such).
Is 36th floor Ok now or you are going to drive me crazy some more?
[ July 30, 2002: Message edited by: Mapraputa Is ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Is 36th floor Ok now or you are going to drive me crazy some more?
Yes.
I'm not entirely convinced you're calculating this correctly, so: what's the largest number of floors a building could have such that the problem can be solved with 3 balls and 8 drops? And what if you get 9 drops?
See what happens when you complain you didn't get enough time to work on a problem - you just get assigned more problems.

Sameer Jamal
Ranch Hand
Posts: 1870
Originally posted by Jim Yingst:
[ July 29, 2002: Message edited by: Jim Yingst ]

General problem:
Suppose you have N different objects, one of them is special. By performing some operation you need to find a special object in a minimum amount of steps.
General solution:
Count the maximum amount of different outcomes of your operation in K steps. Denote this amount by f(K). It is clear that to distinguish all objects you need to have the number of steps such that f(K) ≥ N. Your strategy should be the following: make the first step in such a way that it divides all the objects into groups depending on outcome and each group requires the smallest amount of steps.