Enigmatic Code

Programming Enigma Puzzles

Tantalizer 487: Number system

From New Scientist #1038, 10th February 1977 [link]

If you look up the phone number of Sir William Watergate in the book, you will not find it. He is ex-directory. But you can work it out from the list of ten numbers below. Each of the ten has exactly one of Sir William’s digits correctly placed. Consider the first number, 14073, for instance. It implies that Sir William is not on 14257, which would mean two digits correctly placed, nor on 40731, which would mean none.

14073
29402
35862
42936
50811
63136
79588
84771
98174
07145

If I just add that Sir William’s true number has five digits, can you discover it?

[tantalizer487]

Advertisements

9 responses to “Tantalizer 487: Number system

  1. Jim Randell 22 March 2017 at 8:32 am

    This brute force program is quite short and runs in 459ms.

    from itertools import product
    from enigma import join, printf
    
    # count the matches
    def match(a, b):
      return sum(x == y for (x, y) in zip(a, b))
    
    ts = [
      '14073', '29402', '35862', '42936', '50811',
      '63136', '79588', '84771', '98174', '07145',
    ]
    
    for s in product('0123456789', repeat=5):
      if all(match(s, t) == 1 for t in ts):
        printf("number = {s}", s=join(s))
    

    Solution: The phone number is 09876.

    We can also use the alphametic solver (SubstitutedExpression()) from the enigma.py library to solve this puzzle.

    This run file executes in 216ms.

    #!/usr/bin/env python -m enigma -r
    
    SubstitutedExpression
    
    --distinct=""
    --answer="concat(A, B, C, D, E)"
    
    "sum([A == 1, B == 4, C == 0, D == 7, E == 3]) = 1"
    "sum([A == 2, B == 9, C == 4, D == 0, E == 2]) = 1"
    "sum([A == 3, B == 5, C == 8, D == 6, E == 2]) = 1"
    "sum([A == 4, B == 2, C == 9, D == 3, E == 6]) = 1"
    "sum([A == 5, B == 0, C == 8, D == 1, E == 1]) = 1"
    "sum([A == 6, B == 3, C == 1, D == 3, E == 6]) = 1"
    "sum([A == 7, B == 9, C == 5, D == 8, E == 8]) = 1"
    "sum([A == 8, B == 4, C == 7, D == 7, E == 1]) = 1"
    "sum([A == 9, B == 8, C == 1, D == 7, E == 4]) = 1"
    "sum([A == 0, B == 7, C == 1, D == 4, E == 5]) = 1"
    

    (The digits are not necessarily distinct, and leading zeros are allowed).

    Expressing a similar set of constraints in MiniZinc allows several of the MiniZinc solvers to find a solution in 65-69ms.

  2. Hugh Casement 22 March 2017 at 9:57 am

    This reminds me of the game marketed as Mastermind.
    Ten incorrect numbers seems a lot, to be able to deduce five digits.
    Could it have been solved with fewer numbers given?

    • Jim Randell 22 March 2017 at 10:07 am

      Certainly I noticed when solving the problem that the final candidate (07145) is not required, as we have already got down to a single unique solution with the first nine candidates. So they are not all required.

      In fact 9 in the minimum number of candidates required. We can do without exactly one of: 35862, 84771, 98174, 07145.

    • Jim Randell 22 March 2017 at 10:47 am

      Enigma 52 is another Mastermind type of puzzle.

  3. Brian Gladman 22 March 2017 at 5:41 pm

    Using profile based timing, this version runs in 90ms on my laptop.

    # convert the ten given numbers to lists of their digits
    nbr_dgts = [[(n // 10 ** j) % 10 for j in range(5)] for n in 
          ( 14073, 29402, 35862, 42936, 50811,
            63136, 79588, 84771, 98174,  7145 )]
    
    # the set of digits that occur in each of the five digit positions
    pos_dgts = [set(x) for x in zip(*nbr_dgts)]
    
    # if two or more digits are missing from in the units, tens, ...  
    # columns in the given numbers we could not determine the unknown 
    # number; so if the number of different digits in a column is less
    # than nine we know that one of the digits must match the number
    pos_dgts = [x if len(x) < 9 else set(range(10)) for x in pos_dgts]
    
    # find sequences of digits that share exactly one common digit 
    # with the ten given numbers
    def solve(nbr_dgts, pos_dgts, dseq=[], col=0):
      # if we have found five digits 
      if col == 5:
        # .. check that exactly one digit matches in each number
        if all(len([1 for x, y in zip(dseq, nbr_dgts[n]) 
                        if x == y]) == 1 for n in range(10)):
          yield dseq
      else:
        # try digits that can occur at this position in the number
        for d in pos_dgts[col]:
          # check that less than two digits match in each number  
          if all(len([1 for x, y in zip(dseq + [d], nbr_dgts[n]) 
                        if x == y]) < 2 for n in range(10)):
            yield from solve(nbr_dgts, pos_dgts, dseq + [d], col + 1)
    
    for seq in solve(nbr_dgts, pos_dgts):
      nbr = ''.join(str(x) for x in reversed(seq))
      print(f"Sir William Watergate's number is {nbr}.")
    
    • Jim Randell 22 March 2017 at 6:08 pm

      @Brian: For comparison purposes the total run time of this program is 201ms in my environment.

      • geoffrounce 28 March 2017 at 9:06 am

        Using the telephone numbers in the order listed as num1 to num10 in the code below,
        it looks as though the correct digit in the correct position is not unique in four of the five digits
        – as identified in the extra comments at the end of my code.

        To complicate things further, the correct digit also appears in two or three incorrect positions in all five digits.

        %-----------A solution in MiniZinc-------------
        include "globals.mzn";
        
        % five digits in each telephone number
        int: n = 5;
        
        % Sir William's telephone number
        array[1..n] of var 0..9: tel;
        
        % the ten telephone numbers
        array[1..n] of var 0..9: num1 = [1,4,0,7,3]; 
        array[1..n] of var 0..9: num2 = [2,9,4,0,2]; 
        array[1..n] of var 0..9: num3 = [3,5,8,6,2]; 
        array[1..n] of var 0..9: num4 = [4,2,9,3,6]; 
        array[1..n] of var 0..9: num5 = [5,0,8,1,1]; 
        array[1..n] of var 0..9: num6 = [6,3,1,3,6]; 
        array[1..n] of var 0..9: num7 = [7,9,5,8,8]; 
        array[1..n] of var 0..9: num8 = [8,4,7,7,1]; 
        array[1..n] of var 0..9: num9 = [9,8,1,7,4]; 
        array[1..n] of var 0..9: num10 = [0,7,1,4,5]; 
        
        % look for a matching digit of Sir William's number in each 
        % of the ten telephone numbers
        constraint sum(i in 1..n)(bool2int(tel[i] == num1[i] )) == 1; 
        constraint sum(i in 1..n)(bool2int(tel[i] == num2[i] )) == 1; 
        constraint sum(i in 1..n)(bool2int(tel[i] == num3[i] )) == 1; 
        constraint sum(i in 1..n)(bool2int(tel[i] == num4[i] )) == 1; 
        constraint sum(i in 1..n)(bool2int(tel[i] == num5[i] )) == 1; 
        constraint sum(i in 1..n)(bool2int(tel[i] == num6[i] )) == 1; 
        constraint sum(i in 1..n)(bool2int(tel[i] == num7[i] )) == 1; 
        constraint sum(i in 1..n)(bool2int(tel[i] == num8[i] )) == 1; 
        constraint sum(i in 1..n)(bool2int(tel[i] == num9[i] )) == 1; 
        constraint sum(i in 1..n)(bool2int(tel[i] == num10[i] )) == 1; 
        
        solve satisfy;
        
        output [ "Sir William's telephone number is " ++ show(tel[1]),
        show(tel[2]), show(tel[3]), show(tel[4]), show(tel[5]) ];
        
        % Sir William's telephone number is 09876
        % Finished in 81msec
        
        % Digit '0' occurs in num10 in the correct position  and also in num1, num2 and num5 
        % Digit '9' occurs in num2 and num 7 in the correct position and also in num4 and num9
        % Digit '8' occurs in num3 and num5 in the correct position and also in num7, num8 and num9
        
        % Digit '7' occurs in num1, num8 and num9 in the correct position
        % Digit '7' occurs in num8 and num10 in incorrect positions
        
        % Digit '6' occurs in num4 and num 6 in the correct position 
        % Dogit '6' occurs in num3 and num6 in incorrect positions
        %
        
        • Brian Gladman 28 March 2017 at 1:36 pm
          include "globals.mzn";
          
          % the number of listed phone numbers
          int: m = 10;
          % the number of digits in each phone number
          int: n =  5;
          
          % the listed phone numbers
          array[1..m, 1..n] of int: nbrs = [| 1,4,0,7,3 | 2,9,4,0,2 | 3,5,8,6,2 | 4,2,9,3,6 | 5,0,8,1,1
                                            | 6,3,1,3,6 | 7,9,5,8,8 | 8,4,7,7,1 | 9,8,1,7,4 | 0,7,1,4,5 |];
          % the unknown phone number
          array[1..n] of var 0..9: nbr;
          
          % look for a exactly one matching digit between the number and those given
          constraint forall (i in 1..m) (exactly(1, [bool2int(nbr[j] == nbrs[i, j]) | j in 1..n], 1));
          
          solve satisfy;
          
          output[ "Phone number: " ++ show(nbr[1]) ++ show(nbr[2]) ++ show(nbr[3]) ++ show(nbr[4]) ++ show(nbr[5]) ];
          
        • Jim Randell 28 March 2017 at 1:47 pm

          Here’s my interpretation of the problem using MiniZinc. I get a 65ms run time using mzn-g12fd -a.

          var 0..9: A;
          var 0..9: B;
          var 0..9: C;
          var 0..9: D;
          var 0..9: E;
          
          constraint sum([A = 1, B = 4, C = 0, D = 7, E = 3]) = 1;
          constraint sum([A = 2, B = 9, C = 4, D = 0, E = 2]) = 1;
          constraint sum([A = 3, B = 5, C = 8, D = 6, E = 2]) = 1;
          constraint sum([A = 4, B = 2, C = 9, D = 3, E = 6]) = 1;
          constraint sum([A = 5, B = 0, C = 8, D = 1, E = 1]) = 1;
          constraint sum([A = 6, B = 3, C = 1, D = 3, E = 6]) = 1;
          constraint sum([A = 7, B = 9, C = 5, D = 8, E = 8]) = 1;
          constraint sum([A = 8, B = 4, C = 7, D = 7, E = 1]) = 1;
          constraint sum([A = 9, B = 8, C = 1, D = 7, E = 4]) = 1;
          constraint sum([A = 0, B = 7, C = 1, D = 4, E = 5]) = 1;
          
          solve satisfy;
          
          output [ show([A, B, C, D, E]) ];
          

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: