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

8 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 irange, 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 irange(0, 6) for j in irange(i + 1, 6) 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]) != 0 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 🙂

4. geoffrounce 20 March 2018 at 2:28 pm

A brute force programme in MiniZinc took 2 sec.

```% A Solution in MiniZinc
include "globals.mzn";

var 1..9:E; var 1..9:N; var 1..9:I; var 1..9:G;
var 1..9:M; var 1..9:A;

var 100000..999999: ENIGMA = 100000*E + 10000*N
+ 1000*I + 100*G + 10*M + A;

var 10..99: NI = 10*N + I;
var 100..999: GMA = 100*G + 10*M + A;
var 10..99: MA = 10*M + A;
var 10..99: IG = 10*I + G;

% ENIGMA represents an odd six-digit number
constraint ENIGMA mod 2 == 1;

% 1 is excluded as being an improper divisor
constraint E != 1 /\ G != 1 /\ M != 1 /\ A != 1;

% All the digits are different
constraint  all_different ( [E, N, I, G, M, A] );

% Check all visible proper divisors specified
constraint ENIGMA mod E == 0 /\ ENIGMA mod NI == 0
/\ ENIGMA mod IG == 0 /\ ENIGMA mod G == 0
/\ ENIGMA mod GMA == 0 /\ ENIGMA mod M == 0
/\ ENIGMA mod MA == 0 /\ ENIGMA mod A == 0;

solve satisfy;

output [ "ENIGMA = " ++ show(ENIGMA) ];

% ENIGMA = 921375
% ----------
% Finished in 2s 41msec
```
5. Jim Randell 21 March 2018 at 7:44 am

Here’s a full solution using the SubstitutedExpression() solver from the enigma.py library (which I hadn’t written at the time I posted the puzzle).

It executes in 205ms.

Run: [ @repl.it ]

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

SubstitutedExpression

--invalid="0,AEGIMN" # no leading zeros
--invalid="2|4|6|8,A" # ENIGMA is odd

--verbose=16 # if you only want to see the answer
--answer="ENIGMA"

# check the given VPDs
"ENIGMA % E = 0" "E != 1"
"ENIGMA % NI = 0"
"ENIGMA % IG = 0"
"ENIGMA % G = 0" "G != 1"
"ENIGMA % GMA = 0"
"ENIGMA % M = 0" "M != 1"
"ENIGMA % MA = 0"
"ENIGMA % A = 0" "A != 1"

# and these are the only VPDs
"ENIGMA % N != 0 or N == 1"
"ENIGMA % I != 0 or I == 1"
"ENIGMA % EN != 0"
"ENIGMA % GM != 0"
"ENIGMA % ENI != 0"
"ENIGMA % NIG != 0"
"ENIGMA % IGM != 0"
"ENIGMA % ENIG != 0"
"ENIGMA % NIGM != 0"
"ENIGMA % IGMA != 0"
"ENIGMA % ENIGM != 0"
"ENIGMA % NIGMA != 0"
```

The fact that ENIGMA is odd is not necessary to solve the puzzle, but this fact along with the conditions that E, NI and IG divide ENIGMA are enough to narrow the answer down to a single possibility.