4
\$\begingroup\$

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.

\$\endgroup\$
1
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 2 at 14:55

1 Answer 1

5
\$\begingroup\$

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:

Add type hints to your function signatures.

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.

"""
https://www.olympiad.org.uk/papers/2020/bio/bio20-marks.pdf#page=2
"""

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:

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()

benchmark roman

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.

"""
https://www.olympiad.org.uk/papers/2020/bio/bio20-marks.pdf#page=2
"""

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
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – AJNeufeld
    Commented Jan 3 at 21:33
  • \$\begingroup\$ @AJNeufeld I appreciate that. I can only assume, however, that the Olympiad doesn't support third-party libraries. \$\endgroup\$
    – Reinderien
    Commented Jan 3 at 22:50
  • 1
    \$\begingroup\$ 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)): \$\endgroup\$
    – AJNeufeld
    Commented Jan 4 at 3:43
  • \$\begingroup\$ @AJNeufeld I like it! I've included it in a comparison. \$\endgroup\$
    – Reinderien
    Commented Jan 4 at 16:21
  • \$\begingroup\$ I feel like get_look_and_say_string would be greatly simplified by re.search(r'((.)\2*)',initial_string). \$\endgroup\$
    – Teepeemm
    Commented Jan 4 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.