Enigmatic Code
Programming Enigma Puzzles
Enigma 206: Division. Some letters for digits, some digits missing
Posted by on 13 July 2014
From New Scientist #1352, 7th April 1983 [link]
In the following division sum some of the digits are missing, and some are replaced by letters. The same letter stands for the same digit wherever it appears:
Find the correct sum.
[enigma206]
Enigmatic Code 
I’m not really a fan of these long-division type of problems, so I thought it might be more interesting to write a generic solver for such substituted division sum problems. It’s quite an interesting problem to tackle, and trickier than I initially expected, but I ended up with a generic class that can be used to solve several Enigma puzzles already published. I shall add it to the enigma.py library, but if you fancy a challenge you can try writing your own long division solver.
The algorithm I use looks for numbers that match the given divisor of the sum, and then goes through the intermediate subtraction sums to find single digit multiples of the divisor that match with the intermediate subtraction sums. This gives us the digits of the result, and so by considering the remainder we can deduce the dividend of the sum. We then check that all the intermediate sums fully match, and hence find possible solutions.
For this particular problem the code runs in 141ms.
from collections import namedtuple from enigma import irange, nconcat, split, sprintf, int2base, printf SubstitutedDivisionSolution = namedtuple('SubstitutedDivisionSolution', 'a b c r d') class SubstitutedDivision(object): def __init__(self, dividend, divisor, result, intermediates, mapping={}, wildcard='?', digits=None): self.dividend = dividend self.divisor = divisor self.result = result self.intermediates = intermediates self.mapping = mapping self.wildcard = wildcard self.base = 10 self.digits = (set(irange(0, self.base - 1)) if digits is None else digits) # checks: there should be an intermediate for each digit of the result assert len(result) == len(intermediates) # solutions are generated as a named tuple (a, b, c, r, d) # where a / b = c rem r, and d is mapping of symbols to digits def solve(self): # first let's have some internal functions useful for the solver wildcard = self.wildcard base = self.base digits = self.digits # update a map consistently with (key, value) pairs # an updated mapping will be returned, or None def update(d, kvs): for (k, v) in kvs: if k == wildcard: # if k is a wildcard then that's OK pass elif k in d: # if k is already in the map it had better map to v if d[k] != v: return None else: # both k and v should be new values in the map if v in d.values(): return None # update the map d = d.copy() d[k] = v return d # match a string <s> to a number <n> using mapping <d> # an updated mapping will be returned, or None def match_number(d, s, n): # the empty string matches 0 if s == '': return (d if n == 0 else None) # split the number into digits ns = split(int2base(n, base), int) # they should be the same length if len(s) != len(ns): return None # try to update the map return update(d, zip(s, ns)) # match multiple (<s>, <n>) pairs def match_numbers(d, *args): for (s, n) in args: d = match_number(d, s, n) if d is None: break return d # generate possible numbers matching <s> with dictionary <d> def generate_numbers(s, d, slz=True): # the empty string matches 0 if s == '': yield (0, d) elif len(s) == 1: if s == wildcard: for x in digits: if not(slz and x == 0): yield (x, d) elif s in d: x = d[s] if not(slz and x == 0): yield (x, d) else: for x in digits: if not(slz and x == 0): d2 = update(d, [(s, x)]) if d2: yield (x, d2) else: # multi-character string, do the final character for (y, d1) in generate_numbers(s[-1], d, False): # and the rest for (x, d2) in generate_numbers(s[:-1], d1, slz): yield (base * x + y, d2) # match strings <md> against single digit multiples of <n>, according to map <d> # return (<list of single digits>, <map>) def generate_multiples(ms, n, d): if not ms: yield ([], d) else: # find a match for the first one (m, s) = ms[0] # special case: s is None matches 0 if s is None: if m == wildcard: for (x, d2) in generate_multiples(ms[1:], n, d): yield ([0] + x, d2) elif m in d: if d[m] == 0: for (x, d2) in generate_multiples(ms[1:], n, d): yield ([0] + x, d2) else: if 0 not in d.values(): d2 = d.copy() d2[m] = 0 for (x, d3) in generate_multiples(ms[1:], n, d2): yield ([0] + x, d3) # if m is already allocated elif m in d: i = d[m] d2 = match_number(d, s, i * n) if d2 is not None: for (x, d3) in generate_multiples(ms[1:], n, d2): yield ([i] + x, d3) # generate allowable non-zero digits for wildcard/new assignment else: for i in digits: if i == 0: continue if m != wildcard and i in d.values(): continue d2 = match_number(d, s, i * n) if d2 is None: continue # and the rest for (x, d3) in generate_multiples(ms[1:], n, d2): d4 = (d3 if m == wildcard else update(d3, [(m, i)])) if d4 is not None: yield ([i] + x, d4) # match the intermediates/dividend against the actual values in a/b = c # an updated mapping will be returned, or None def match_intermediates(a, b, c, zs, dividend, d): i = len(int2base(a, base)) - len(zs) sx = dividend[:i] sxr = list(dividend[i:]) n = base ** (len(zs) - 1) z = 0 # consider each intermediate sum: x - y = z for s in zs: sx = sx + sxr.pop(0) (x, a) = divmod(a, n) x = base * z + x (y, c) = divmod(c, n) y *= b z = x - y # the remainder must be in the correct range if not(0 <= z < b): return if s is None: # there is no intermediate when y == 0 assert y == 0 else: d = match_numbers(d, (s, z), (sx, x)) if d is None: return sx = s n //= base yield d # now for the actual solver dividend = self.dividend divisor = self.divisor result = self.result intermediates = self.intermediates # in the intermediates (x - y = z) we're interested in the ys and the zs # (we index from the end in case the xs have been provided) ys = list((None if s is None else s[-2]) for s in intermediates) zs = list((None if s is None else s[-1]) for s in intermediates) # list of (<digit of result>, <multiple of divisor>) pairs ms = list(zip(result, ys)) # initial mapping of letters to digits d0 = self.mapping # consider the sum as: a / b = c remainder r # consider possible divisors (b) for (b, d1) in generate_numbers(divisor, d0): # find multiples of the divisor that match for (cd, d2) in generate_multiples(ms, b, d1): # the result (c) is now defined c = nconcat(cd, base=base) # find possible remainders (r) for (r, d3) in generate_numbers(intermediates[-1][1], d2): # so the actual sum is a / b = c rem r a = b * c + r # check that the computed dividend matches the template d4 = match_number(d3, dividend, a) if d4 is None: continue # now check the intermediate results match up for d5 in match_intermediates(a, b, c, zs, dividend, d4): yield SubstitutedDivisionSolution(a, b, c, r, d5) # generate actual intermediates # note: "empty" intermediate sums are not returned def solution_intermediates(self, s): (a, x, c, intermediates) = (list(int2base(s.a, self.base)), 0, 0, []) while a: x = x * self.base + int(a.pop(0)) (y, r) = divmod(x, s.b) if y == 0: continue intermediates.append((x, s.b * y, r)) c = c * self.base + y x = r return intermediates # output the solution def solution(self, s): (a, b, c, r, d) = s printf("{a} / {b} = {c} rem {r} [{d}] [{intermediates}]", d=' '.join(k + '=' + str(d[k]) for k in sorted(d.keys())), intermediates=', '.join(sprintf("{x} - {y} = {z}") for (x, y, z) in self.solution_intermediates(s))) # create the division sum p = SubstitutedDivision( 'pkmkh', '??', '???', [('pmd', 'xp'), ('??', 'kh'), ('mbg', 'k')] ) # look for solutions for s in p.solve(): p.solution(s)Solution: The correct sum is: 47670 ÷ 77 = 619 remainder 7.
I have now replaced the [[
SubstitutedDivision()]] solver in the enigma.py library with a more flexible version (based on the [[SubstitutedExpression()]] solver).This puzzle can now be solved using the following run-file, which executes in 110ms.