Sunday Times Teaser 2852 – When in Rome

by Nick MacKinnon

Published May 21 2017 (link)

An ancient five-by-five table of letters have been found in Rome. All the ten different five-letter rows across and five-letter columns down are Roman numerals, with no letter exceeding a C. The across numbers are, in order, even, even, a cube, a prime, and a power of 2. The down numbers include a cube, the rest being even or prime.

Which two Roman numerals cross at the middle square?

3 Comments Leave one →

Brian Gladman permalink


from itertools import product
from number_theory import is_prime, factors

tb = (('I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'),
      ('X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'),
      ('C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'))

# convert integers in the range 1 .. 999 to roman numerals 
def roman(x):
  r, i = '', 0
  while x:
    x, d = divmod(x, 10)
    if d:
      r = tb[i][d - 1] + r
    i += 1
  return r

# map integers to roman numerals and vice versa if the numerals
# are of length five and only include I, V, X, L or C
i2r, r2i = dict(), dict()
for n in range(1, 400):
  r = roman(n)  
  if len(r) == 5 and set(r) <= set('IVXLC'):
    i2r[n] = r
    r2i[r] = n

# list integers that are of the required roman form and are
# also even, cubes, primes and powers of two respectively
ev = [x for x in i2r.keys() if not x & 1]
cb = [x for x in i2r.keys() if round(x ** (1/3)) ** 3 == x]
pr = [x for x in i2r.keys() if is_prime(x)]
p2 = [x for x in i2r.keys() if set(factors(x)) == {2}]

# consider the first two rows of even roman numerals and save
# pairs of rows for which the first two characters in each of 
# the five columns are all possible for valid roman numerals
evp = []
rn2 = set(x[:2] for x in r2i.keys())
evp = tuple((a, b) for a, b in product(ev, ev) if 
        set(x + y for x, y in zip(i2r[a], i2r[b])) < rn2)
  
# consider all possible combinations of the five rows
for e2, c, p, w in product(evp, cb, pr, p2):
  rows = e2 + (c, p, w)
  
  # convert the rows to roman numerals
  roman_rows = tuple(i2r[x] for x in rows)
  # extract the columns as roman numerals 
  roman_cols = tuple(''.join(x) for x in zip(*roman_rows))  
  # where possible convert these roman numerals to integers
  try:
    cols = tuple(r2i[x] for x in roman_cols)
  except KeyError:
    continue
  
  # find any cubes in the columns
  cc = [x for x in cols if x in cb]
  # if there is one and the other columns are either even or prime  
  if cc and all(not x & 1 or x in pr for x in cols if x != cc[0]):
    if len(set(rows + cols)) == 10:
      print(f'{roman_rows[2]} ({rows[2]}) and {roman_cols[2]} ({cols[2]})')
      print(f'rows: {roman_rows} {rows}')
      print(f'cols: {roman_cols} {cols}')
      print()

from itertools import product

from number_theory import is_prime, factors

tb = (('I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'),

('X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'),

('C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'))

# convert integers in the range 1 .. 999 to roman numerals

def roman(x):

r, i = '', 0

while x:

x, d = divmod(x, 10)

if d:

r = tb[i][d - 1] + r

i += 1

return r

# map integers to roman numerals and vice versa if the numerals

# are of length five and only include I, V, X, L or C

i2r, r2i = dict(), dict()

for n in range(1, 400):

r = roman(n)

if len(r) == 5 and set(r) <= set('IVXLC'):

i2r[n] = r

r2i[r] = n

# list integers that are of the required roman form and are

# also even, cubes, primes and powers of two respectively

ev = [x for x in i2r.keys() if not x & 1]

cb = [x for x in i2r.keys() if round(x ** (1/3)) ** 3 == x]

pr = [x for x in i2r.keys() if is_prime(x)]

p2 = [x for x in i2r.keys() if set(factors(x)) == {2}]

# consider the first two rows of even roman numerals and save

# pairs of rows for which the first two characters in each of

# the five columns are all possible for valid roman numerals

evp = []

rn2 = set(x[:2] for x in r2i.keys())

evp = tuple((a, b) for a, b in product(ev, ev) if

set(x + y for x, y in zip(i2r[a], i2r[b])) < rn2)

# consider all possible combinations of the five rows

for e2, c, p, w in product(evp, cb, pr, p2):

rows = e2 + (c, p, w)

# convert the rows to roman numerals

roman_rows = tuple(i2r[x] for x in rows)

# extract the columns as roman numerals

roman_cols = tuple(''.join(x) for x in zip(*roman_rows))

# where possible convert these roman numerals to integers

try:

cols = tuple(r2i[x] for x in roman_cols)

except KeyError:

continue

# find any cubes in the columns

cc = [x for x in cols if x in cb]

# if there is one and the other columns are either even or prime

if cc and all(not x & 1 or x in pr for x in cols if x != cc[0]):

if len(set(rows + cols)) == 10:

print(f'{roman_rows[2]} ({rows[2]}) and {roman_cols[2]} ({cols[2]})')

print(f'rows: {roman_rows} {rows}')

print(f'cols: {roman_cols} {cols}')

print()

Jim Randell permalink

It doesn’t make any difference to the answer, but the 10 numbers given by the Roman numerals in the rows and columns must all be different, so one of the solutions your code finds is disallowed. There is actually only one possible way to fill out the grid

Reply
- Brian Gladman permalink
  
  Thanks for pointing this out Jim. I will update the code accordingly.
  
  Reply

Sunday Times Teaser 2852 – When in Rome

by Nick MacKinnon

Published May 21 2017 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta