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 |
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 treated as symbols that can be mapped to other digits. But if 'map_digits' is set to False, digits will be treated as literal values but are not excluded from also being represented by 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 symbols to numeric 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 (as integers) 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 True) ''' def __init__(self, terms, total, *, digits=None, l2d={}, d2nv=None, base=10, map_digits=True): 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 symbol' map is given, set it # to exclude leading zeros self.d2inv = ({0:set(c[0] for c in list(terms) + [total])} if d2nv is None else d2nv) self.digits = set(range(base) if digits is None else 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 symbols to numeric 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 (right to left) for t in self.terms: try: column.append(t[col]) except IndexError: continue # now extract symbols in the column with symbols 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) syms = 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 syms 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(syms)): # skip this permutation if any letters have digits that are not allowed if any(l in self.d2inv.get(d, set()) for l, d in zip(syms, dgts)): continue # update the map to account for the new letter to digit mappings l2dn = l2d.copy() l2dn.update(zip(syms, 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 digits are literals and the total is a digit if not self.map_digits and self.is_dgt(t_sym): if self.to_dgt(t_sym) != d: continue else: # if the total symbol has been allocated a digit if t_sym in l2dn: if l2dn[t_sym] != d: continue # don't allocate the digit if it is already allocated or invalid elif d in l2dn.values() or t_sym in self.d2inv.get(d, set()): continue l2dn[t_sym] = d # move to the next column 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] if c in l2d else int(c) for c in t), 0) for t in self.terms], reduce(f, (l2d[c] if c in l2d else int(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 output 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 solutions (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