Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

You task is to design a search algorithm that will find my secret number, which is between 0 and 2^64. If your test value is too low you can test again in 1 second. If your test value is too high you are not allowed to test again the next 300 seconds.

Every second I will add 1 to or subtract 1 from the number. I will not tell you what I have done, and while it may be random it also might not be random.

How can you find the approximate number fast?

The obvious answer is to use a binary search, but since the penalty is high for guessing too high, I would think it needs some adjustment.

Background

I need to find the speed of a system. The speed changes slowly. It takes 1 second to do a guess. If my guess is too low: no problem. If it is too high, then system reboots, causing a 5 minute delay.

My goal is to get a decent estimate of the speed relatively fast.

share|improve this question
    
guess at 1/300 in the possible range –  ratchet freak Apr 10 at 19:56
    
Binary search from the small end. Somewhat related to en.wikipedia.org/wiki/Exponential_backoff Try 1, 2, 4, 8, 16, 32 ... until hit first "too high". Then switch to binary search between the last-known good value. –  rwong Apr 10 at 20:07
    
While algorithms are on-topic, guessing games are not. Please edit your question to make it more clear what you need to understand the algorithm behind solving this puzzle. –  GlenH7 Apr 10 at 20:07

2 Answers 2

I did some empirical simulation of a simplified version of this system. It seems intuitive that one could use a binary search, modified with a weight factor to bias the "midpoint" selection toward lower numbers. Another answer proposed 300 (so choosing a midpoint that is 1/300 of the way from the left to the right), but I wanted to check this.

I wrote a simulation (code here) which runs 1000 trials for each weighting factor between 2 (standard binary search taking the midpoint at 1/2) and 499 (taking the midpoint at 1/499). The results can be seen in this spreadsheet, and the resulting graph looks something like this:

enter image description here

What this appears to show is that a standard binary search does perform badly, as expected. However, the optimal weight factor appears to be something around 70 (so choosing the midpoint for the binary search as 1/70 of the way from the left to the right bound). (I'm not sure why this is true, perhaps a question for https://math.stackexchange.com.)

I did not attempt to model the target "wandering" behaviour in your question. You may modify the simulation to add this feature.

share|improve this answer

I am not a statistician, but it seems to me that guessing 1/300 of the overall range would get you the answer most quickly, a weighted binary search.

So, the first guess is (1/300) * 2^64

The second guess is either

on success (1/300) * (1/300) * 2^64 or

on failure (1/300) + (1/300) * (2^64 - (1/300))

etc.

share|improve this answer
1  
I was curious about this (seemingly sensible) idea, so I ran a simulation. See my answer for some simulation data. –  Greg Hewgill Apr 10 at 20:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.