Enigmatic Code

Programming Enigma Puzzles

Enigma 41: Division bungle

From New Scientist #1183, 29th November 1979 [link]

In making up his latest division sum, with letters substituted for digits, Uncle Bungle has this time left out, not only the divisor, but also the answer.

What is left looks like this:

Enigma 41

Find the divisor and all the digits of the sum, including the answer.

[enigma41]

Advertisements

5 responses to “Enigma 41: Division bungle

  1. jimrandell 30 January 2012 at 10:52 am

    The following Python program runs in 38ms.

    from itertools import combinations
    from enigma import irange, gcd, concat, factor, multiply, printf
    
    d1 = set(irange(0, 9))
    
    # sum 1: rd + d = ss
    for d in irange(6, 9):
      s = (2 * d) % 10
      r = s - 1
    
      # sum 2: rd + vx
      d2 = d1.difference((d, s, r))
      for x in d2:
        (c, t) = divmod(d + x, 10)
        v = d - (r + c)
    
        d3 = d2.difference((x, t, v))
        if len(d3) != 4: continue
    
        # sum 3: vxv + x = vxr
        if not(v + x == r): continue
    
        # at this point we know rd and vxv are multiples of the divisor
        rd = 10 * r + d
        vxv = 101 * v + 10 * x
        if gcd(rd, vxv) < 2: continue
    
        # sum 4: vy + y = xd
        (y, c) = divmod(10 + d, 2)
        if c > 0 or v + 1 != x: continue
    
        d4 = d3.difference((y,))
        if len(d4) != 3: continue
    
        # sum 5: da + x = ym
        for a in d4:
          if a + x < 10: continue
          m = (a + x) % 10
    
        d5 = d4.difference((a, m))
        if len(d5) != 1: continue
    
        # sum 6: vy + t = xm
        if 10 + m != y + t and x != y + 1: continue
    
        # sum 7: tts + s = tvv
        if 10 + v != 2 * s and v != t + 1: continue
    
        dividend = int(concat(s, s, t, r, d, m, m, v, v))
    
        # rd, vxv, vy, da, tts are all multiples of the divisor
        vy = 10 * v + y
        da = 10 * d + a
        tts = 110 * t + s
        ms = (rd, vxv, vy, da, tts)
    
        # find the common factors
        fs = set(factor(ms[0]))
        fs.intersection_update(*map(factor, ms[1:]))
    
        # and consider all possible multiples of them
        for n in irange(1, len(fs)):
          for z in combinations(fs, n):
            divisor = multiply(z)
            (answer, remainder) = divmod(dividend, divisor)
            if remainder != s: continue
            if answer != int(concat(*map(lambda x: x // divisor, (rd, rd, vxv, vy, da, vy, 0, tts)))): continue
    
            printf("{dividend} / {divisor} = {answer} remainder {remainder}")
    

    Solution: 661580022 ÷ 29 = 22813104 remainder 6.

    • jimrandell 30 January 2012 at 1:14 pm

      The following program takes a different approach, based on the form of the answer of the division. It runs in 134ms, and is shorter (although about half of it is checking all the intermediate sums once the answer is found).

      from itertools import permutations
      from enigma import irange, concat, split, printf
      
      # the dividend is sstrdmmvv
      # the answer is AABCDC0E, where A, C, D < B, E, so E is in [4, 9]
      
      ds = set(irange(0, 9))
      for (s, t, r, d, m, v) in permutations(ds, 6):
        if 0 in (s, r, d, v, t): continue
        rd = 10 * r + d
        # ss - rd = d
        if not(11 * s - rd == d): continue
      
        dividend = int(concat(s, s, t, r, d, m, m, v, v))
        tts = 110 * t + s
        # tts = E * divisor for some single digit E
        for E in irange(4, 9):
          (divisor, R) = divmod(tts, E)
          if R > 0: continue
      
          # what would the answer be?
          (answer, R) = divmod(dividend, divisor)
          if not(R == s): continue
          if len(str(answer)) != 8: continue
      
          # does it conform to the required pattern?
          (A, A2, B, C, D, C2, Z, E2) = split(answer, int)
          if not(A == A2 and C == C2 and E == E2 and Z == 0): continue
          if not(len(set((A, B, C, D, E, Z))) == 6): continue
      
          # check all the intermediate calculations, just to be sure
          # rd = A * divisor
          if not(rd == A * divisor): continue
          # vxr - vxv = x
          x = r - v
          # dt - rd = vx
          if not(10 * d + t - rd == 10 * v + x): continue
          # vxv = B * divisor
          (v1, x1, v2) = split(B * divisor, int)
          if not(v1 == v2 == v and x1 == x): continue
          # vy = C * divisor
          (v1, y) = split(C * divisor, int)
          if not(v1 == v): continue
          # xd - vy = y
          if not(x * 10 + d - v * 10 - y == y): continue
          # da = D * divisor
          (d1, a) = split(D * divisor, int)
          if not(d1 == d): continue
          # ym - da = x
          if not(y * 10 + m - d * 10 - a == x): continue
          # xm - vy = t
          if not(x * 10 + m - v * 10 - y == t): continue
          # tvv - tts = s
          if not(11 * v - 10 * t - s == s): continue
      
          # and check all the digits are different
          if not(len(set((s, t, r, d, m, v, x, y, a))) == 9): continue
      
          print("{dividend} / {divisor} = {answer} remainder {s}")
      
      • Jim Randell 13 July 2014 at 9:30 am

        Using the SubstitutedDivision() solver from the enigma.py library solves the problem in 66ms.

        from enigma import SubstitutedDivision
        
        # we can infer the result from the intermediate subtraction sums, it
        # has 8 digits and matches AABCDC0E
        #
        # the dividend has 9 digits and the result has 8 digits therefore the
        # divisor is in the range:
        #   [ 112345566 / 99876706, 998765544 / 11234305 ] = [ 2, 88 ]
        # but two of the intermediate sums have three digits, so the divisor
        # is two digits
        
        SubstitutedDivision(
          'sstrdmmvv', '??', '????????',
          [('ss', 'rd', 'd'), ('dt', 'rd', 'vx'), ('vxr', 'vxv', 'x'), ('xd', 'vy', 'y'), ('ym', 'da', 'x'), ('xm', 'vy', 't'), None, ('tvv', 'tts', 's')]
        ).go()
        
  2. Julian Gray 29 October 2015 at 6:20 pm

    Jim, sorry to be a nuisance! I have just tackled Enigma 41 and couldn’t solve it. When I applied your published solution it indicated a misprint in the division. The last line three-digit line should be t t s, not t s s.

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: