- 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
all forums

this forum made possible by our volunteer staff, including ...

Marshals:

- Campbell Ritchie
- Liutauras Vilda
- Jeanne Boyarsky
- Devaka Cooray
- Paul Clapham

Sheriffs:

- Tim Cooke
- Knute Snortum
- Bear Bibeault

Saloon Keepers:

- Ron McLeod
- Tim Moores
- Stephan van Hulst
- Piet Souris
- Ganesh Patekar

Bartenders:

- Frits Walraven
- Carey Brown
- Tim Holloway

posted 9 years ago

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 :-)

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 :-)

posted 9 years ago

use binary search.

maybe it will take 2-3 iterations.

maybe it will take 2-3 iterations.

SCJP 1.6 ,SCWCD 5

Istvan Kovacs

Ranch Hand

Posts: 100

posted 9 years ago

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 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

posted 9 years ago

so what is the solution?

SCJP 1.6 ,SCWCD 5

Istvan Kovacs

Ranch Hand

Posts: 100

posted 9 years ago

Don't want to spoil the fun for the others. I'll sent it in PM.

Rohan kanade wrote:so what is the solution?

Don't want to spoil the fun for the others. I'll sent it in PM.

posted 9 years ago

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 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.

posted 9 years ago

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 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

Ranch Foreman

Posts: 3266

19

posted 9 years ago

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...

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.

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.

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

Ranch Hand

Posts: 1167

11

posted 9 years ago

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 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

Ranch Foreman

Posts: 3266

19

posted 9 years ago

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

Ranch Hand

Posts: 1167

11

posted 8 years ago

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.

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.

It is sorta covered in the JavaRanch Style Guide. |

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!