Enigmatic Code
Programming Enigma Puzzles
Enigma 63: Addition: letters for digits
Posted by on 8 January 2013
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.
Write the sum out with numbers substituted for letters.
Enigma 21 is also called “Addition: letters for digits”.
[enigma63]
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.
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 the enigma.py library for future use.
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")% 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 %