• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Breaking objects (logic puzzle, no OOP)

 
Ranch Hand
Posts: 135
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Suppose you have two identical, solid objects. They will break if dropped from a great height, but you don't know exactly how far you have to lift them. There's a 50-storey building you can be sure is tall enough, so if you drop them from the 50th floor, they will break.

You want to learn which is the lowest numbered floor that is high enough for the objects to break if dropped from that floor.

What is the minimal number of experiments needed to find that floor (in the worst case)? You have 2 objects, each of them can only be used until it breaks :-)
 
Ranch Hand
Posts: 106
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
use binary search.

maybe it will take 2-3 iterations.
 
Istvan Kovacs
Ranch Hand
Posts: 135
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rohan kanade wrote:use binary search.
maybe it will take 2-3 iterations.



You cannot use binary search.
Suppose you start at the middle, floor #25. You drop one of the objects. It breaks.
Now you go to floor 12 or 13. You drop the other object. It breaks.
What now?
 
Rohan kanade
Ranch Hand
Posts: 106
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
so what is the solution?
 
Istvan Kovacs
Ranch Hand
Posts: 135
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rohan kanade wrote:so what is the solution?



Don't want to spoil the fun for the others. I'll sent it in PM.
 
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Seems a little early to give up, isn't it?

I have a solution requiring 10 drops. I believe this is optimal for the problem as stated. But I'll give others a chance before I reveal more details.
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:Seems a little early to give up, isn't it?

I have a solution requiring 10 drops. I believe this is optimal for the problem as stated. But I'll give others a chance before I reveal more details.



I agree with an answer of 10.

I came up with the start of the pattern that you probably figured out, Mike. I started with a guess of 15 tests and figured out the pattern for that. "If I have to make a decision in 15 test, I can start at floor Q. If my first thingy breaks, I test floors R-S. If it doesn't break, I go up to floor T, etc." Once I saw the pattern of floors (Q, T, etc.) for 15, the correct answer of 10 was easy to determine.

Of course, there might be a strategy that I didn't see that yields a smaller minimum. ...but I doubt it.

Follow-up question: What if you had 3 identical breakable objects and an 80-story building? How about N breakables and an M-story building? Even if you can't write the complete formula, how would you go about solving it?
 
Mike Simmons
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hey - someone snuck a new question in after I read their last post. No fair!

Fortunately, it was essentially the same question I was thinking about...

Ryan McGuire wrote:Follow-up question: What if you had 3 identical breakable objects and an 80-story building?


8 drops. Or if you had 4 identical breakable objects, then 7 drops. Unfortunately, after this you no longer can reduce the number of drops by increasing the number of objects. You need 7 drops for any number of objects greater than 3, to solve an 80-story building.

Ryan McGuire wrote:How about N breakables and an M-story building? Even if you can't write the complete formula, how would you go about solving it?


Well, I don't have a single analytic formula for that (yet), but I do have a fairly simple algorithm for making a table to solve it. I have a feeling further simplification is possible though, so I'll post more later.
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:Hey - someone snuck a new question in after I read their last post. No fair!

Fortunately, it was essentially the same question I was thinking about...

Ryan McGuire wrote:Follow-up question: What if you had 3 identical breakable objects and an 80-story building?


8 drops. Or if you had 4 identical breakable objects, then 7 drops. Unfortunately, after this you no longer can reduce the number of drops by increasing the number of objects. You need 7 drops for any number of objects greater than 3, to solve an 80-story building.

Ryan McGuire wrote:How about N breakables and an M-story building? Even if you can't write the complete formula, how would you go about solving it?


Well, I don't have a single analytic formula for that (yet), but I do have a fairly simple algorithm for making a table to solve it. I have a feeling further simplification is possible though, so I'll post more later.



If not a closed form formula, how about a recursive formula?



Since the original problem, is to find T given B and S(), you could say the answer is...



Granted, plugging various values of T into the recursive formula for S() to find the smallest T is more of an algorithm than a formula. Nonetheless, it does give you a way to find the answer regardless of inputs. It might take a while, but it will conclude.

Or....
You could pre-calculate a table of values for S() for various values of T and B:
- Fill in row T=0 with 0
- Fill in column B=1 with T
- For all the other tables cells, fill in a value that is the sum the cell value immediately above (S(B, T-1)), the cell value above and to the left (S(B-1,T-1)) and 1.

That sounds a lot like Pascal's Triangle, doesn't it? I'll leave the derivation of the closed form as an exercise for the interested reader.



In the breakable items B=2 column, a 50-story building falls between the rows for T=9 and T=10. Nine tests isn't enough, ten tests is.

What about the other case I posed: S() = 80, B=3? In column B=3, S()=80 between rows T=7 and T=8. The answer, as Mike calculated, is 8. Beautiful.
 
Mike Simmons
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yep - generating that table was what I meant by having a fairly simple algorithm to make a table to solve it. And I saw how it is tantalizingly similar to Pascal's triangle, but diverges. Which is why I thought there may well be more to it, and perhaps a simpler form. But I haven't done anything else with the problem since that post.
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ryan McGuire wrote:



Just in case anyone uses this problem / solution later...
There are some incorrect values in the table I generated. The repeating value near the end of row T=6 should be 63. All the values that derive from those values will be incorrect as well. At least the formula is correct.

I'll leave it as an exercise for the interested reader to fill in the correct values. Knowing that you have a problem is the first step to recovery.

 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic