Dropping eggs - puzzle solving with Haskell
The Problem
You have e eggs and an f-storey building.
You want how high you have to drop an egg from for it to break.
We shall assume that these eggs are rather more robust than normal chickens' eggs.
If an egg breaks when dropped from floor f, it will always break when dropped from floors >= f.
Once you've broken an egg, you cannot use it for further tests. You can however reuse unbroken eggs.
It may be that the eggs do not break for any floor of your building.
Find a strategy for egg-dropping that minimize the worst-case number of tests.
Haskell to the rescue
Haskell is good for calculating the best worst-case number of tests, though it won't prove any theorems for you!
f :: (Integer, Integer) -> Integer f = minimum . opts opts :: (Integer, Integer) -> [Integer] -- Assuming we don't know if it would break at the top opts (1 , floors) = [ floors ] opts (eggs, 0) = [ 0 ] opts (eggs, floors) = [ 1 + max (f (eggs - 1, i - 1)) (f (eggs, floors - i)) | i <- [1..floors] ]
Improving the program
Dynamic programming will help, as will a binary search (not quite the usual one) for the minimum...
Proving a solution for all f, e
TO DO
Copyright (C) 2006-8 Ryan Lothian. All rights reserved.