Suppose I want to guess a binary code, where the quality of my guess is provided by an evaluation function. I imagine a safe, where the user enters a binary code by flipping $N$ switches. After pressing a button, the code is evaluated and the error (for simplicity, let's assume Hamming Distance divided by $N$) displayed, for example using some sort of gauge or display.

Now, I want to guess the code by minimizing the number of tries (button presses). A naive approach would be to simply the first switch, press the button, and see if the gauge changes, and repeat that for every switch, so I would need at most $N$ tries.

Qustion: Is there a faster way?
Bonus question: What if the feedback gauge is noisy or the exact evaluation function is not known?


1 Answer 1


So, I reckon it is either $N$ or $N-1$, depending on what you know about the gauge.

Call the sequence after $n$ operations $x_n$, let it be $N$ bits long. Let the correct sequence be $x'$ and the Hamming distance be $H$.

Lets say the gauge reads out the value of $H(x,x')$. To discover the value of the sequence $x'$ we need at most $N-1$ switches, because the value of $H(x_{N-1},x')$ tells us the value of the remaining switch. This however assumes requires the knowledge of the gauge other than it changes monotonically with the accuracy - if you do not know this then the best you can do is $N$.

You can justify this in terms of the information gain, as long as you switch different switches each time, you get one bit of information from the increase of decrease in $H$, you need $N$ bits to determine the binary sequence. Then, for the case where you know the function and it's minimum, there is an extra bit of information in whether or not it's absolute value is what you would predict (a yes or no question).

Consider the following sequence:

 Target: 0 0 1 0
Current: 0 1 1 1   H=2

Using the algorithm you describe, we do the following

 Target: 0 0 1 0
Current: 1 1 1 1   H=2
Correct: N         H_so_far = 1

 Target: 0 0 1 0
Current: 1 0 1 1   H=1
Correct: N Y       H_so_far = 1

 Target: 0 0 1 0
Current: 1 0 0 1   H=3
Correct: N Y N     H_so_far = 2

Then we can say that for the state of the first $3$ switches the Hamming distance is $2$ (two Ns), but in total the hamming distance is $3$, so the last switch must be incorrect. We have deduced the sequence in $N-1$ presses. This will apply for any other known functions too, but it isn't as simple.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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