# Roman numerals look and say sequence

I was practicing question 1 of the 2020 british informatics olympiad past paper:

The Roman look-and-say description of a string (of Is, Vs, Xs, Ls, Cs, Ds and Ms) is made by taking each block of adjacent identical letters and replacing it with the number of occurrences of that letter, given in Roman numerals (*), followed by the letter itself. A block of adjacent identical letters is never broken into smaller pieces before describing it.

Write a program that reads in a Roman numeral representing a number between 1 and 3999 inclusive, followed by n (1 ≤ n ≤ 50). You should apply the Roman look-and-say description n times and then output the number of Is in the final description, followed by the number of Vs.

I wrote this python code to attempt to solve this:

ROMAN_NUMERALS = {
1000: "M",
900: "CM",
500: "D",
400: "DC",
100: "C",
90: "XC",
50: "L",
40: "XL",
10: "X",
9: "IX",
5: "V",
4: "IV",
1: "I"
}

def convert_to_roman_numeral(n):
s = ""
while n > 0:
for key, value in ROMAN_NUMERALS.items():
if n - key >= 0:
s += value
n -= key

break

return s

def get_look_and_say_string(initial_string):
output = ""

while initial_string != "":
for i in range(len(initial_string)):
if initial_string[i] != initial_string[0]:
output += convert_to_roman_numeral(i) + initial_string[i - 1]

initial_string = initial_string[i:]

break

elif len(initial_string) == i + 1:
output += convert_to_roman_numeral(i + 1) + initial_string[i]

return output

s, apply_times = input().split()

for i in range(int(apply_times)):
s = get_look_and_say_string(s)

print(s.count("I"), s.count("V"))


For example, given the input MMXX 1, it outputs 4 0.

(A list of test cases can be found in the mark scheme here)

I would be grateful to hear about any improvements that could be made to this code.

• The code requires that the order of dict entries in ROMAN_NUMERALS is preserved. This is true for CPython since 3.6 and is part of the standard since Python 3.7. This should be specified explicitly or, as you don't use ROMAN_NUMERALS as dict but only as sequence, you could instead use a list or tuple of tuples (key, value) to avoid any possible problems. Commented Jan 2 at 14:55

Michael Butscher is correct to suggest that you should not be using a dictionary; just use a tuple of tuples. Otherwise, for a light refactor:

Replace your incremental string concatenation with ''.join(generator) style, which performs better under some scenarios (though you will want to measure this, and I haven't).

Replace for i in range(len(initial_string)): with a call to enumerate so that you get both the current symbol and its index.

Your elif len(initial_string) == i + 1: is a smell, because it's written to execute at the end of a loop - so just... move it out of the loop, under an else.

Separate an outer input(); print() function from a testable, non-console function; and write unit tests.

"""
"""

from typing import Iterator

ROMAN_NUMERALS = (
(1000, 'M'),
(900, 'CM'),
(500, 'D'),
(400, 'DC'),
(100, 'C'),
(90, 'XC'),
(50, 'L'),
(40, 'XL'),
(10, 'X'),
(9, 'IX'),
(5, 'V'),
(4, 'IV'),
(1, 'I'),
)

def convert_to_roman_numeral(n: int) -> Iterator[str]:
while n > 0:
for increment, symbol in ROMAN_NUMERALS:
new_n = n - increment
if new_n >= 0:
yield symbol
n = new_n
break

def get_look_and_say_string(initial_string: str) -> Iterator[str]:
while initial_string != '':
for i, str_i in enumerate(initial_string):
if str_i != initial_string[0]:
yield from convert_to_roman_numeral(i)
yield initial_string[i - 1]
initial_string = initial_string[i:]
break
else:
yield from convert_to_roman_numeral(len(initial_string))
yield initial_string[-1]
return

def problem(input_str: str) -> tuple[int, int]:
s, apply_times = input_str.split()
for _ in range(int(apply_times)):
s = ''.join(get_look_and_say_string(s))
return s.count('I'), s.count('V')

def test_op() -> None:
assert problem('MMXX 1') == (4, 0)

def test_official() -> None:
assert problem('MMXX 3') == (6, 2)
assert problem('C 1') == (1, 0)
assert problem('V 1') == (1, 1)
assert problem('III 2') == (2, 1)
assert problem('I 7') == (6, 2)
assert problem('MMXX 8') == (30, 12)
assert problem('II 20') == (101, 37)
assert problem('IV 20') == (121, 46)
assert problem('MDCLX 30') == (1795, 695)
assert problem('M 50') == (2858, 1103)
assert problem('V 50') == (2858, 1104)
assert problem('MMDCCCLXXXVIII 50') == (19013, 7333)

def main() -> None:
i, v = problem(input())
print(i, v)

if __name__ == '__main__':
test_op()
test_official()
# main()


## Logarithmic lookup

Your inner convert_to_roman_numeral should probably be changed so that it does a bisection search to get digits:

import bisect
from typing import Iterator

ROMAN_VALUES = (
1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000,
)

ROMAN_SYMBOLS = (
'I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'DC', 'D', 'CM', 'M',
)

def convert_to_roman_numeral(n: int) -> Iterator[str]:
hi = len(ROMAN_VALUES)
while n > 0:
i_low = bisect.bisect_right(a=ROMAN_VALUES, x=n, hi=hi) - 1
value = ROMAN_VALUES[i_low]
repeat = n // value
yield ROMAN_SYMBOLS[i_low] * repeat
n -= value * repeat
hi = i_low


## Direct logarithmic bound

You can fairly straightforwardly prove that for some n input to convert_to_roman_numeral, the index i into the ROMAN arrays is bounded by

$$\lceil 4 \log_{10} \frac n 4 \rceil \le i \le \lfloor 4 \log_{10} n \rfloor$$

To demonstrate, here are values from 10 through 100 and their index bounds:

From this, you can write an alternative convert_to_roman_numeral that starts on a bound and loops linearly through a very short (1-2) sequence of values to find the target. Whereas in theory this is O(1) compared to bisection's O(log(n)), it still performs slightly better than this; to compare:

import bisect
import math
import timeit
from typing import Iterator

import numpy as np
import pandas as pd
import seaborn
from matplotlib import pyplot as plt

ROMAN_NUMERALS_DICT = {
1000: "M",
900: "CM",
500: "D",
400: "DC",
100: "C",
90: "XC",
50: "L",
40: "XL",
10: "X",
9: "IX",
5: "V",
4: "IV",
1: "I"
}
def convert_roman_op(n):
s = ""
while n > 0:
for key, value in ROMAN_NUMERALS_DICT.items():
if n - key >= 0:
s += value
n -= key

break
return s

ROMAN_NUMERALS_TUPLE = (
(1000, 'M'),
(900, 'CM'),
(500, 'D'),
(400, 'DC'),
(100, 'C'),
(90, 'XC'),
(50, 'L'),
(40, 'XL'),
(10, 'X'),
(9, 'IX'),
(5, 'V'),
(4, 'IV'),
(1, 'I'),
)
def convert_roman_inner(n: int) -> Iterator[str]:
while n > 0:
for increment, symbol in ROMAN_NUMERALS_TUPLE:
new_n = n - increment
if new_n >= 0:
yield symbol
n = new_n
break
def convert_roman_gen(n: int) -> str:
return ''.join(convert_roman_inner(n))

ROMAN_VALUES = (
1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000,
)

ROMAN_SYMBOLS = (
'I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'DC', 'D', 'CM', 'M',
)
def convert_roman_inner_bisect(n: int) -> Iterator[str]:
hi = len(ROMAN_VALUES)
while n > 0:
i_low = bisect.bisect_right(a=ROMAN_VALUES, x=n, hi=hi) - 1
value = ROMAN_VALUES[i_low]
repeat = n // value
yield ROMAN_SYMBOLS[i_low] * repeat
n -= value * repeat
hi = i_low
def convert_roman_bisect(n: int) -> str:
return ''.join(convert_roman_inner_bisect(n))

def convert_roman_inner_log(n: int) -> Iterator[str]:
max_index = len(ROMAN_VALUES) - 1
while n > 0:
top = min(max_index, int(4*math.log10(n)))
value = ROMAN_VALUES[top]
while value > n:
top -= 1
value = ROMAN_VALUES[top]
repeat = n // value
yield ROMAN_SYMBOLS[top] * repeat
n -= value * repeat
def convert_roman_log(n: int) -> str:
return ''.join(convert_roman_inner_log(n))

methods = (
convert_roman_op,
convert_roman_gen,
convert_roman_bisect,
convert_roman_log,
)

def benchmark() -> None:
results = []

for size in (
10**np.linspace(0, 5, 101)
).astype(int):
reps = max(1, 100 // size)
ref = None

for method in methods:
def run() -> None:
nonlocal ref
output = method(size)
if ref is None:
ref = output
else:
assert ref == output
for _ in range(reps):
t = timeit.timeit(stmt=run, number=1)
results.append((size, method.__name__, t))
df = pd.DataFrame(
data=results,
columns=['size', 'method', 'dur'],
)

fig, ax = plt.subplots()
ax: plt.Axes
seaborn.lineplot(ax=ax, data=df, x='size', y='dur', hue='method')
ax.set_xscale('log')
ax.set_yscale('log')
plt.show()

if __name__ == '__main__':
benchmark()


## Iterating in look-and-say

AJNeufeld has an excellent suggestion to use itertools (or more_itertools which I don't demonstrate). It both cleans up and speeds up your main loop.

"""
"""

import bisect
import itertools
import time
from typing import Iterator

ROMAN_VALUES = (
1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000,
)

ROMAN_SYMBOLS = (
'I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'DC', 'D', 'CM', 'M',
)

def convert_to_roman_numeral(n: int) -> Iterator[str]:
hi = len(ROMAN_VALUES)
while n > 0:
i_low = bisect.bisect_right(a=ROMAN_VALUES, x=n, hi=hi) - 1
value = ROMAN_VALUES[i_low]
repeat = n // value
yield ROMAN_SYMBOLS[i_low] * repeat
n -= value * repeat
hi = i_low

def get_look_and_say_op(initial_string):
output = ""

while initial_string != "":
for i in range(len(initial_string)):
if initial_string[i] != initial_string[0]:
output += ''.join(convert_to_roman_numeral(i)) + initial_string[i - 1]

initial_string = initial_string[i:]

break

elif len(initial_string) == i + 1:
output += ''.join(convert_to_roman_numeral(i + 1)) + initial_string[i]

return output

def problem_op(input_str):
s, apply_times = input_str.split()
for _ in range(int(apply_times)):
s = get_look_and_say_op(s)
return s.count('I'), s.count('V')

def get_look_and_say_gen(initial_string: str) -> Iterator[str]:
while initial_string != '':
for i, str_i in enumerate(initial_string):
if str_i != initial_string[0]:
yield from convert_to_roman_numeral(i)
yield initial_string[i - 1]
initial_string = initial_string[i:]
break
else:
yield from convert_to_roman_numeral(len(initial_string))
yield initial_string[-1]
return

def problem_gen(input_str: str) -> tuple[int, int]:
s, apply_times = input_str.split()
for _ in range(int(apply_times)):
s = ''.join(get_look_and_say_gen(s))
return s.count('I'), s.count('V')

def get_look_and_say_ajneufeld(initial_string: str) -> Iterator[str]:
for letter, repeats in (
(k, sum(1 for _ in g))
for k, g in itertools.groupby(initial_string)
):
yield from convert_to_roman_numeral(repeats)
yield letter

def problem_ajneufeld(input_str: str) -> tuple[int, int]:
s, apply_times = input_str.split()
for _ in range(int(apply_times)):
s = ''.join(get_look_and_say_ajneufeld(s))
return s.count('I'), s.count('V')

def benchmark() -> None:
largest_test_case = 'MMDCCCLXXXVIII 50'
for method in (
problem_op,
problem_gen,
problem_ajneufeld,
):
start = time.perf_counter()
result = method(largest_test_case)
end = time.perf_counter()
assert result == (19013, 7333)
print(method.__name__, end - start)

if __name__ == '__main__':
benchmark()

problem_op 0.12485683699924266
problem_gen 0.09267444600118324
problem_ajneufeld 0.0854689560001134

• I cringe when I see your get_look_and_say_string(initial_string) implementation. Use: for letter, repeats in more_itertools.run_length.encode(initial_string): yield from convert_to_roman_numeral(repeats) yield letter. Otherwise, superb answer. Commented Jan 3 at 21:33
• @AJNeufeld I appreciate that. I can only assume, however, that the Olympiad doesn't support third-party libraries. Commented Jan 3 at 22:50
• True, but the OP was only doing it “for practice”, so I thought it would be allowed. Since it is part of the standard library, itertools should be allowed: for letter, repeats in ((k, sum(1 for _ in g)) for k, g in itertools.groupby(iterable)): Commented Jan 4 at 3:43
• @AJNeufeld I like it! I've included it in a comparison. Commented Jan 4 at 16:21
• I feel like get_look_and_say_string would be greatly simplified by re.search(r'((.)\2*)',initial_string). Commented Jan 4 at 19:55