Enigmatic Code

Programming Enigma Puzzles

Enigma 579: The great divide

From New Scientist #1732, 1st September 1990 [link]

In the two division sums below, the six-figure dividend is the same but the divisor and the answer have been interchanged (that is, the first is x ÷ y = z and the second is x ÷ z = y). No digit occurs in both the divisor and the answer, and no digit in the dividend is used in either the divisor or the answer.

What is the dividend?

[enigma579]

6 responses to “Enigma 579: The great divide

  1. Jim Randell 19 October 2020 at 9:45 am

    We can express both division sums (and the additional constraints) as alphametic expressions (using additional symbols for the “blanks”), and then use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve them.

    (The [[ SubstitutedDivision ]] solver automates this process for a single division sum, but for multiple sums with extra conditions it is easier just to use the [[ SubstitutedExpression solver).

    The following run file executes in 306ms.

    Run: [ @repl.it ]

    #!/usr/bin/env python -m enigma -r
    
    SubstitutedExpression
    
    --symbols="ABCDEFGHIJKLabcdefghijkmnpqrstuvwxy"
    --distinct=""
    
    # 1st division:
    #
    #           JKL
    #      --------
    #  GHI ) ABCDEF
    #        abcd
    #        ----
    #          efE
    #          ghi
    #          ---
    #           jkF
    #           jkF
    #           ===
    
    "GHI * JKL = ABCDEF"
    
    "GHI * J = abcd"
    "GHI * K = ghi"
    "GHI * L = jkF"
    
    "ABCD - abcd = ef"
    "efE - ghi = jk"
    
    
    # 2nd division:
    #
    #           GHI
    #      --------
    #  JKL ) ABCDEF
    #         mnp
    #        ----
    #         qrsE
    #         tuvw
    #         ----
    #           xyF
    #           xyF
    #           ===
    
    "JKL * G = mnp"
    "JKL * H = tuvw"
    "JKL * I = xyF"
    
    "ABCD - mnp = qrs"
    "qrsE - tuvw = xy"
    
    
    # additional conditions
    --code="disjoint = lambda *xs: not intersect(map(nsplit, xs))"
    
    # no digit occurs in both the divisor and the answer
    "disjoint({GHI}, {JKL})"
    
    # no digit in the dividend occurs in either the divisor or the answer
    "disjoint({ABCDEF}, {GHIJKL})"
    
    # required answer
    --answer="ABCDEF"
    
    # [optional] neaten up output
    --template="(ABCDEF / GHI = JKL) (ABCDEF / JKL = GHI)"
    --solution=""
    

    Solution: The dividend is: 109116.

    The two division sums are: 109116 ÷ 252 = 433, and: 109116 ÷ 433 = 252.

  2. Frits 19 October 2020 at 4:54 pm
    from enigma import divisors, nsplit
    
    # A = 1  
    for i in range(100000, 200000):
      lsti = nsplit(i)
      # check for three digit divisors
      for d1 in [x for x in divisors(i) if x in range(200,1000) 
                                        and i // x in range(200,1000) 
                                        and x < i // x]:
        lstd1 = nsplit(d1)
        d2 = i // d1
        lstd2 = nsplit(d2)
       
        # no digit in the dividend occurs in either the divisor or the answer
        if [1 for x in lsti if x in lstd1 or x in lstd2]: continue
       
        # divisors may not share digits
        if [1 for x in lstd1 if x in lstd2]: continue
       
        # G < 5, J < 5 (JKL * G = mnp)
        if not (lstd1[0] < 5 and lstd2[0] < 5): continue
        
        # K < 4 (GHI * K = ghi and J > K)
        if not (lstd1[1] < 4 or lstd2[1] < 4): continue
        
        # L < 4 (GHI * L = jkF and J > L)
        if not (lstd1[2] < 4 or lstd2[2] < 4): continue
        
        # L < 4, I < 5 (JKL * I = xyF)
        if not (lstd1[2] < 5 and lstd2[2] < 5): continue
        
        # GHI * J > 999 and JKL * G < 1000
        if not ((lstd1[0] * d2 > 999) != (lstd2[0] * d1 > 999)): continue
        
        # GHI * K < 1000 and JKL * H > 999
        if not ((lstd1[1] * d2 > 999) != (lstd2[1] * d1 > 999)): continue
        
        # JKL * I < 1000 and GHI * L < 1000
        if not (lstd1[2] * d2 < 1000 and lstd2[2] * d1 < 1000): continue
        
        # ABCD - xxxx should have length 2 and 3
        rest1 = (i // 100 - lstd1[0] * d2)
        rest2 = (i // 100 - lstd2[0] * d1)
        if not ([len(str(rest1)), len(str(rest2))] in ([2,3], [3,2])): continue
        
        print("dividend =",i, "--", d1, d2)
    
  3. GeoffR 23 October 2020 at 9:31 am

    The first division sum produced 14 possible solutions, which were narrowed by the second division sum to a single solution. A quite verbose solution, but it gets the right answer and I have included the full divisions sums at the end of the solution.

    % A Solution in MiniZinc 
    include "globals.mzn";
    
    % 1st (Left Hand) solution
    % Using Jim's notation
    %            JKL
    %       --------
    %   GHI ) ABCDEF
    %         abcd
    %         ----
    %           efE
    %           ghi
    %          ---
    %            jkF
    %            jkF
    %            ===
    
    var 0..9:A; var 0..9:B; var 0..9:C; var 0..9:D; 
    var 0..9:E; var 0..9:F; var 0..9:G; var 0..9:H;
    var 0..9:I; var 0..9:J; var 0..9:K; var 0..9:L;
    
    % No digit occurs in both the divisor and the answer, and 
    % no digit in the dividend is used in either the divisor or the answer.
    constraint card ({G,H,I} intersect {J,K,L} ) == 0;
    constraint card( {G,H,I} intersect {A,B,C,D,E,F}) == 0;
    constraint card( {J,K,L} intersect {A,B,C,D,E,F}) == 0;
    
    constraint A > 0 /\ G > 0 /\ J > 0;
    
    var 0..9:a; var 0..9:b; var 0..9:c; var 0..9:d;
    var 0..9:e; var 0..9:f; var 0..9:g; var 0..9:h;
    var 0..9:i; var 0..9:j; var 0..9:k;
    
    constraint a > 0 /\ e > 0 /\ G > 0 /\ j > 0;
    
    var 10..99:ef = 10*e + f;
    var 10..99:jk = 10*j + k;
    var 100..999:ghi = 100*g + 10*h + i;
    
    var 100..999:GHI = 100*G + 10*H + I;
    var 100..999:JKL = 100*J + 10*K + L;
    var 1000..9999:ABCD = 1000*A + 100*B + 10*C + D;
    
    var 100000..999999:ABCDEF = 100000*A + 10000*B 
    + 1000*C + 100*D + 10*E + F;
    
    var 1000..9999:abcd = 1000*a + 100*b + 10*c + d;
    var 100..999:efE = 100*e + 10*f + E;
    var 100..999:jkF = 100*j + 10*k + F;
    
    constraint GHI * JKL == ABCDEF;
    
    constraint GHI * J == abcd /\ ABCD - abcd == ef;
    
    constraint GHI * K == ghi /\ efE - ghi == jk;
    
    constraint GHI * L == jkF;
    
    % 2nd (Right hand) solution
    % using Jim's notations
    % 
    %            GHI
    %       --------
    %   JKL ) ABCDEF
    %          mnp
    %         ----
    %          qrsE
    %          tuvw
    %          ----
    %            xyF
    %            xyF
    %            ===
    
    var 0..9:m; var 0..9:n; var 0..9:p; var 0..9:q;
    var 0..9:r; var 0..9:s; var 0..9:t; var 0..9:u;
    var 0..9:v; var 0..9:w; var 0..9:x; var 0..9:y;
    
    constraint m > 0  /\ q > 0 /\ t > 0 /\ x > 0;
    
    var 10..99:mn = 10*m + n;
    var 100..999:mnp = 100*m + 10*n + p;
    var 100..999:qrs = 100*q + 10*r + s;
    var 1000..9999:qrsE = 1000*q + 100*r + 10*s + E;
    var 1000..9999:tuvw = 1000*t + 100*u + 10*v + w;
    var 10..99:xy = 10*x + y;
    var 100..999:xyF = 100*x + 10*y + F;
    
    constraint JKL * G = mnp /\ ABCD - mnp = qrs;
    
    constraint JKL * H = tuvw /\ qrsE - tuvw = xy;
    
    constraint JKL * I = xyF;
    
    solve satisfy;
    
    output ["Dividend is " ++ show(ABCDEF) ++
    "\nDivisors are " ++ show(GHI) ++ " and " ++ show(JKL)];
    
    % Dividend is 109116
    % Divisors are 252 and 433
    % ----------
    % ==========
    
    % Full solutions are:
    
    %          433             252
    %      -------          ------
    %   252)109116      433)109116
    %       1008             866
    %       ----            ----
    %         831            2251 
    %         756            2165
    %         ---            ----
    %          756             866
    %          756             866
    %          ===             ===
    
    
  4. GeoffR 25 October 2020 at 11:56 am

    Re-using some of my earlier code, I found a much shorter solution.

    % A Solution in MiniZinc 
    include "globals.mzn";
    
    var 0..9:A; var 0..9:B; var 0..9:C; var 0..9:D; 
    var 0..9:E; var 0..9:F; var 0..9:G; var 0..9:H;
    var 0..9:I; var 0..9:J; var 0..9:K; var 0..9:L;
    
    constraint A > 0 /\ G > 0 /\ J > 0;
    
    % No digit occurs in both the divisor and the answer, and 
    % no digit in the dividend is used in either the divisor or the answer.
    constraint card ({G,H,I} intersect {J,K,L} ) == 0;
    constraint card( {G,H,I} intersect {A,B,C,D,E,F}) == 0;
    constraint card( {J,K,L} intersect {A,B,C,D,E,F}) == 0;
    
    % Divisors are GHI and JKL, 6-digit number is ABCDEF
    var 100..999: GHI = 100*G + 10*H + I;
    var 100..999: JKL = 100*J + 10*K + L;
    
    var 100000..999999:ABCDEF = 100000*A + 10000*B 
    + 1000*C + 100*D + 10*E + F;
    
    constraint GHI * JKL == ABCDEF;
    
    % First division sum
    constraint J * GHI > 1000 /\ J * GHI <10000;
    constraint K * GHI > 100 /\  K * GHI < 1000;
    constraint L * GHI > 100 /\  L * GHI < 1000;
    
    % Second division sum
    constraint G * JKL > 100 /\ G * JKL < 1000;
    constraint H * JKL  > 1000 /\  H * JKL < 10000;
    constraint I * JKL > 100 /\  I * JKL < 1000;
    
    solve satisfy;
    
    output ["Solution: " ++  show(ABCDEF) ++ " / " 
    ++ show(GHI) ++ " = " ++ show(JKL)  
    ++ "\nor " ++ show(ABCDEF) ++ " / " 
    ++ show(JKL) ++ " = " ++ show(GHI) ]
    
    % Solution: 109116 / 252 = 433
    % or 109116 / 433 = 252
    % ----------
    % ==========
    
    
  5. GeoffR 29 October 2020 at 12:25 pm
    # Two divisors are ghi and jkl
    for ghi in range(100, 1000):
      g, h, i = tuple(int(c) for c in str(ghi))
      for jkl in range(100, 1000):
        j, k, l = tuple(int(c) for c in str(jkl))
        s1, s2 = {g, h, i}, {j, k, l}
        
        # Two divisors have different digits
        if s1.intersection(s2):
          continue
        
        # dividend must be six digits
        dividend = ghi * jkl
        if 100000 < dividend < 1000000:
          a, b, c, d, e, f = tuple(int(c) for c in str(dividend))
          s3 = {a, b, c, d, e, f}
          # Digits in dividend different from two divisors
          if s1.intersection(s3): 
            continue
          if s2.intersection(s3): 
            continue
          
          # digit pattern in division sum for divisor ghi
          if not(1000 < j * ghi < 10000):
            continue
          if not (100 < k * ghi < 1000):
            continue
          if not (100 < l * ghi < 1000):
            continue
          
          # digit pattern in division sum for divisor jkl
          if not(100 < g * jkl < 1000):
            continue
          if not(1000 < h * jkl < 10000):
            continue
          if not(100 < i * jkl < 1000):
            continue
          print(f"Dividend was {dividend} ")
          print(f"Divisors were {ghi} and {jkl}")
    
    # Dividend was 109116 
    # Divisors were 252 and 433
    
    

    I tried the free Wing Personal IDE to format my code to PEP8 – it has a Source/Reformatting option in the Main Menu to format the code to PEP8. The biggest change to my normal practice was putting the ‘continue’ statment on a separate line.

    @Frits:
    In both of my solutions I used a range for checking the six digit dividend from 100,000 to 999,999,
    as this seemed appropriate programmatically. I notice your programme used a range of 100,000 to 200,000. Did you find a reason to use this lower upper bound value?

    • Frits 29 October 2020 at 4:41 pm

      @GeoffR, the reason is mentioned line above (A has to be 1, see 2nd division). I added it to bring the run time under 1 second.

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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: