Enigmatic Code

Programming Enigma Puzzles

BrainTwister #21: Digit gangs

10 Comments Posted by on 25 May 2024

From New Scientist #3492, 25th May 2024 [link] [link]

If we use the digits 0-9 in place of the letters A–J (in some order) in the numbers ABC, DE, FGH and IJ, we can create four numbers to use in calculations. For example, the numbers could be 134, 50, 289 and 67; or 013, 56, 289 and 74.

(a) What is the largest total you can make for ABC + DE + FGH + IJ by assigning the digits?

(b) Can you assign the digits to maximise the value of (ABC × DE) + (FGH × IJ)? What is the largest total you can get?

(c) How can you assign the digits to make the value of (ABC × DE) − (FGH × IJ) as close to zero as possible?

[braintwister21]

braintwister

10 responses to “BrainTwister #21: Digit gangs”

  1. Jim Randell 25 May 2024 at 9:55 am

    We can provide a brute force solution for these puzzles using the [[ SubstitutedExpression ]] solver from the enigma.py library. (Although it is not necessarily very fast – 100ms for part (a), and 3.88s each for parts (b) and (c)).

    Note that the puzzle permits leading zeros (as in the second example).

    For (a) it doesn’t matter what order the digits appear in each column:

    #! python3 -m enigma -r

SubstitutedExpression

# allow leading zeros
--invalid=""

# remove duplicates
"A < F"
"B < D < G < I"
"C < E < H < J"

--answer="ABC + DE + FGH + IJ"
--accumulate="max"
--verbose="A"

    (a) The largest value is 1926:

    840 + 51 + 962 + 73 = 1926

    Not unsurprisingly, 8 and 9 are in the hundreds column. 4, 5, 6, 7 in the tens column. And 0, 1, 2, 3 in the units column.

    #! python3 -m enigma -r

SubstitutedExpression

# allow leading zeros
--invalid=""

# remove duplicates
"A < F"

--answer="(ABC * DE) + (FGH * IJ)"
--accumulate="max"
--verbose="A"

    (b) The largest value is 125354:

    (630 × 72) + (851 × 94) = 125354
    (720 × 63) + (851 × 94) = 125354

    Again, the larger digits tend to be leading digits, and smaller digits towards the end.

    #! python3 -m enigma -r

SubstitutedExpression

# allow leading zeros
--invalid=""

# remove duplicates
"A < F"

--answer="abs((ABC * DE) - (FGH * IJ))"
--accumulate="min"
--verbose="A"

    (c) There are 99 ways we can get a value of 0. One of them is:

    (782 × 53) − (901 × 46) = 0

    Reply
    • Jim Randell 26 May 2024 at 11:18 am

      The following Python program examines all possible letter to digit assignments, and solves all three parts of the puzzle in 215ms (under PyPy 7.3.16).

      from enigma import (Accumulator, irange, subsets, printf)

# accumulators for each question
(a, b, c) = (Accumulator(fn=fn) for fn in [max, max, min])

# construct the 4 numbers (leading zeros allowed)
for (A, B, C, D, E, F, G, H, I, J) in subsets(irange(0, 9), size=len, select='P'):
  ABC = 100*A + 10*B + C
  DE = 10*D + E
  FGH = 100*F + 10*G + H
  IJ = 10*I + J
  # evaluate the expressions
  a.accumulate(ABC + DE + FGH + IJ)
  b.accumulate((ABC * DE) + (FGH * IJ))
  c.accumulate(abs((ABC * DE) - (FGH * IJ)))

# output solutions
printf("(a) {a.value}")
printf("(b) {b.value}")
printf("(c) {c.value}")
      Reply
  2. GeoffR 25 May 2024 at 11:19 am

    To avoid repeating code, as only one solve statement is allowed in MiniZinc, I have had to comment out two of the three solve/output statements to show the third part e.g. as shown, the solution finds Part(b) answer, with Part(a) and Part(c) commented out.

    % 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;

constraint a > 0 /\ d > 0 /\ f > 0 /\ i > 0;

constraint all_different([a,b,c,d,e,f,g,h,i,j]);

var 100..999:abc == 100*a + 10*b + c;

var 10..99:de == 10*d+ e;

var 100..999:fgh == 100*f + 10*g + h;

var 10..99:ij == 10*i + j;

% Part (a)
% solve maximize(abc + de + fgh + ij);
% output ["Max. value for Part(a) = " ++ show(abc + de + fgh + ij)];
% Max. value for Part(a) = 2196

% Part (b)

solve maximize((abc*de) + (fgh * ij));
output ["Max. value for Part(b) = " ++ show( (abc * de) + (fgh * ij))];
% Max. value for Part(b) = 125354
%----------

% Part(c)

% constraint (abc * de) - (fgh * ij) >= 0;
% solve minimize((abc * de) - (fgh * ij));
% output ["Min. value for Part(c) = " ++ show((abc * de) - (fgh * ij) )];

% Min. value for Part(c) = 0
% -------------
    Reply
  3. GeoffR 25 May 2024 at 7:37 pm 
    # Part (a) maximise ABC + DE + FGH + IJ"
from itertools import permutations
digits = set('1234567890')

maxm = 0
for p1 in permutations(digits, 4):
    A,D,F,I = p1
    # make leading digits as large as possible
    # A and F are larger than D and I
    if A not in ('89'):continue
    if F not in ('89'):continue
    if D not in ('67'):continue
    if I not in ('67'):continue
    q1 = digits - {A,D,F,I}
    for p2 in permutations(q1):
       B,C,E,G,H,J = p2
       ABC, DE = int(A+B+C), int(D+E)
       FGH, IJ = int(F+G+H), int(I+J)
       maxm2 = ABC + DE + FGH + IJ
       if maxm2 > maxm:
          maxm = maxm2
          
print('Max value = ',maxm) 



    # Part (b) - maximise (ABC × DE) + (FGH × IJ)
from itertools import permutations
digits = set('1234567890')

maxm = 0
for p1 in permutations(digits,4):
    A,D,F,I = p1
    # make leading digits as large as possible
    if {A+D+F+I} != {'6789'}:continue
    q1 = digits - {A,D,F,I}
    for p2 in permutations(q1):
       B,C,E,G,H,J = p2
       ABC, DE = int(A+B+C), int(D+E)
       FGH, IJ = int(F+G+H), int(I+J)
       maxm2 = (ABC * DE) + (FGH * IJ)
       if maxm2 > maxm:
          maxm = maxm2
print('Max value = ',maxm)     


    # Part (c) - make (ABC × DE) − (FGH × IJ) as close to zero as possible
from itertools import permutations
digits = set('1234567890')

cnt = 0
for p1 in permutations(digits,4):
    A,D,F,I = p1
    q1 = digits - {A,D,F,I}
    for p2 in permutations(q1):
       B,C,E,G,H,J = p2
       ABC, DE = int(A+B+C), int(D+E)
       FGH, IJ = int(F+G+H), int(I+J)
       # check for difference being zero
       if (ABC * DE) - (FGH * IJ) == 0:
           cnt += 1
           # find 3 solutions, if possible
           if cnt < 4:
               print(f"ABC={ABC}, DE={DE}. FGH={FGH}, IJ={IJ}")
               
# Part (a) =1926
# Part (b) = 125354
# Part (c) - Typical 1st three solutions with zero minimum
# ABC=630, DE=27. FGH=945, IJ=18
# ABC=614, DE=29. FGH=307, IJ=58
# ABC=618, DE=27. FGH=309, IJ=54

    I also found 10 solutions for part (c) with a difference of 1, the last one being (703 * 82) – (945 * 61).

    Reply
  4. ruudvanderham 25 May 2024 at 7:53 pm

    Pure brute force solution for all three parts:

    from istr import istr
import itertools

print(max((a | b | c) + (d | e) + (f | g | h) + (i | j) for a, b, c, d, e, f, g, h, i, j in itertools.permutations(istr.digits(), 10)))

print(max(((a | b | c) * (d | e)) + ((f | g | h) * (i | j)) for a, b, c, d, e, f, g, h, i, j in itertools.permutations(istr.digits(), 10)))

print(min(abs(((a | b | c) * (d | e)) - ((f | g | h) * (i | j))) for a, b, c, d, e, f, g, h, i, j in itertools.permutations(istr.digits(), 10)))

    Same solution as shown above.

    Runtimes:
    Dell XPS13 i7: 287 s
    iPhone 14 mini: 240 s
    iPad Pro 11″ M4: 130 s

    Reply
  5. ruudvanderham 25 May 2024 at 8:04 pm

    I also did some count on the number of solutions:
    a) 1152 solutions
    b) 4 solutions
    c) 198 solutions (no idea why @Jim Randell comes to 99)

    Reply
    • Jim Randell 25 May 2024 at 9:04 pm

      @Ruud: For (c) the solutions come in pairs as every solution gives another symmetrical solution with the values A/F, B/G, C/H, D/I, E/J can be swapped over, so I only counted one from each pair.

      Counting separate assignments of symbols to digits you would get twice the number, i.e. 198 solutions (or 128 if you disallow leading zeros – from 64 pairs).

      There are no solutions involving leading zeros for the parts (a) and (b).

      Reply
  6. Frits 27 May 2024 at 12:47 pm

    This program runs in 65/130 ms for PyPy/CPython.

    from itertools import permutations

dgts = set(range(10))

# (a) max ABC + DE + FGH + IJ, we can assume A < F
mx = 0
for A in range(8, -1, -1): 
  for F in range(9, A, -1): 
    if mx // 100 > A + F + 3: break
    for B, D, G, I, C, E, H, J in permutations(dgts - {A, F}):
      ABC = 100*A + 10*B + C
      DE = 10*D + E
      FGH = 100*F + 10*G + H
      IJ = 10*I + J
      if (t := ABC + DE + FGH + IJ) > mx:
        mx = t
        
print("(a):", mx)  

# (b) max (ABC * DE) + (FGH * IJ), we can assume A < F
mx = 0
for A in range(8, -1, -1): 
  for F in range(9, A, -1): 
    # determine highest 2-digit number left
    m2 = [i for i in range(9, -1, -1) if i not in {A, F}][:2]
    m2 = 10 * m2[0] + m2[1]
    
    # break if we can't reach <mx> 
    if (100 * A + m2) * m2 + (100 * F + m2) * m2 < mx: break
    
    for B, C, D, E in permutations(dgts - {A, F}, 4):
      if not (A > B > C) or not (D > E): continue
      ABC = 100*A + 10*B + C
      DE = 10*D + E
      for G, H, I, J in permutations(dgts - {A, F, B, C, D, E}):
        #if not (F > G > H) or not (I > J): continue
        FGH = 100*F + 10*G + H
        IJ = 10*I + J
        if (t := (ABC * DE) + (FGH * IJ)) > mx:
          mx = t

print("(b):", mx)  

# (c) min (ABC * DE) - (FGH * IJ), we can assume A < F 
mn = 99999
for A in range(8, -1, -1): 
  for F in range(9, A, -1): 
    for B, D, G, I, C, E, H, J in permutations(dgts - {A, F}):
      ABC = 100*A + 10*B + C
      DE = 10*D + E
      FGH = 100*F + 10*G + H
      IJ = 10*I + J

      if (t := abs((ABC * DE) - (FGH * IJ))) < mn:
        mn = t
        if t == 0: break
    else: continue
    break
  else: continue
  break   
    
print("(c):", mn)
    Reply

Leave a Comment

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