# Enigmatic Code

Programming Enigma Puzzles

## Enigma 206: Division. Some letters for digits, some digits missing

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]

### 2 responses to “Enigma 206: Division. Some letters for digits, some digits missing”

1. Jim Randell 13 July 2014 at 7:51 am

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.

2. Jim Randell 16 July 2017 at 11:13 am

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.

```#!/usr/bin/env python -m enigma -r

SubstitutedDivision

"pkmkh / ?? = ???"

"pkm - pmd = xp"
"xpk - ?? = kh"
"khh - mbg = k"
```