Enigmatic Code

Programming Enigma Puzzles

Enigma 1691: Factory parts

From New Scientist #2858, 31st March 2012 [link]

The number 3120 is divisible without remainder by each number in the following set: 3, 312, 12, 120, 2 and 20. Each of these numbers will be called a visible proper divisor (VPD) of 3120 because each is visible either as a single digit or as a group of adjacent digits in 3120. (1 and 3120 have been excluded as being improper, in order that any prime number has no VPDs).

ENIGMA represents an odd six-digit number in which all the digits are different. The set of all VPDs of ENIGMA is E, NI, IG, G, GMA, M, MA, and A. What is ENIGMA?

[enigma1691]

Advertisements

6 responses to “Enigma 1691: Factory parts

  1. Jim Randell 28 March 2012 at 7:21 pm

    Here’s my first attempt in Python. It runs in 1.7s.

    from itertools import permutations
    from enigma import concat, printf
    
    ds = set(range(1, 10))
    ls = ("ENIGMA", "E", "NI", "IG", "G", "GMA", "M", "MA", "A")
    
    # A must be odd
    for A in (1, 3, 5, 7, 9):
      l2n = { 'A': A }
      # and the other letters must be non-zero
      for s in permutations(ds.difference((A,)), 5):
        l2n.update(zip("ENIGM", s))
        vpds = list(int(concat(*(l2n[i] for i in l))) for l in ls)
        ENIGMA = vpds.pop(0)
    
        # check all VPDs divide ENIGMA
        if any(ENIGMA % vpd for vpd in vpds): continue
    
        # check that these are the only VPDs
        s = str(ENIGMA)
        n = len(s)
        vs = []
        for i in range(n):
          for j in range(i+1, n+1):
            vpd = int(s[i:j])
            if vpd in (1, ENIGMA): continue
            if ENIGMA % vpd: continue
            vs.append(vpd)
        if vs != vpds: continue
    
        printf("ENIGMA={ENIGMA}, VPDs: {vpds}")
    

    Solution: ENIGMA = 921375.

    • Jim Randell 28 March 2012 at 11:28 pm

      As 1 is not allowed as a VPD, we can ignore cases where one of E, G, M, A is 1. This version runs in 794ms (and gives the same answer).

      from itertools import permutations
      from enigma import concat, printf
      
      ds = set(range(1, 10))
      ls = ("ENIGMA", "E", "NI", "IG", "G", "GMA", "M", "MA", "A")
      
      # 1 is not allowed as a VPD, so E, G, M, A cannot be 1
      
      # A must be odd
      for A in (3, 5, 7, 9):
        l2n = { 'A': A }
        for EGM in permutations(ds.difference((A, 1)), 3):
          l2n.update(zip("EGM", EGM))
          for NI in permutations(ds.difference((A,), EGM), 2):
            l2n.update(zip("NI", NI))
            vpds = list(int(concat(*(l2n[i] for i in l))) for l in ls)
            ENIGMA = vpds.pop(0)
      
            # check all VPDs divide ENIGMA
            if any(ENIGMA % vpd for vpd in vpds): continue
      
            # check that these are the only VPDs
            s = str(ENIGMA)
            n = len(s)
            vs = []
            for i in range(n):
              for j in range(i+1, n+1):
                vpd = int(s[i:j])
                if vpd in (1, ENIGMA): continue
                if ENIGMA % vpd: continue
                vs.append(vpd)
            if vs != vpds: continue
      
            printf("ENIGMA={ENIGMA}, VPDs: {vpds}")
      
      • Jim Randell 29 March 2012 at 7:44 am

        Here’s a version that sets up the indices of substrings that are VPDs, and those that aren’t VPDs. It runs in 135ms.

        from itertools import permutations
        from enigma import concat, printf
        
        # substrings that are VPDs
        vpds = ((0, 1), (1, 3), (2, 4), (3, 4), (3, 6), (4, 5), (4, 6), (5, 6))
        
        # substrings that aren't
        nvpds = list((i, j) for i in range(7) for j in range(i + 1, 7) if (i, j) not in vpds)
        nvpds.remove((0, 6)) # but not the whole string
        
        # 1 is not allowed as a VPD, so E, G, M, A cannot be 1
        # A must be odd
        
        ds = set(range(1, 10))
        for A in (3, 5, 7, 9):
          for E, G, M in permutations(ds.difference((A, 1)), 3):
            for N, I in permutations(ds.difference((A, E, G, M)), 2):
              s = concat(E, N, I, G, M, A)
              ENIGMA = int(s)
              # check all VPDs divide ENIGMA
              if any(ENIGMA % int(s[i:j]) for i, j in vpds): continue
              # check the other substrings aren't VPDs
              if any(map(lambda x: x > 1 and ENIGMA % x == 0, (int(s[i:j]) for i, j in nvpds))): continue
        
              printf("ENIGMA={ENIGMA}")
        
  2. Brian Gladman 29 March 2012 at 12:37 pm

    Here is my version:

    from itertools import permutations
    
    # The units digit of the divisors must all be odd because ENIGMA is odd 
    # and cannot hence have an even divisor.  But E, G, M and A cannot be 1
    # because 1 is excluded as a proper divisor. Hence I must be 1 and N is
    # not 0.
      
    vpdw = ( 'E', 'NI', 'IG', 'G', 'GMA', 'M', 'MA', 'A')
    d = { 'I':'1' }
    for p in permutations('3579', 4):
      d.update(zip('AEGM', p))
      for n in '2468':
        d['N'] = n
        enigma = int(''.join(d[c] for c in 'ENIGMA')) 
        vpd = tuple(int(''.join(d[c] for c in w)) for w in vpdw)
        if not any(enigma % x for x in vpd):
          print('ENIGMA =', enigma)
    
    • Jim Randell 3 April 2012 at 8:42 am

      Your analysis massively reduces the search space to only 96 cases, only one of which has all of the required VPDs. Although I think it is still necessary to check that that candidate has no other VPDs to strictly satisfy the conditions of the question.

      Here’s my final code. It executes in 37ms.

      from itertools import permutations
      from enigma import concat, printf
      
      # indices of substrings that are VPDs
      vpdw = ( "E", "NI", "IG", "G", "GMA", "M", "MA", "A" )
      vpds = list((a, a + b) for a, b in (("ENIGMA".find(w), len(w)) for w in vpdw))
      
      # and indices of substrings that aren't
      nvpds = list((i, j) for i in range(7) for j in range(i + 1, 7) if (i, j) not in vpds)
      nvpds.remove((0, 6)) # but not the whole string
      
      # E, I, G, M, A must all be odd (as ENIGMA can have no even divisors)
      # also 1 is not allowed as a VPD, so E, G, M, A cannot be 1
      # hence I = 1, and A, E, G, M are 3, 5, 7, 9 (in some order)
      # leaving N to be an even (non-zero) digit
      
      I = 1
      for (A, E, G, M) in permutations((3, 5, 7, 9)):
        for N in (2, 4, 6, 8):
          s = concat(E, N, I, G, M, A)
          ENIGMA = int(s)
          # check all VPDs divide ENIGMA
          if any(ENIGMA % int(s[i:j]) for i, j in vpds): continue
          # check the other substrings aren't VPDs
          if any(ENIGMA % n == 0 for n in (int(s[i:j]) for i, j in nvpds) if n > 1): continue
          printf("ENIGMA={ENIGMA}")
      
  3. Brian Gladman 3 April 2012 at 4:27 pm

    If I had got more than one solution, I would have done so 🙂

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: