Converting Roman numerals to integers

Question

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a Roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:
Input: "III"
Output: 3

Example 2:
Input: "IV"
Output: 4

Example 3:
Input: "IX"
Output: 9

Example 4:
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

My function in Python to accomplish this task:

def romanToInt(self, s: str) -> int:
    checks = {"IV":-2,"IX":-2, "XL":-20, "XC":-20, "CD":-200, "CM":-200}
    values = {"I":1, "V":5,"X":10, "L":50,"C":100, "D":500,"M":1000}
    sum = 0

    for i in s:
        sum += values[i]

    for i in range(len(s) - 1):
        combine = str(s[i] + s[i + 1])
        if combine in checks:
            sum += checks[combine]

    return sum

I'd love to get some feedback. I'm not sure if I should change the variable name from sum to something else, as I'm overwriting a python function. However, I don't use that function inside of my function, so does it matter?

Additionally, should I be converting the string to a list? Strings are immutable and I'm pulling apart and creating a new string with the combine variable, so I'm not sure if that's something I should be concerned about with regards to time complexity.

Answer 1

Don't use sum as a variable. Especially because you want to use it with your approach!

sum = 0
for i in s:
    sum += values[i]

could become:

number = sum(values[i] for i in s)

---

s[i] is a string. s[i] + s[i+1] is a string. There is no need to use str() to convert what is already a string to a string. But s[i:i+2] is easier still.

---

With 3999 as the maximum, the longest Roman numeral string would be 15 characters ("MMMDCCCLXXXVIII"). Your last loop would iterate 14 times, taking two letter substrings.

There are only 6 two letter negative combinations. You could instead search for those 6 patterns:

number += sum(value for key, value in checks.items() if key in s)

This is 6 \$O(N)\$ substring searches, instead of N \$O(1)\$ lookups. Time complexity is unchanged, but this latter approach may be faster for many strings. (It certainly will be slower for 1 character strings!)

---

checks and values are constants. You should not recreate them every time you call the function. Make them global, initialized once.

---

PEP-8:

Variables and functions should be snake_case, not camelCase, so romanToInt should be roman_to_int.

s is too short to be descriptive. roman might be better.

---

self? This should be a function, not a method in a class. If it is in a class, then use @staticmethod, since it doesn't use self (or cls) at all.

---

Result:

SUBTRACTIVE = {"IV": 2, "IX": 2, "XL": 20, "XC": 20, "CD": 200, "CM": 200}
VALUES = {"I": 1, "V": 5, "X":10, "L": 50, "C": 100, "D": 500, "M": 1000}

def roman_to_int(roman: str) -> int:

    number = sum(VALUES[ch] for ch in roman)
    number -= sum(val for key, val in SUBTRACTIVE.items() if key in roman)

    return number

Although I'm not a fan of CHECKS, but a better concise name is escaping me. Now using SUBTRACTIVE as suggested by JollyJoker.

---

Speed Tests

Execution time for parsing all Roman numerals from I to MMMCMXCIX, repeated 100 times, in seconds:

somya_agrawal   1.288
ajneufeld       0.737
jg              1.521
jg2             1.324
maarten_bodewes 2.186
maarten_bodewes 1.653 (decode only)

It wasn't clear whether J.G. was using local variable or global variables for checks and values in their solution, so I coded it both ways.

Speed Test Code

import time

def create_roman(value):
    roman = ""
    for letters, val in (("M", 1000),
                         ("CM", 900), ("D", 500), ("CD", 400), ("C", 100),
                         ("XC", 90), ("L", 50), ("XL", 40), ("X", 10),
                         ("IX", 9), ("V", 5), ("IV", 4), ("I", 1)):
        while value >= val:
            roman += letters
            value -= val
    return roman

ROMAN_NUMERALS = [create_roman(value) for value in range(1, 4000)]

def somya_agrawal(s: str) -> int:
    checks = {"IV":-2,"IX":-2, "XL":-20, "XC":-20, "CD":-200, "CM":-200}
    values = {"I":1, "V":5,"X":10, "L":50,"C":100, "D":500,"M":1000}
    sum = 0

    for i in s:
        sum += values[i]

    for i in range(len(s) - 1):
        combine = str(s[i] + s[i + 1])
        if combine in checks:
            sum += checks[combine]

    return sum

CHECKS = {"IV": 2, "IX": 2, "XL": 20, "XC": 20, "CD": 200, "CM": 200}
VALUES = {"I": 1, "V": 5, "X":10, "L": 50, "C": 100, "D": 500, "M": 1000}

def ajneufeld(roman: str) -> int:
    number = sum(VALUES[ch] for ch in roman)
    number -= sum(val for key, val in CHECKS.items() if key in roman)

    return number

def jg(s: str) -> int:
    checks = {"IV":-2,"IX":-2, "XL":-20, "XC":-20, "CD":-200, "CM":-200}
    values = {"I":1, "V":5,"X":10, "L":50,"C":100, "D":500,"M":1000}

    result = sum(values[i] for i in s)
    result += sum(checks.get(s[i : i + 2], 0) for i in range(len(s) - 1))

    return result

checks = {"IV":-2,"IX":-2, "XL":-20, "XC":-20, "CD":-200, "CM":-200}
values = {"I":1, "V":5,"X":10, "L":50,"C":100, "D":500,"M":1000}

def jg2(s: str) -> int:

    result = sum(values[i] for i in s)
    result += sum(checks.get(s[i : i + 2], 0) for i in range(len(s) - 1))

    return result

def time_test(f):
    start = time.perf_counter()
    for _ in range(100):
        for roman in ROMAN_NUMERALS:
            f(roman)
    end = time.perf_counter()
    print(f"{f.__name__:15} {end-start:5.3f}")

if __name__ == '__main__':
    for f in (somya_agrawal, ajneufeld, jg, jg2):
        time_test(f)

Answer 2

Try to use more Python idioms; in particular, make your code more declarative rather than imperative. You can rewrite everything after your dictionary definitions with

return sum(values[i] for i in s)+sum(checks.get(s[i:i+2], 0) for i in range(len(s)-1))

or, which is more PEP-8 friendly,

result = sum(values[i] for i in s)
result += sum(checks.get(s[i : i + 2], 0) for i in range(len(s) - 1))
return result

Let me explain:

• For each sum, I don't need [] around the argument, because without them I'm summing a generator instead of a list;
• If d is a dictionary, it's considered best practice to use d.get(k, v) to get d[k] if it exists, or v otherwise.

Your function also shouldn't have a self argument. If it must exist in a class, delete this argument and place an @staticmethod Python decorator above it. (Please don't confuse Python decorators with the decorator pattern.)

Having said all that, your algorithm is very clever, well done. I've coded the same problem myself before, but it never occurred to me to calculate the result assuming no subtractions were needed, then make the subtractions accordingly.

Answer 3

What I am entirely missing from your implementation is any correctness checks on the input of roman numerals. This makes it possible to reverse Roman literals, for instance, without any indication that they are invalid. Even if there are bad characters or lowercase characters the program will just crash. That's not any way to behave.

One little trick I used was to simply subtract any value if it was smaller than the next one. That will also ignore invalid Roman numerals. However, I did one neat trick afterwards: I simply generated the roman numerals back again from the number and validated that it matched with the original input. That way you have encoding / decoding and a fool proof validation. There is only one canonical encoding after all (unless you include things like IIII for 4 on clocks etc.).

---

For instance:

nums = "IVXLCDM"

class RomanNumerals:

    def encode(this, value):
        if (value < 1 or value > 3999):
            raise ValueError("Value should be between 1 and 3999 inclusive")

        roman = ""

        x = value
        numoff = 0
        while x > 0:
            d = x % 10
            if d < 4:
                roman = nums[numoff] * d + roman
            elif d == 4:
                roman = nums[numoff] + nums[numoff + 1] + roman
            elif d < 9:
                roman = nums[numoff] * (d - 5) + roman
                roman = nums[numoff + 1] + roman
            else:
                roman = nums[numoff] + nums[numoff + 2] + roman
            x = x // 10
            numoff += 2
        return roman

    def decode(this, roman):
        if len(roman) == 0:
            raise ValueError("Roman encoded value is empty")

        res = 0

        tail = False
        for c in roman:
            # raises ValueError if not found
            i = nums.index(c)

            # power of ten for each two, but multiply with 5 if we're in between
            cv = 10**(i // 2) * (1 if i % 2 == 0 else 5)

            if tail:
                # decrease if the next value is larger instead of smaller (e.g. IV instead of VI)
                if cv > lv:
                    res -= lv
                else:
                    res += lv
            else:
                tail = True
            lv = cv
        res += lv

        # check for correctness the way the Roman numeral is formatted doing the reverse
        if roman != this.encode(res):
            raise ValueError("Roman encoding is not canonical")

        return res

Note that this is for demonstrating the idea only (and for me to practice some Python).