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]

Advertisements

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()
    for w in open(file).readlines():
      w = w.strip().upper()
      if w in words1:
        words.add(w)
    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()
    for w in open('..\sowpods.txt').readlines():
      if len(w) == 5:
        valid_words.add(w.strip().upper())
    
    # 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)
    

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: