You are on the 0th floor of a infinitely tall building. At any floor, you can walk to the window and drop an egg. Your goal is to figure out the highest floor that the egg can withstand without breaking. However, you have a maximum of 3 eggs to use to figure this out, but you need to minimize the number of tries.
In formal terms:
- You are given a function
bool(n <= X)for an unknown
0 <= X
- You must return the value of
X(without accessing it directly)
f(n)must only return
Falsea maximum of
3times (in a single test case). If it returns
Falsemore than that, then your answer is disqualified.
Your score is the total number of calls you make to
f(n) (in the test cases below)
If you wish, you may forgo passing in a function, and simply "simulate" the above situation. However, your solving algorithm must know nothing of
Your algorithm should not hard code the test cases, or a maximum
X. If I were to regenerate the numbers, or add more, your program should be able to handle them (with a similar score).
If your language doesn't support arbitrary precision integers, then you may use the
long datatype. If your language doesn't support either, then you are out of luck.
The nth test case is generated using the following:
g(n) = max(g(n-1)*random(1,1.5), n+1), g(0) = 0, or approximately
This is a code-challenge, and the person with the lowest score wins!