# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1271: Roman ring

From New Scientist #2429, 10th January 2004

George recalled the junior school word game of turning DOG into CAT and back to DOG, changing just one letter at a time forming a valid English word at each step, without using the same word twice.

He now proposed a similar puzzle using Roman numerals – for example one eight step loop might be:

George’s rules are that each “word” must be a valid Roman numeral of six different letters and beginning with “M”. Just one letter is changed at each step.

By analogy with DOG and CAT, George proposes to change the smallest possible Roman numeral within his rules (MCXLIV) to the largest (MDCLXV) and back to MCXLIV in the smallest possible number of steps with no repetition of any numeral.

What is the “Arabic” value of the numeral which comes exactly half way round the cycle from MCXLIV back to MCXLIV?

This completes the archive of puzzles for 2004, which means there is now a full archive of the most recent 10 years of Enigma puzzles from the start of 2004 to the final Enigma at the end of 2013 (510 puzzles).

There are also 244 puzzles from the start of Enigma in February 1979 up to December 1983 (there next puzzle published will complete 1983), bringing the grand total number of puzzles on the site to 755, which is around 42% of all Enigma puzzles.

[enigma1271]

### One response to “Enigma 1271: Roman ring”

1. Jim Randell 13 December 2014 at 8:35 am

This Python 3 program used the int2roman() and roman2int() functions from the enigma.py library to deal with Roman Numerals. It runs in 61ms.

```from collections import defaultdict
from enigma import irange, int2roman, roman2int, printf

# find 6 different digit romans beginning with M
romans = list()
for i in irange(1144, 1665):
r = int2roman(i)
if len(r) == 6 and len(set(r)) == 6 and r[0] == 'M':
romans.append(r)

# for each one find ones that are only one digit different
step = dict()
for r in romans:
step[r] = list(t for t in romans if sum(1 for (x, y) in zip(r, t) if x == y) == 5)

# extend sequence <rs> of romans from <s> to <f>
def solve(s, f, rs):
if s == f:
yield rs
else:
for r in step[s]:
if r not in rs:
yield from solve(r, f, rs + [r])

# record sequences by length
m = defaultdict(list)
# start and finish
(r1, r2) = ('MCXLIV', 'MDCLXV')
# go from r1 to r2
for rs1 in solve(r1, r2, []):
# and back from r2 to r1
for rs2 in solve(r2, r1, rs1):
rs = [r1] + rs2
m[len(rs)].append(rs)

# find the shortest sequences
k = min(m.keys())
printf("min sequence = {k}")
for s in m[k]:
printf("middle = {i} [{s}]", i=roman2int(s[k // 2]), s=' '.join(s))
```

Solution: The value of the Roman Numeral in the middle of sequence is 1546 (= MDXLVI).

The full sequence is shown below:

(or its reverse).

The numeral in red is changed to the numeral in blue on the line below.