Enigmatic Code

Programming Enigma Puzzles

Enigma 63: Addition: letters for digits

From New Scientist #1206, 19th June 1980 [link]

Below is an addition sum with letters substituted for digits. The same letter stands for the same digit wherever it appears, and different letters stand for different digits.

Enigma 63

Write the sum out with numbers substituted for letters.

Enigma 21 is also called “Addition: letters for digits”.

[enigma63]

Advertisements

4 responses to “Enigma 63: Addition: letters for digits

  1. Jim Randell 8 January 2013 at 9:13 am

    The following Python program tries all permutations. It runs in 1.1s.

    from itertools import permutations
    from enigma import irange, nconcat, split, printf
    
    ds = set(irange(0, 9))
    for (L, B, R, Q, E, S, V) in permutations(ds, 7):
      if L == 0 or B == 0: continue
      s1 = nconcat(L, B, R, L, Q, Q, R)
      s2 = nconcat(L, B, B, B, E, S, L)
      s3 = nconcat(L, B, R, E, R, Q, R)
      s4 = nconcat(L, B, B, B, E, V, R)
      r = str(s1 + s2 + s3 + s4)
      if len(r) != 8: continue
      (b1, b2, e1, K, v1, M, G, l1) = split(r, int)
      if not(b1 == b2 == B): continue  
      if not(e1 == E and v1 == V and l1 == L): continue
      s = set((K, M, G))
      if len(s) != 3 or s.intersection((L, B, R, Q, E, S, V)): continue
    
      printf("{s1} + {s2} + {s3} + {s4} = {r}")
    

    Solution: The sum is 8308440 + 8333218 + 8302040 + 8333260 = 33276958.

    • Jim Randell 8 January 2013 at 9:19 am

      Having done a couple of these sums with letters substituted for digits recently I thought it would be fun to write a general solver for them.

      The following code takes a straightforward right-to-left approach on the columns of the sum, recursively examining the possibilities for each column. There are three interfaces to it: _substituted_sum() is the core of the algorithm, but it assumes its arguments are nicely formed. substituted_sum() is a friendlier way to run the algorithm, it makes sure the arguments are valid and fills out sensible default values. SubstitutedSum() wraps the previous function as a class so you don’t have to remember the terms in sum itself, and provides some handy functions for reporting solutions.

      Gratifyingly this solution runs in 139ms, nearly 10× faster than the previous solution.

      from itertools import permutations
      from enigma import uniq
      
      # a substituted sum solver
      # terms - list of summands of the sum (each the same length as result)
      # result - the result of the sum (sum of the terms)
      # digits - set of unallocated digits
      # l2d - map from letters to allocated digits
      # d2i - map from digits to letters that cannot be allocated to that digit
      # n - column we are working on (string index in result)
      # carry - carry from the column to the right
      # base - base we are working in
      # solutions are returned as assigments of letters to digits (the l2d dict)
      def _substituted_sum(terms, result, digits, l2d, d2i, n, carry=0, base=10):
        # are we done?
        if n == 0:
          if carry == 0:
            l2d.pop('_', None)
            yield l2d
          return
        # move on to the next column
        n -= 1
        # find unallocated letters in this column
        u = list(uniq(t[n] for t in terms if t[n] not in l2d))
        # and allocate them from the remaining digits
        for ds in permutations(digits, len(u)):
          _l2d = l2d.copy()
          _l2d.update(zip(u, ds))
          # sum the column
          (c, r) = divmod(sum(_l2d[t[n]] for t in terms) + carry, base)
          # is the result what we expect?
          if result[n] in _l2d:
            # the digit of the result is already allocated, check it
            if _l2d[result[n]] != r: continue
            allocated = ds
          else:
            # the digit in the result is one we haven't come across before
            if r not in digits or r in ds: continue
            _l2d[result[n]] = r
            allocated = ds + (r,)
          # check there are no invalid allocations
          if any(any(_l2d[x] == d for x in ls if x in _l2d) for (d, ls) in d2i.items()): continue
          # try the next column
          for r in _substituted_sum(terms, result, digits.difference(allocated), _l2d, d2i, n, c, base):
            yield r
      
      # friendly interface to the substituted sum solver
      # terms - list of summands in the sum
      # result - result of the sum (sum of the terms)
      # digits - digits to be allocated (default: 0 - base-1)
      # l2d - initial allocation of digits (default: all digits unallocated)
      # d2i - invalid allocations (default: leading digits cannot be 0)
      # base - base we're working in (default: 10)
      def substituted_sum(terms, result, digits=None, l2d=None, d2i=None, base=10):
        # fill out the parameters
        if digits is None: digits = range(base)
        digits = set(digits)
        if l2d is None: l2d = dict()
        if d2i is None:
          d2i = dict()
          d2i[0] = ''.join(uniq(x[0] for x in terms + [result]))
        # number of columns in sum
        n = len(result)
        # make sure the terms are the same length as the result
        ts = list('_' * (n - len(t)) + t for t in terms)
        l2d['_'] = 0
        # call the solver
        for r in _substituted_sum(ts, result, digits, l2d, d2i, n, 0, base):
          yield r
      
      # object interface to the substituted sum solver
      class SubstitutedSum(object):
      
        def __init__(self, terms, result, digits=None, l2d=None, d2i=None, base=10):
          self.terms = terms
          self.result = result
          self.digits = digits
          self.l2d = l2d
          self.d2i = d2i
          self.base = base
          self.text = ' + '.join(terms) + ' = ' + result
          
        def solve(self):
          for r in substituted_sum(self.terms, self.result, digits=self.digits, l2d=self.l2d, d2i=self.d2i, base=self.base):
            yield r
      
        def substitute(self, l2d, text):
          digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' # up to base 36
          return ''.join((digits[l2d[c]] if c in l2d else c) for c in text)
      
        def solution(self, l2d):
          # output the assignments in letter order
          print(' '.join(k + '=' + str(l2d[k]) for k in sorted(l2d.keys())))
          # print the sum with digits substituted in
          print(self.substitute(l2d, self.text))
      
      p = SubstitutedSum(['LBRLQQR', 'LBBBESL', 'LBRERQR', 'LBBBEVR'], 'BBEKVMGL')
      for s in p.solve():
        p.solution(s)
      

      I will probably clean this up, add some more documentation and put it in my enigma.py library for future use.

  2. Naim Uygun 8 January 2013 at 4:06 pm
    from itertools import permutations
    for c in permutations("9876543210"):
       L,B,R,Q,E,S,V,K,M,G = c
       if int(L)==0:continue
       if int(B)==0: continue
       if int(B)>3: continue
       n1=L+B+R+L+Q+Q+R
       n2=L+B+B+B+E+S+L
       n3=L+B+R+E+R+Q+R
       n4=L+B+B+B+E+V+R
       n5=B+B+E+K+V+M+G+L
       total=int(n1)+int(n2)+int(n3)+int(n4)
       if total != int(n5): continue
       print("{0} + {1} + {2} + {3}= {4}".format(n1,n2,n3,n4,total))
       input("THE END")
    
  3. geoffrounce 1 August 2016 at 9:53 am
    % A solution in MiniZinc
    include "globals.mzn";
    
    var 0..9:L;  
    var 0..9:B;  
    var 0..9:R;  
    var 0..9:Q;   
    var 0..9:E;  
    var 0..9:S;  
    var 0..9:V;  
    var 0..9:K; 
    var 0..9:M;  
    var 0..9:G;  
    
    constraint alldifferent([L,B,R,Q,E,S,V,K,M,G])
    /\ L > 0 /\ B > 0;
    
    constraint
       (L*1000000 + B*100000 + R*10000 + L*1000
         + Q*100 + Q*10 + R) +
       (L*1000000 + B*100000 + B*10000 + B*1000
         + E*100 + S*10 + L) +
       (L*1000000 + B*100000 + R*10000 + E*1000
         + R*100 + Q*10 + R) +
       (L*1000000 + B*100000 + B*10000 + B*1000
         + E*100 + V*10 + R) ==
       (B*10000000 + B*1000000 + E*100000
         + K*10000 + V*1000 + M*100 + G*10 + L);
    
    solve satisfy;
    
    output ["[L,B,R,Q,E,S,V,K,M,G] = " ++ show (L),show(B), 
            show(R),show(Q),show(E),show(S),show(V),show(K),
            show(M),show(G)];
    
    % Output
    % [L,B,R,Q,E,S,V,K,M,G] = 8304216795
    % ----------
    % Finished in 79msec
    % Comment :letter sum is: LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL
    % so constructed digit sum is:  8308440 + 8333218 + 8302040 + 8333260 = 33276958
    %
    
    

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: