Enigmatic Code

Programming Enigma Puzzles

Enigma 389: Missing, presumed …?

From New Scientist #1537, 11th December 1986 [link]

In the following division sum, some of the digits are missing and some are replaced by letters. The same letter stands for the same digit wherever it appears. The digits in the answer are all different.

Find the correct sum.

[enigma389]

Advertisements

5 responses to “Enigma 389: Missing, presumed …?

  1. Jim Randell 24 March 2017 at 7:23 am

    We can use the SubstitutedDivision() solver from the enigma.py library to solve this in 436ms.

    from enigma import SubstitutedDivision, is_duplicate
    
    SubstitutedDivision(
      'd??k??', '??', '????',
      [('d??', 'k??', '?'), ('?k', '?r', '?r'), ('?r?', 't??', 'd'), ('d?', '??', '')]
    ).go(lambda s: not is_duplicate(s.c))
    

    However, we can get a faster solution (although with more typing) by using the SubstitutedExpression() solver.

    This run file translates the lower case letters in the original sum to upper case and adds additional upper case letters for the dashes. The complete run time is 147ms.

    #!/usr/bin/env python -m enigma -r
    
    #           H I J L
    #     -------------
    # F G ) D A B K C E
    #       K M N
    #       -----
    #           P K
    #           Q R
    #           ---
    #           S R C
    #           T U V
    #           -----
    #               D E
    #               D E
    #               ===
    
    SubstitutedExpression
    
    --distinct="DKRT"
    
    # the division sum
    "HIJL * FG = DABKCE"
    
    # the multiples
    "H * FG = KMN"
    "I * FG = QR"
    "J * FG = TUV"
    "L * FG = DE"
    
    # the intermediate subtraction sums
    "DAB - KMN = P"
    "PK - QR = SR"
    "SRC - TUV = D"
    
    # all digits in the result are different
    "is_pairwise_distinct(H, I, J, L)"
    

    Solution: The correct sum is 305283 ÷ 33 = 9251.

    Even without the additional condition that all the digits in the result are different there is only one solution.

  2. geoffrounce 24 March 2017 at 12:30 pm

    I used lowercase versions of the letters you used in my solution and got the same answer
    ie 9251 X 33 = 305283 in 84 msec.

    The programme was a bit long in MiniZinc, but I wanted to try a division alphametic in MiniZinc

    I used ‘FG’ (lowercase) in the multiplications (as your statement of the puzzle) but noticed you say ‘EF’ in the solver for the divisor? Anyway, I get the same answer.

    % A Solution in MiniZinc
    
    include "globals.mzn";
    
    set of int: Digit = 0..9;
    
    var Digit: a; var Digit: b; var Digit: c; var Digit: d; var Digit: e; var Digit: f;
    var Digit: g; var Digit: h; var Digit: i; var Digit: j; var Digit: k; var Digit: l;
    var Digit: m; var Digit: n; var Digit: o; var Digit: p; var Digit: q; var Digit: r;
    var Digit: s; var Digit: t; var Digit: u; var Digit: v; var Digit: w; var Digit: x; 
    
    % letters in the answer are all different values
    constraint alldifferent([h,i,j,l]);
    
    % Letters given in the puzzle are different values to each other
    constraint d != k /\ d != r /\ d != t;
    constraint k != r /\ k != t /\ r != t;
    
    constraint h > 0 /\ f > 0 /\ d > 0 /\ k > 0 /\ p > 0 /\ q > 0
     /\ s > 0 /\ t > 0 /\ w > 0;
    
    % 2 digit variables
    var 10..99: fg = 10*f + g;
    var 10..99: pk = 10*p + k;
    var 10..99: qr = 10*q + r;
    var 10..99: de = 10*d + e;
    var 10..99: wx = 10*w + x;
    var 10..99: sr = 10*s + r;
    
    % 3 digit variables
    var 100..999: kmn = 100*k + 10*m + n;
    var 100..999: src = 100*s + 10*r + c;
    var 100..999: tuv = 100*t + 10*u + v;
    var 100..999: dab = 100*d + 10*a + b;
    
    % other variables
    var 1000..9999: hijl = 1000*h + 100*i + 10*j + l;
    var 100000..999999: dabkce = 100000*d + 10000*a 
    + 1000*b + 100*k + 10*c + e;
    
    % multiplication constraints
    constraint hijl * fg == dabkce;
    constraint h * fg == kmn;
    constraint i * fg == qr;
    constraint j * fg == tuv;
    constraint l * fg == wx;
    
    % subtraction constraints
    constraint dab - kmn == p;
    constraint pk - qr == sr;
    constraint src - tuv == d;
    constraint de - wx == 0;
    
    solve satisfy;
    
    output [ show (hijl) ++ " X " ++ show(fg) ++ " = " ++ show(dabkce) ];
    
    % 9251 X 33 = 305283
    % Finished in 84msec
    
    
    
    • Jim Randell 24 March 2017 at 1:01 pm

      @geoff: Thanks for pointing out the EF / FG mix-up. I renamed some of the symbols I used before posting my code, but I must have missed changing them in the multiples. Fortunately it turns out that E, F and G all stand for 3, so it didn’t affect the result of the program, but I’ve sorted it out now.

      I’d been considering writing code to automatically turn these problems into expressions that can be fed directly into the SubstitutedExpression() solver without manual intervention. So maybe it’s time to look at that again.

  3. Jim Randell 30 March 2017 at 11:49 am

    This puzzle has led me to make the “distinct” parameter for the SubstitutedExpression() solver more flexible.

    This means we can now specify multiple sets of symbols, and the values of the symbols in each set have to be distinct from the values of the other symbols in that set, but may be the same as the value of symbols in different sets.

    This removes the need for the "is_pairwise_distinct(H, I, J, L)" expression (line 38) in my solution using the SubstitutedExpression() solver. Instead we can just specify the “distinct” parameter as --distinct="DKRT,HIJL" at line 20. The rest of the file remains the same.

    #!/usr/bin/env python -m enigma -r
    
    #           H I J L
    #     -------------
    # F G ) D A B K C E
    #       K M N
    #       -----
    #           P K
    #           Q R
    #           ---
    #           S R C
    #           T U V
    #           -----
    #               D E
    #               D E
    #               ===
    
    SubstitutedExpression
    
    # digits DKRT, and the result HIJL are (separately) distinct
    --distinct="DKRT,HIJL"
    
    # the division sum
    "HIJL * FG = DABKCE"
    
    # the multiples
    "H * FG = KMN"
    "I * FG = QR"
    "J * FG = TUV"
    "L * FG = DE"
    
    # the intermediate subtraction sums
    "DAB - KMN = P"
    "PK - QR = SR"
    "SRC - TUV = D"
    

    This functionality is available in enigma.py from version 2017-03-24.

  4. Jim Randell 19 July 2017 at 3:03 pm

    The new implementation of the SubstitutedDivision() solver in the enigma.py library is derived from SubstitutedExpression() so we can use the same technique to require the digits of the result to be distinct, but we don’t need to specify symbols for the rest of the sum.

    Here’s a run-file that uses the new SubstitutedDivision() solver. It executes in 179ms.

    #!/usr/bin/env python -m enigma -r
    
    SubstitutedDivision
    
    --distinct="dkrt,ABCD"
    
    "d??k?? / ?? = ABCD"
    
    "d?? - k?? = ?"
    "?k - ?r = ?r"
    "?r? - t?? = d"
    "d? - ?? = 0"
    

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: