Thank you for an interesting math problem in your article on Bowling for Perl (Issue 110, January 2010). However, the mathematician in me smelt a sub-optimal algorithm for dropping the bowling balls!
If the person's strategy were instead to always first try dropping at the end of an interval (i.e., on first round, the 14th floor), then the worst case scenario is that they will make 14 tries to find the highest OK floor, and not 15, as solved by the Perl script. It effectively removes the need to always drop the first ball at floor 1 on your first go, which is a wasted move.
For example, if the highest level is anywhere in floors 1-14, the worst case floors are 12 and 13, the sequence being [14, 1, 2, ... 13], which is 14 tries with 2 breaks for floor 12, and only 1 break for floor 13. Similarly for interval 2, the worst case floors are 25 and 26, the sequence being [14, 27, 15, ... 26], again 14 tries.
There are always two "worst case" floors in an interval, one of which requires only one broken ball to find, and the other requires that you break both.
This extends all the way across the intervals in the same way as described in the article, because to try all the floors in an interval of length (n - i), you make i moves to get into that interval, and thus the maximum number of tries is (n - i + i), where n is the quadratic solution, as previously described in the article.
I wrote a Groovy class to test the outcomes instead of Perl. I'm a Java developer and wanted to find an excuse to learn Groovy, so thank you!
Mark Fisher
| LM |
We received several letters from readers who saw a better algorithm for the problem posed by the Perlmeister in the January 2010 issue: "Given two identical bowling balls, determine with the minimum number of drops from which floor of a 100-story building could you drop either ball without it breaking."
Thanks for pointing the way to a better solution. (We might add that a more efficient algorithm is also safer for bystanders.) Perlmeister Mike Schilli provides an addendum for his article, including some new Perl code, at his website: http://perlmeister.com/forum/viewtopic.php?t=2294
About six months ago, my son Anthony asked if he could have Tux on his birthday cake. His fourth Birthday was at the end of October, and after the elapsed time, we were surprised he still wanted to have Tux on his cake.
When Anthony was about 30 months old, I set-up an old AMD 2400XP computer with dual-boot Mint Linux and Windows XP for him. He took to Gnome like a duck to water and was able to navigate the menu for his games in a few short days. After a couple of weeks, I found he was selecting either operating system to access his educational games at will on both Linux and Windows.
He says he prefers Linux over Windows, as it doesn't crash at all, except, "Why can't they make The Sims for Linux?"
When we pick up my copy of Linux Magazine each month, Anthony goes through it almost forensically counting up all the Tux images. It's great to keep him occupied while we wait for mum to finish her shopping.
Anyway guys, keep up the great work you all undertake at Linux Magazine, as it's very appreciated!
Ray McNamara
| LM |
We're glad to oblige. It is nice to see a new generation coming around to Linux. Perhaps Anthony will enjoy counting the Tux on his own birthday cake:
