Project Euler Solution 89: Roman Numerals

🧔🏻

🗓️

📂 Code & Zahlen

Here we will look at Project Euler Problem 89 where we have to deal with Roman numerals.

The problem is pretty straightforward, we're given a list of Roman numerals in some inefficient style of writing and shall rewrite them in the most compact way. The end result is the number of characters saved.

This one is about many rules, so tests are good. Let's start with the test for the parser:

def test_parse_roman_numeral() -> None:
    cases = {
        "IV": 4,
        "IIII": 4,
        "XIX": 19,
        "XXXXIIIIIIIII": 49,
        "XXXXVIIII": 49,
        "XXXXIX": 49,
        "XLIX": 49,
    }
    for roman, arabic in cases.items():
        assert parse_roman_numeral(roman) == arabic

Then we write the actual function:

values = {"M": 1000, "D": 500, "C": 100, "L": 50, "X": 10, "V": 5, "I": 1}


def parse_roman_numeral(numeral: str) -> int:
    value = 0
    last = 0
    for n in reversed(numeral):
        n = values[n]
        if last > n:
            value -= n
        else:
            value += n
        last = n
    return value

My approach here is to parse in reverse and then subtract or add the current number based on the previous one.

Next we need to generate roman numerals. Let's just write a test with the parser that we already have:

def test_two_way() -> None:
    for i in range(5_000):
        roman = write_as_roman(i)
        assert parse_roman_numeral(roman) == i

Then we can implement this function:

numerals = {
    1: "I",
    2: "II",
    3: "III",
    4: "IV",
    5: "V",
    6: "VI",
    7: "VII",
    8: "VIII",
    9: "IX",
    10: "X",
    20: "XX",
    30: "XXX",
    40: "XL",
    50: "L",
    60: "LX",
    70: "LXX",
    80: "LXXX",
    90: "XC",
    100: "C",
    200: "CC",
    300: "CCC",
    400: "CD",
    500: "D",
    600: "DC",
    700: "DCC",
    800: "DCCC",
    900: "CM",
    1000: "M",
}


def write_as_roman(number: int) -> str:
    bits = []
    while number:
        next_value, next_numeral = max(
            (value, numeral) for value, numeral in numerals.items() if value <= number
        )
        number -= next_value
        bits.append(next_numeral)
    return "".join(bits)

Nothing fancy there. I just take the remainder of the number and write that using the largest possible characters. I've given an explicit list because I didn't want to program all the logic. This seemed faster.

The solution itself then just uses both parts and computes the difference in length:

def solution() -> int:
    characters_saved = 0
    with open("data/0089_roman.txt") as f:
        for line in f:
            long = line.strip()
            short = write_as_roman(parse_roman_numeral(long))
            characters_saved += len(long) - len(short)
    return characters_saved

That runs in 17 ms, but performance or algorithm isn't really the point here. It is about implementing that logic correctly. And with test driven development it works well.