Enigmatic Code

Programming Enigma Puzzles

Enigma 52: Think of a number

From New Scientist #1195, 21st February 1980 [link]

The little Buggins were given a games-playing robot for Christmas and are fascinated still. Among its games is a fearsome version of the old Victorian pastime now marketed as Mastermind. The robot thinks of a number and you try and deduce what it is by proposing a series of numbers with the right number of digits. After each guess the robot shows one flashing light (F) for each correct digit correctly placed and one steady light (S) for each correct digit wrongly placed. Thus, if it chose 98766 and you guessed 66765, it would show FFS.

The machine can handle any number of digits up to nine but the Buggins kids are only human and are having trouble enough with five-digit numbers. Here, for instance, is a series of five guesses and the robot’s comments:

1 2 3 4 5  FFS
3 1 6 2 0  SSS
7 3 8 9 0  FS
8 9 5 1 4  F
6 0 1 7 1  FSS

What do you reckon the robot’s number is?

Enigma 147 and Enigma 262 are also called “Think of a number”.

[enigma52]

Advertisements

One response to “Enigma 52: Think of a number

  1. Jim Randell 30 January 2013 at 12:05 am

    My original solution was just to try all candidate 5-digit numbers against the guesses to see if they produced the right scores, but this took a couple of seconds. Here’s a recursive solution that uses the “right digit in the right place” information to test a much reduced set of candidate 5-digit numbers. It runs in 43ms.

    from itertools import combinations, product
    from enigma import printf
    
    # possible digits
    ds = '0123456789'
    
    # number of digits in the numbers
    N = 5
    
    # score guess g against number n
    def score(n, g):
      if n == g: return (N, 0)
      # indices where the digits are in the right place
      rs = list(i for i in range(N) if n[i] == g[i])
      # what digits remain?
      (rn, rg) = zip(*((n[i], g[i]) for i in range(N) if i not in rs))
      return (len(rs), sum(min(rn.count(i), rg.count(i)) for i in set(rn)))
    
    # check to see if the result matches the guesses
    def check(ss, gs):
      # turn the sequence of guessed digits into a dict
      d = dict(ss)
      # consider the remaining possibilities
      for p in product(*((d[i] if i in d else ds) for i in range(N))):
        p = ''.join(p)
        # check all the guesses match
        if all(score(p, s) == (r, w) for (s, r, w) in gs):
          print(p)
    
    # consider digits that are in the right place
    def solve(ss, gs, n):
      # are we done?
      if n == len(gs):
        # check the candidate
        check(ss, gs)
        return
      # consider the next guess
      (s, r, w) = gs[n]
      # count how many digits are in the right place
      c = sum(1 for (i, d) in ss if s[i] == d)
      # is there scope for adding more right digits?
      if r > c:
        # what digits remain to be filled out
        for js in combinations(set(range(N)).difference((i for (i, d) in ss)), r - c):
          # try to solve with the select digits filled out
          solve(ss.union((j, s[j]) for j in js), gs, n + 1)
      elif r == c:
        # move onto the next guess
        solve(ss, gs, n + 1)
    
    # guesses, correctly placed, wrongly placed
    gs = (
      ('12345', 2, 1),
      ('31620', 0, 3),
      ('73890', 1, 1),
      ('89514', 1, 0),
      ('60171', 1, 2),
    )
    
    solve(set(), gs, 0)
    

    Solution: The robot’s number is 72311.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: