Enigmatic Code
Programming Enigma Puzzles
Enigma 579: The great divide
Posted by on 19 October 2020
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]
Enigmatic Code 
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 [[SubstitutedExpressionsolver).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.
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)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 % === ===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 % ---------- % ==========# 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 433I 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?
@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.