I'm trying to guess a 4 digit number where each digit has a range from [1, 6]
Each time I send a guess to the oracle, the oracle tells me how many digits are guessed correctly.
How do you minimize the number of times you would have to ask the oracle?
I came up with 14 times. Is there a better algorithm?
I would first guess the following
1111 2222 3333 4444 5555
I can deduce how many 6's there are from 4 - (Oracle(1111)+ Oracle(2222)+ ....) From this I can deduce how many times each number appears in the 4 digit number.
For the first digit I would have to guess at most another 4 times - the 4 times being one of the numbers from the 5 guesses. If the oracle gives a number higher than previous, then I found that digit. If oracle gives me number that is lower then previous, digit is the previous.
Do this for the second digit, for 3 guesses
Do this for the third digit for 2 guesses.
Since we know all of the other digits, we can deduce the last digit.
So 5 + 4 + 3 +2 = 14 guesses.
Is there a better way of doing this?