A survey boat measures the depth of a lake nobody has charted. The depth D is a whole number of
metres, at least 1, and there is no known maximum: it could be 3 or a (very fictional)
10**18. A weighted line can be lowered to any whole length k >= 1, and touches_bottom(k)
reports True if a line of k metres reaches the bottom (that is, D <= k).
Write find_depth(touches_bottom) that returns D. Deep lakes may take more soundings than
shallow ones, but you may use at most 2 * ⌈log2 D⌉ soundings (1 sounding when D == 1). One
sounding too many raises TooManySoundings.
The tests run with_line(find_depth, low, high, seed), which picks a depth between low and
high, hides it and counts your soundings. Try it with Run:
print(with_line(find_depth, 1, 1000, 1)).
Examples
Input: with_line(find_depth, 5, 5, 1) (D = 5: at most 2 * 3 = 6 soundings)
Output: {"answer": 5, "soundings": ..., "limit": 6, "depth": 5}
Input: with_line(find_depth, 1, 1, 2) (D = 1: a single sounding)
Output: {"answer": 1, "soundings": 1, "limit": 1, "depth": 1}
Constraints
1 <= D <= 10**18; your function is not told any bound- at most
max(1, 2 * ⌈log2 D⌉)soundings touches_bottom(k)raisesValueErrorunlesskis an integer>= 1
Goals
- Search for a number when no upper bound is known
- Keep the question count proportional to the size of the answer, not to a guessed maximum