2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – pepster Sep 22 '18 at 20:32
  • $\begingroup$ @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. $\endgroup$ – Jens Sep 22 '18 at 21:05
  • $\begingroup$ @pepster can you explain your algorithm for worst case minimum of 9 guesses? $\endgroup$ – john Sep 22 '18 at 21:20
  • $\begingroup$ 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. $\endgroup$ – pepster Sep 22 '18 at 22:45
  • 2
    $\begingroup$ 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. $\endgroup$ – pepster Sep 23 '18 at 11:08
1
$\begingroup$

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()
$\endgroup$

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.