# Alphametic Sum Solver

Here is my version of a solver class for alphametic sums. It follows the interface used by Jim Randell in his enigma.py utilities package but has an additional feature in that, in sums that include both letters and digits, the digits can stand for themselves and in this case these digits can also appear in letter form. The solver (listed below) is available here AlphaSum (this version is slightly modified to add tests).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 |
from itertools import permutations from functools import reduce class AlphaSum(object): ''' A class for solving letters for digits addition puzzles. It returns a dictionary mapping symbols to digits such that, when translated into numeric form, the words in the list 'terms' sum to 'total'. Words can contain symbols and digits with each symbol consistently standing for a different digit. By default any decimal digits that appear are not subject to translation but are not excluded from also being represented by letters. But setting 'map_digits' to True will allow digits to be translated as well as other symbols. terms a list of words that are the addends total the word that is the total of the sum l2d a dictionary that maps letters to digits (this defaults to empty on entry) digits the numeric value of digits that are allowed (defaults to 0 .. base-1 if not present) d2nv a dictionary that maps digits to a string holding the letters that are not valid for this digit (if empty it is set to map 0 to all leading letters) base the number base in use (defaults to 10) map_digits if true digits are mapped (default is false) ''' def __init__(self, terms, total, *, digits=None, l2d={}, d2nv=None, base=10, map_digits=False): self.terms = terms self.total = total self.l2d = l2d self.base = base self.map_digits = map_digits self.text = ' + '.join(terms) + ' = ' + total self.tx = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' # if no 'digit to invalid letter' map is given, set it # to exclude leading zeros if d2nv is None: self.d2ln = ({0:set(c[0] for c in terms + [total])} if d2nv is None else d2nv) else: self.d2ln = d2nv if digits is None: self.digits = set(range(base)) else: self.digits = set(digits) if not self.map_digits: self.is_dgt = lambda x: str(x).upper() in self.tx[:base] self.to_dgt = lambda x: self.tx.index(x.upper()) ''' returns results as a dictionary mapping input letters and, if map_digits is true, digits to digits. ''' def solve(self, l2d=None, col=-1, cry = 0): l2d = self.l2d if l2d is None else l2d column = [] # extract the symbols in the current column for t in self.terms: try: column.append(t[col]) except IndexError: continue # now extract symbols in the column with letters having # allocated digits and, if map_digits is false, digits # being added to the carry from the previous column; such # symbols are then removed from the column so that only # the as yet unallocated symbols are left for ltr in column[:]: if ltr in l2d: cry += l2d[ltr] column.remove(ltr) elif not self.map_digits and self.is_dgt(ltr): cry += self.to_dgt(ltr) column.remove(ltr) symb = tuple(set(column)) try: t_sym = self.total[col] except IndexError: # there is no total for this column so we have finished - we have # a solution if there are no letters to set and no column sum if not symb and not cry: self.l2d = l2d # return the letter to digit mapping that gives the solution yield l2d return # compile the digits that are not yet allocated to letters digits = self.digits.difference(l2d.values()) # permute these digits for the unallocated letters in the current column for dgts in permutations(digits, len(symb)): # skip this permutation if any letters have digits that are not allowed if any(d in self.d2ln and l in self.d2ln[d] for l, d in zip(symb, dgts)): continue # update the map to account for the new letter to digit mappings l2dn = l2d.copy() l2dn.update(zip(symb, dgts)) # now sum the column and form the total digit and the carry c, d = divmod(sum(l2dn[c] for c in column) + cry, self.base) # if decimal digits are not mapped and the total symbol is a digit if not self.map_digits and self.is_dgt(t_sym): dd = self.to_dgt(t_sym) else: # if the total symbol has been allocated a digit if t_sym in l2dn: dd = l2dn[t_sym] # but only allocate the digit if it valid and it has not been # allocated elsewhere elif (d in self.digits and t_sym not in self.d2ln.get(d, ()) and d not in l2dn.values()): l2dn[t_sym] = dd = d else: continue # move to the next column only if the total matches the column sum if dd == d: yield from self.solve(l2dn, col - 1, c) ''' return the word list for the addends and the word for the total ''' def input(self): return self.terms, self.total ''' return the map from letters to digits ''' def map(self, l2d=None): l2d = self.l2d if l2d is None else l2d return ', '.join(c + ':' + str(l2d[c]) for c in sorted(l2d)) ''' return the output numbers list for addends and the number total ''' def result(self, l2d=None): l2d = self.l2d if l2d is None else l2d f = lambda x, y: 10 * x + y return ([reduce(f, (l2d[c] for c in t), 0) for t in self.terms], reduce(f, (l2d[c] for c in self.total), 0)) ''' return <text> with mapped letter values translated to digits ''' def substitute(self, text=None, l2d=None): tx = self.text if text is None else text l2d = self.l2d if l2d is None else l2d return ''.join((self.tx[l2d[c]] if c in l2d else c) for c in tx) ''' return the input, the ouput and the map using the format string <>fmt> where the {0:}, {1:} and {2:} are the input, output and map respectively ''' def output(self, *, fmt='\n{0:}\n{1:}\n{{ {2:} }}', l2d=None): l2d = self.l2d if l2d is None else l2d return fmt.format(self.text, self.substitute(), self.map()) ''' print solutions and the result <sol> (if present) including, if <fn> is present, only those solution (s) for which <fn>(<s>) returns True ''' def go(self, *, sol=None, fn=None): for s in self.solve(): if fn is None or fn(s): print(self.output()) if sol: print(sol + ' -> ' + self.substitute(sol)) |

No comments yet