# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1195: Damn love

From New Scientist #2351, 13th July 2002 [link]

You are probably familiar with the word-chain game where you have to get from one word
to another by changing one letter at a time, making a proper word at each stage.
For example one shortest chain for changing DAMN to LOVE is:

DAMN – DAME – DOME – DOVE – LOVE.

Your task today is to find a shortest chain from MALE to DIRT. But your chain has to have a further property. You have to consistently replace each letter by a non-zero digit throughout the chain, different digits being used for different letters. For example, one such substitution in the above chain yields:

1863 – 1869 – 1769 – 1749 – 5749.

In that chain some of the four-figure numbers are prime and some are not. But in your substitution for a shortest MALE to DIRT chain all the four-figure numbers must be primes less than 2500.

What is the number for MALE?

[enigma1195]

### 2 responses to “Enigma 1195: Damn love”

1. Jim Randell 2 November 2015 at 7:17 am

The shortest possible chains will have 3 intermediate words, with one of the four letters/digits being changed at each step.

This Python 3 program looks for chains of 5 primes where each of the four digits are changed in one of the transitions. Then by considering the first prime to correspond to MALE and the final prime to correspond to DIRT we can assign letters to each of the primes. We then eliminate chains where the “words” created by substituting letters for digits do not appear in a suitable word list.

I’ve used the sowpods.txt list of valid Scrabble words (that I used in Enigma 288a) but other word lists can be used.

This Python 3 program runs in 245ms (using sowpods.txt).

```from itertools import permutations
from collections import defaultdict
from enigma import Primes, join, printf

# primes below 2500
MAX = 2499
primes = Primes(MAX)

# find 4 digit primes with non-zero distinct digits
ps = list()
for n in primes.range(1000, MAX):
s = str(n)
if '0' in s or len(set(s)) != 4: continue
ps.append(s)
printf("[{n} candidate primes]", n=len(ps))

# return the indices that differ in two strings
def diffs(a, b):
return list(i for (i, (x, y)) in enumerate(zip(a, b)) if x != y)

# compile transitions that change one digit
ts = defaultdict(list)
for (p, q) in permutations(ps, 2):
ds = diffs(p, q)
if len(ds) != 1: continue
ts[(p, ds[0])].append(q)

# produce chains of primes
# ds - indices for the transitions
# s - sequence of primes
def chains(ds, s):
if not ds:
yield s
else:
for x in ts[(s[-1], ds[0])]:
yield from chains(ds[1:], s + [x])

# record solutions
solns = list()
# consider possible digit orders
for ds in permutations((0, 1, 2, 3)):
# consider possible starting primes
for p in ps:
for s in chains(ds, [p]):
# chains go from MALE -> DIRT
ss = s[0] + s[-1]
if len(set(ss)) != 8: continue
d2l = dict((d, l) for (d, l) in zip(ss, 'MALEDIRT'))
ws = list(join(d2l[x] for x in p) for p in s)
solns.append((s, ws))
printf("{ds}: {s} -> {ws}")

# find valid words
file = 'sowpods.txt'
words1 = set().union(*(ws for (ps, ws) in solns))
words = set()
w = w.strip().upper()
if w in words1:
printf("valid words = {words}, rejected = {x}", x=words1.difference(words))

# solutions that only use valid words
for (ps, ws) in solns:
if words.issuperset(ws):
printf("{ps} -> {ws}")
```

Solution: MALE = 2459.

The three chains I found are:

MALE → DALE → DARE → DIRE → DIRT / 2459 → 1459 → 1489 → 1789 → 1783
MALE → DALE → DARE → DART → DIRT / 2459 → 1459 → 1489 → 1483 → 1783
MALE → DALE → DALT → DART → DIRT / 2459 → 1459 → 1453 → 1483 → 1783

DALT is apparently an obsolete Scottish word for a foster child.

When considering the chains of numbers the program finds additional chains from 1783 → 2459, but these require use of the words MIRT and MILT. There are also additional solutions from 2459 → 1783 that use the word DILT. But the only valid numerical chains are between 2459 and 1783.

If the maximum prime is raised to 2543 then we can find additional chains from 2543 → 1789 (e.g. MALE → DALE → DARE → DIRE → DIRT / 2543 → 1543 → 1583 → 1783 → 1789).

2. Brian Gladman 5 November 2015 at 11:12 am
```from itertools import permutations
from collections import defaultdict
from number_theory import Primes

prime_limit = 2500

# compile a list of valid four letter words
valid_words = set()
if len(w) == 5:

# four digit primes below limit
pr = set(str(x) for x in Primes().list(1000, prime_limit))
# primes with no zeros or repeated digits (for the shortest
# chain each letter in any word can only be from either MALE
# or DIRT so all words must have different letters)
pr = set(x for x in pr if '0' not in x and len(set(x)) == 4)

# for each possible prime, list the primes that can follow it
pi = defaultdict(list)
for p, q in permutations(pr, 2):
if sum(1 for x, y in zip(p, q) if x != y) == 1:
pi[p] += [q]

# create a chain of five primes in which only one digit
# changes between adjacent primes and the initial and
# final primes share no common digits
def chain(pl):
if len(pl) == 5:
if not set(pl[0]) & set(pl[-1]):
yield tuple(pl)
else:
for q in pi[pl[-1]]:
yield from chain(pl + [q])

# find all solutions and convert the five primes
# in each solution to words
for p in pr:
for pc in chain([p]):
# use initial and final values to create a dictionary
d = dict(zip(pc[0] + pc[4], 'MALEDIRT'))
# and convert all five values into words
wc = tuple(''.join(d[l] for l in n) for n in pc)
if set(wc) <= valid_words:
print(pc, wc)
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.