Solving the nice puzzle below, I found it easier to define a stream coinductively than to define a function from natural numbers inductively.
You’re standing in front of a 100 story building with two identical bowling balls. You’ve been tasked with testing the bowling balls’ resilience. The building has a stairwell with a window at each story from which you can (conveniently) drop bowling balls.
To test the bowling balls you need to find the first floor at which they break. It might be the 100th floor or it might be the 50th floor, but if it breaks somewhere in the middle you know it will break at every floor above.
Devise an algorithm which guarantees you’ll find the first floor at which one of your bowling balls will break. You’re graded on your algorithm’s worst-case running time.
“Running time” here means the number of times we drop a ball.
Before testing begins, all we know is that the answer is somewhere between the bottom of the building and the top. There are 101 possibilities in all, because maybe the balls are so strong that even dropping them from the 100th floor doesn’t break them, or maybe the balls are so weak that even dropping them from the first floor breaks them. At any time during testing, the set of possible answers remaining a contiguous set of floors: the lower bound is established by a drop that did not break the ball, and the upper bound by a drop that did break the ball.
Let c(n) denote the minimum worst−case running time, starting with 2 balls and n possible answers (so we want to calculate c(101)). We can stop once we know the answer, so c(1) = 0. If n > 1, suppose that we next drop a ball from the i-th possible floor from the top. (It only makes sense for i to be between 2 and n, inclusive, because if i < 2 then we already know the ball would break, and if i > n then we already know the ball would not break.) If the ball doesn’t break, then we have narrowed the answer down to i − 1 possibilities, so we have only c(i − 1) drops to go. If the ball does break, then we have narrowed the answer down to n − i + 1 possibilities, but we have only 1 ball left, so we’d better be careful and test the remaining floors from bottom to top, which takes n − i drops. To sum up, we have
c(1) = 0
c(n) = 1 + min2≤i≤n max { c(i − 1), n − i } if n > 1.
A nice way to calculate c(101) in Haskell is to define
a stream of numbers count, such that
count!!n-1 is
c(n).
count :: [Int] count = 0 : [ 1 + minimum (zipWith max counts [0..]) | counts <- inits' count ]
Look ma, no indices! The list [0..] above
enumerates all possible values of
n − i. This definition uses an
auxiliary function inits', which is equivalent to
map reverse .
tail . inits but
produces a result with more sharing.
inits' :: [a] -> [ [a] ] inits' = f [] where f accum [] = [] f accum (x:xs) = accum' : f accum' xs where accum' = x:accum
(The first clause defining f is not really
necessary for our purpose, because the list count
never ends.)
Let’s try it out.
*Main> take 101 count [0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10,10,10,10,10,10,10,10,10,10, 11,11,11,11,11,11,11,11,11,11,11, 12,12,12,12,12,12,12,12,12,12,12,12, 13,13,13,13,13,13,13,13,13,13,13,13,13, 14,14,14,14,14,14,14,14,14]
So the best we can do is
indeed 14 drops. What about general n? Note that
1 appears once, 2 appears twice,
3 appears thrice, and so on in the list above. It’s
not hard to see (and to prove by induction on n) that
the pattern continues, so c(n) is the least such
that 1 + … + c(n) ≥
n − 1.
*Main> and $ take 10000 $ zipWith (==) count $ [ ceiling ((-1 + sqrt (8 * n - 7)) / 2) | n <- [1..] ] True
Thus, indeed
c(n) = ⌈(−1 + √(8n−7))/2⌉.