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:

Enigma 206

Find the correct sum.

[enigma206]

Advertisements

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"
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: