7
\$\begingroup\$

For an interview question I made a roman to integer converter:

def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        mapping = {"I": 1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000}
        numeral_list = list(s)

        num_list = [[mapping[i], -1] for i in numeral_list]
        count = 0
        i = 0
        while(i < len(num_list) - 1):
            if num_list[i] < num_list[i + 1]:
                count += num_list[i + 1][0] - num_list[i][0]
                num_list[i+1][1] = 1
                num_list[i][1] = 1
                i += 2
            else:
                count += num_list[i][0]
                num_list[i][1] = 1
                i += 1
        if num_list[-1][1] == -1:
            count += num_list[-1][0]
        return count

As you can see I sometimes miss the last digit because I didn't want to get an index error. To avoid that I added an extra attribute that would check if the last element was checked or not (in cases where s[len(s)-2] < s[len(s)-1], s[len(s)-1] is checked, but if s[len(s)-2] > s[len(s)-1] then s[len(s)-1] is not checked.

Having an extra check and using extra space just for one element is highly erroneous. Where am I going wrong in my logic?

\$\endgroup\$
4
\$\begingroup\$

You should stick to variable names according to the python style guide, PEP8. This means using lower_case for variables and functions.

You could also use more descriptive names, for example roman instead of s.

The complicated checking you do with having 2-tuples and deciding on that can be circumvented by iterating over zip(numbers, numbers[1:]) to have both the number and the following number available at the same time. Still, we need to manually add the last digit at the end. Similar to the answer to this question I would propose to use something like:

def roman_to_int(roman):
    """Convert from Roman numerals to an integer."""
    values = {'M': 1000, 'D': 500, 'C': 100, 'L': 50, 
              'X': 10, 'V': 5, 'I': 1}
    numbers = [values[char] for char in roman]
    total = 0
    for num1, num2 in zip(numbers, numbers[1:]):
        if num1 >= num2:
            total += num1
        else:
            total -= num1
    return total + num2
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the answer. This function throws an exception with 1 char strings, here's a quick fix. if len(numbers) > 1: for num1, num2 in zip(numbers, numbers[1:]): .... else: return numbers[0] \$\endgroup\$ – Yair Beer Sep 27 '17 at 9:28
2
\$\begingroup\$

To extend @Graipher's answer, I would use the pairwise itertool recipe instead of duplicating the array.

I would also get the last number from the original string rather than rely on the for loop to fetch it. This also means that the original string should contain at least one letter, which you may need to take care of.

Lastly, there is no need to recreate the conversion table each time the function is called, better extract it as a constant:

from itertools import tee


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


def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)


def roman_to_int(roman):
    """Convert from Roman numerals to an integer"""

    if not roman:
        return 0

    last_number = ROMAN_TABLE[roman[-1]]
    total = sum(
        number if number >= next_number else -number
        for number, next_number in pairwise(
            ROMAN_TABLE[char] for char in roman
        )
    )
    return total + last_number
\$\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.