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

Question

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?

Answer 1

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)[0]
      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()