# Guess 4 digit number where each digit has a range from [ 1, 6 ] with oracle

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

5 guesses

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?

• The theoretical minimum is 5 guesses, and the maximum is 9 from some code I run. I don't know how one would go about proving what is the minimum. – pepster Sep 22 '18 at 20:32
• @pepster What do you mean the theoretical minimum is 5 guesses? The "theoretical" minimum is 1 guess, but we are looking for the worst-case minimum. – Jens Sep 22 '18 at 21:05
• @pepster can you explain your algorithm for worst case minimum of 9 guesses? – john Sep 22 '18 at 21:20
• There is no "algorithm" but a "search tree" of depth 9. There are probably many such trees and are not hard to find scholastically. Posting the tree is a little cumbersome, still thinking about it. – pepster Sep 22 '18 at 22:45
• This is because I printed only the internal nodes. Here is the tree with the "leaves" in green (filedn.com/llztAlmJ0zvkPa8QEheU5n5/p8.png). Also, good news, I run the code a little longer and got a tree of depth 8, which is the tree printed above. – pepster Sep 23 '18 at 11:08

## 1 Answer

Here are the (python 2.7) code for stochastically searching for the search tree.

For the record: this is really terrible code and I am ashamed to be associated with it.

import itertools, random

def nbull(numb, gus) :
return sum([x==y for x,y in zip(numb, gus)])

def part(grp, guess) :
sp = [list() for _ in range(len(guess)+1)]
for z in grp:
sp[nbull(z,guess)].append(z)
return sp

class Part(object) :
def __init__(self, numbs) :
self.numbs = numbs
self.guess = None
self.parts = None

def partition(self, guess) :
assert len(self.numbs) > 1
self.guess = guess
grps = part(self.numbs, self.guess)
self.parts = [Part(x) for x in grps]

def rpartition(self, recurse=False, anyGuess=False) :
if len(self.numbs) > 1:
if anyGuess :
g = [random.randint(1, 6) for _ in range(4)]
else :
g = random.sample(self.numbs, 1)
self.partition(g)
if recurse:
for p in self.parts:
p.rpartition(recurse, anyGuess)

def depth(self) :
if len(self.numbs) > 1:
return max([p.depth() for p in self.parts]) + 1
return 0

def refine(self, anyGuess=False) :
if len(self.numbs) > 1:
d = self.depth()
save = self.guess, self.parts
self.rpartition(True, anyGuess)
dn = self.depth()
if dn > d :
self.guess, self.parts = save
return dn < d

return False

def rrefine(self, anyGuess=False) :
if len(self.numbs) > 1:
anyr = False
d = self.depth()
for p in self.parts:
p.rrefine(anyGuess)
if self.depth() < d :
anyr = True
r = self.refine(anyGuess)
return r or anyr
return False

if 1:
best = None
nt = 0
alln = list(itertools.product(range(1,7), repeat=4))
while nt < 10:
nt += 1
p0 = Part(list(alln)) ; p0.rpartition(1,anyGuess=1)
for _ in range(20) :
a = p0.rrefine(1); print   a,p0.depth()
for _ in range(20) :
a = p0.rrefine(0); print   a,p0.depth()
if not best or p0.depth() <= best.depth() :
best = p0
print "--",nt,p0.depth(),best.depth()