6
\$\begingroup\$

I've built a Roman numeral class in Python, and I want to know what can be improved in it. An assumption I'm making is that the initialization of an object will use valid Roman numerals (I, V, X, L, C, D, M).

class RomanNumeral:
    def __init__(self, roman_numeral=''):
        self.roman_numeral = roman_numeral.upper()
        self.value = 0  # arabic value
        self.simple_form = ''  # Least possible number of character equivalence of Roman numeral
        self.valid = False  # Is the Roman numeral valid
        self.arabs = []  # List of corresponding arabic numbers

        self.convert = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        self.reverse_convert = dict((v, k) for k, v in self.convert.items())
        self.reverse_convert.update({4: 'IV', 9: 'IX', 40: 'XL', 90: 'XC', 400: 'CD', 900: 'CM'})

        self.convert_arabs()
        self.convert_value()
        self.convert_simple()

    def __repr__(self):
        return self.roman_numeral

    def __str__(self):
        return f'{self.roman_numeral} : {self.value}'

    def convert_arabs(self):
        """
        Converts the roman numeral to a list of the corresponding arabic numbers for each roman numeral
        """
        self.arabs = []
        for i, num in enumerate(self.roman_numeral):
            if num == 'I' and i != len(self.roman_numeral) - 1:
                if self.roman_numeral[i+1] == 'V':
                    self.arabs.append(4)
                    continue
                elif self.roman_numeral[i+1] == 'X':
                    self.arabs.append(9)
                    continue

            if num == 'X' and i != len(self.roman_numeral) - 1:
                if self.roman_numeral[i+1] == 'L':
                    self.arabs.append(40)
                    continue
                elif self.roman_numeral[i+1] == 'C':
                    self.arabs.append(90)
                    continue

            if num == 'C' and i != len(self.roman_numeral) - 1:
                if self.roman_numeral[i+1] == 'D':
                    self.arabs.append(400)
                    continue
                elif self.roman_numeral[i+1] == 'M':
                    self.arabs.append(900)
                    continue

            if num == 'V' and i != 0 and self.roman_numeral[i-1] == 'I':
                continue

            if num == 'X' and i != 0 and self.roman_numeral[i-1] == 'I':
                continue

            if num == 'L' and i != 0 and self.roman_numeral[i-1] == 'X':
                continue

            if num == 'C' and i != 0 and self.roman_numeral[i-1] == 'X':
                continue

            if num == 'D' and i != 0 and self.roman_numeral[i-1] == 'C':
                continue

            if num == 'M' and i != 0 and self.roman_numeral[i-1] == 'C':
                continue

            self.arabs.append(self.convert[num])

    def is_valid(self):
        """
        Checks if the Roman Numeral is valid
        """
        desc_sort = self.arabs == sorted(self.arabs)[::-1]  # Numerals must be in descending order

        small_exceed = True  # Cannot have number of smaller values exceed X, C, or M
        if self.roman_numeral.count('I') > 9:
            small_exceed = False
        if self.roman_numeral.count('X') > 9:
            small_exceed = False
        if self.roman_numeral.count('C') > 9:
            small_exceed = False

        five_once = True  # Cannot have more than one V, L, D
        if self.roman_numeral.count('V') > 1:
            five_once = False
        if self.roman_numeral.count('L') > 1:
            five_once = False
        if self.roman_numeral.count('D') > 1:
            five_once = False

        return desc_sort and small_exceed and five_once

    def convert_value(self):
        """
        Convert the value of the roman numeral to the arabic number
        """
        self.value = sum(self.arabs)

    def convert_simple(self):
        """
        Converts the roman numeral to its simplest form, meaning the least number of characters
        """
        subtract_list = sorted(self.reverse_convert.keys())[::-1]
        simplel = []
        curr_val = self.value
        i = 0
        while curr_val > 0:
            if curr_val - subtract_list[i] >= 0:
                simplel.append(subtract_list[i])
                curr_val -= subtract_list[i]
            else:
                i = (i + 1) % len(subtract_list)  # Go back to beginning

        self.simple_form = ''.join(self.reverse_convert[i] for i in simplel)  # make into simplest form
\$\endgroup\$
7
\$\begingroup\$

I do not really know how you plan to use your RomanNumeral object. From what's in the constructor, I guess you'd use it to convert a string corresponding to a numeral into a integer.

By doing so, you define multiple attributes and call multiple internal functions.

I am convinced some things could be re-organised:

  • self.convert = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000} could be changed into a global constant at the module top-level ROMAN_VALUES = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}.

  • convert_arabs() sets and fill a self.arabs attribute. I think it would make sense for the method to return the array and pass it directly to convert_value(self, arab_number_lst) (and to get rid of the self.arabs member).

  • then maybe we can get rid of convert_value altogether to write something like: self.value = sum(self.convert_arabs()).

  • then we realise that things could be even easier if convert_arabs was to return an integer directly. To do so, we'd just need to remplace my_arab_array.append(number) with my_arab_value += number everywhere.

  • then, the convert_arabs only uses the roman_numeral member to return an integer. It would be just as easy to move this out of the class and make this a function on its own taking the roman string as a parameter: def convert_roman_to_int(roman). This function has a clear purpose, converting roman string to int and is easier to think about. Let's make this function more beautiful:

Improving convert_roman_to_int

The first main improvement is to reduce the amount of duplicated logic.

Your function performs a lot of boundary checking. You could reorganise your code to remove a lot of it:

for i, num in enumerate(roman):
    if i != len(roman) - 1:
        next_ = roman[i+1]
        f num == 'I':
            if next_ == 'V':
                self.arabs.append(4)
                continue
            elif next_ == 'X':
                self.arabs.append(9)
                continue
        if num == 'X':
            if next_ == 'L':
                self.arabs.append(40)
                continue
            elif next_ == 'C':
                self.arabs.append(90)
                continue
        if num == 'C':
            if next_ == 'D':
                self.arabs.append(400)
                continue
            elif next_ == 'M':
                self.arabs.append(900)
                continue
        ...

Similarly, a block could start with if i != 0:.

The logic just aboves correspond to a more generic situation: if the current value is smaller than the next one, we actually want to substract the smaller from the bigger. This can be written:

for i, num in enumerate(roman):
    curr_val = ROMAN_VALUES[num]
    if i != len(roman) - 1:
        next_ = roman[i+1]
        next_val = ROMAN_VALUES.get(next_, None)
        if next_val and curr_val < next_val:
            value += next_val - curr_val
            continue

The other case corresponds to a situation I had more troubles to generalise. It can be rewritten as:

    if i != 0:
        prev = roman[i-1]
        if (num, prev) in set([('V', 'I'), ('X', 'I'), ('L', 'X'), ('C', 'X'), ('D', 'C'), ('M', 'C')]):
            continue

but I guess it can be improved.

At this stage, we have the following function:

def convert_roman_to_int(roman):
    value = 0
    for i, num in enumerate(roman):
        curr_val = ROMAN_VALUES[num]
        if i != len(roman) - 1:
            next_ = roman[i+1]
            next_val = ROMAN_VALUES.get(next_, None)
            if next_val and curr_val < next_val:
                value += next_val - curr_val
                continue

        if i != 0:
            prev = roman[i-1]
            if (num, prev) in set([('V', 'I'), ('X', 'I'), ('L', 'X'), ('C', 'X'), ('D', 'C'), ('M', 'C')]):
                continue

        value += curr_val
    return value

Similary, is_valid could be extracted out and made into a clear function with a well defined behavior. Also convert_roman_to_int could call it before doing anything else and raise an exception.

Improving is_valid_roman(roman)

You are iterating over the input multiple times to count the different characters one by one. A better approach would be to iterate over it once and count all the characters in one go. Fortunately, this task is really easy with the collections.Counter class.

def is_valid_roman(roman):
    """
    Checks if the Roman Numeral is valid
    """
    # TODO desc_sort = self.arabs == sorted(self.arabs)[::-1]  # Numerals must be in descending order
    count = collections.Counter(roman)
    small_exceed = True  # Cannot have number of smaller values exceed X, C, or M
    if count['I'] > 9:
        small_exceed = False
    if count['X'] > 9:
        small_exceed = False
    if count['C'] > 9:
        small_exceed = False

    five_once = True  # Cannot have more than one V, L, D
    if count['V'] > 1:
        five_once = False
    if count['L'] > 1:
        five_once = False
    if count['D'] > 1:
        five_once = False

    return small_exceed and five_once

Then, you could ensure that when something going wrong is found, you do not keep on checking. You could use elif, you could use early return, etc. My favorite way to do so is to use a single expression and rely on short-circuit evaluation.

count = collections.Counter(roman)
return (count['I'] <= 9 and # Cannot have number of smaller values exceed X, C, or M
        count['X'] <= 9 and
        count['C'] <= 9 and
        count['V'] <= 1 and # Cannot have more than one V, L, D
        count['L'] <= 1 and
        count['D'] <= 1)

This looks good but there is still a major property that we probably want to check: there should be nothing but 'IVXLCDM'. We could add a condition and all(c in 'IVXLCDM' for c in count).

count = collections.Counter(roman)
return (count['I'] <= 9 and # Cannot have number of smaller values exceed X, C, or M
        count['X'] <= 9 and
        count['C'] <= 9 and
        count['V'] <= 1 and # Cannot have more than one V, L, D
        count['L'] <= 1 and
        count['D'] <= 1 and
        all(c in 'IXCVLDM' for c in count))

However, a funnier option could be to define a dictionary mapping each character to the number of time it is allowed (assuming 0 is not in the dict). That dictionnary could be defined either in the function or at the module level, close to ROMAN_VALUES.

MAX_NUMBER_FOR_CHAR = { 'I': 9, 'X': 9, 'C': 9, 'V': 1, 'L': 1, 'D': 1, 'M': None }

def is_valid_roman(roman):
    """
    Checks if the Roman Numeral is valid
    """
    # TODO desc_sort = self.arabs == sorted(self.arabs)[::-1]  # Numerals must be in descending order
    count = collections.Counter(roman)
    for c, nb in count.items():
        allowed = MAX_NUMBER_FOR_CHAR.get(c, 0)  # assume 0 if not found
        if allowed is not None and allowed < nb:
            return False
    return True

Then, following what we've done for other functions, it seems pretty obvious that convert_simple is begging to be a function:

def integer_to_roman(n):
    """
    Converts the roman numeral to its simplest form, meaning the least number of characters
    """
    reverse_convert = dict((v, k) for k, v in ROMAN_VALUES.items())
    reverse_convert.update({4: 'IV', 9: 'IX', 40: 'XL', 90: 'XC', 400: 'CD', 900: 'CM'})
    subtract_list = sorted(reverse_convert.keys())[::-1]
    simplel = []
    i = 0
    while n > 0:
        if n - subtract_list[i] >= 0:
            simplel.append(subtract_list[i])
            n -= subtract_list[i]
        else:
            i = (i + 1) % len(subtract_list)  # Go back to beginning

    return ''.join(reverse_convert[i] for i in simplel)  # make into simplest form

After building a list of values, you iterate in a very unconventional way to decide how many times each values is taken. I think it can be writen in a clearer way:

subtract_list = sorted(reverse_convert.keys())[::-1]
simplel = []
for v in subtract_list:
    while n >= v:
        simplel.append(v)
        n -= v
return ''.join(reverse_convert[i] for i in simplel)  # make into simplest form

You could also perform the conversion with reverse_convert as you go:

subtract_list = sorted(reverse_convert.keys())[::-1]
simplel = []
for v in subtract_list:
    while n >= v:
        simplel.append(reverse_convert[v])
        n -= v
return ''.join(simplel) 

Then you can actually be smarter by considering how many times you'll enter the while loop. This can be decided with a simple division:

for v in subtract_list:
    q = n // v
    simplel.extend(q * reverse_convert[v])
    n -= q * v

Then, it is interesting to note that the n -= q * v is actually the same thing as n %= v : you check what is left after the division. The awesome thing is that Python has a function to get you both the quotient and reminder of a division so that the code can be written:

subtract_list = sorted(reverse_convert.keys())[::-1]
simplel = []
for v in subtract_list:
    q, n = divmod(n, v)
    simplel.extend(q * reverse_convert[v])
return ''.join(simplel)

Tests

Now that I have a simple function converting numbers to roman and roman to numbers, I can write a simple test to ensure everything is fine.

for i in range(10000):
    s = integer_to_roman(i)
    i2 = convert_roman_to_int(s)
    # print(i, s, i2)
    assert i == i2

In order to to this properly, you could/should a proper test framework. Also , it would be worth adding tests for invalid inputs...

Back to integer_to_roman

Now that I have tests to protect me, I can mess with the function a bit more. It looks like the bit I did not get can be replaced by:

    if i != 0:
        prev = roman[i-1]
        prev_val = ROMAN_VALUES.get(prev, None)
        if prev_val < curr_val:
            continue

(It is not stricly speaking equivalent but on valid inputs, it does not make a difference).

Then, I realised that this was trying not to add a value because it was handled already. It is actually much easier to handle it only partially at first so that you do not need to check if you need to add the number or not:

def convert_roman_to_int(roman):
    value = 0
    for i, num in enumerate(roman):
        curr_val = ROMAN_VALUES[num]
        if i != len(roman) - 1:
            next_ = roman[i+1]
            next_val = ROMAN_VALUES.get(next_, None)
            if next_val and curr_val < next_val:
                value -= curr_val
                continue
        value += curr_val
    return value

Then an idea could be to convert all the values once at the beginning and then iterate on the list of converted values:

def convert_roman_to_int(roman):
    value = 0
    values = [ROMAN_VALUES[num] for num in roman]
    for i, val in enumerate(values):
        if i != len(roman) - 1:
            next_val = values[i+1]
            if val < next_val:
                value -= val
                continue
        value += val
    return value

You could also use some recipes to iterate over consecutive pairs. Then, you'd get rid of the boundary check altogether:

def convert_roman_to_int(roman):
    value = 0
    values = [ROMAN_VALUES[num] for num in roman]
    for val, next_val in zip(values, values[1:] + [0]):
        if val < next_val:
            value -= val
        else:
            value += val
    return value

Ultimately, this could be written using sum and a generator expression but this may be going too far:

def convert_roman_to_int(roman):
    values = [ROMAN_VALUES[num] for num in roman]
    return sum(-val if val < next_val else val
               for val, next_val in zip(values, values[1:] + [0]))

Also, for the last steps, I should have used itertools.zip_longest because it has a convenient fillvalue argument.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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