Conversion from/to roman numbers

Question

I wrote as an exercise in Test-Driven Development a piece of Python code that contains two functions:

• roman2dec(roman), that converts a roman number (string) into a decimal number (int)
• dec2roman(dec), that converts a decimal number (int) into a roman number (string)

I'd like to read your comments on this code, if there are bad practices, if you would sign it for shipping or if you'd change anything.

import re
import math

# Regular expression used to validate and parse Roman numbers
roman_re = re.compile("""^
   ([M]{0,9})   # thousands
   ([DCM]*)     # hundreds
   ([XLC]*)     # tens
   ([IVX]*)     # units
   $""", re.VERBOSE)

# This array contains valid groups of digits and encodes their values.
# The first row is for units, the second for tens and the third for
# hundreds. For example, the sixth element of the tens row yields the
# value 50, as the first is 0.
d2r_table = [
    ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'],
    ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'],
    ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']]


def roman2dec(roman):
    """Converts a roman number, encoded in a string, to a decimal number."""
    roman = roman.upper()
    match = roman_re.match(roman)

    if not match:
        raise ValueError

    thousands, hundreds, tens, units = match.groups()
    result = 1000 * len(thousands)
    result += d2r_table[2].index(hundreds) * 100
    result += d2r_table[1].index(tens) * 10
    result += d2r_table[0].index(units)

    return result


def dec2roman(dec):
"""Converts a positive decimal integer to a roman number."""
    if dec == 0:
        return ''

    digit = 0
    rem = dec
    result = ''

    # Length in digits of the number dec
    dec_len = int(math.ceil(math.log10(dec)) + 1)

    # Scan the number digit-by-digit, starting from the MSD (most-significant
    # digit)
    while dec_len > 0:
        # Let's take the current digit
        factor = 10 ** (dec_len - 1)
        digit = rem / factor

        # And remove it from the number
        rem = rem - digit * factor

        if dec_len >= 4:
            # Thousands
            result = result + digit * 'M'
        else:
            # Look in the look-up table
            result = result + d2r_table[dec_len - 1][digit]

        dec_len -= 1

    return result

EDIT: Here is the test suite for dec2roman:

class DecToRoman(unittest.TestCase):
    def testZeroIsEmpty(self):
        self.checkString(0, "")

    def testSingleDigits(self):
        self.checkString(1, "I")
        self.checkString(10, "X")
        self.checkString(50, "L")
        self.checkString(100, "C")
        self.checkString(500, "D")
        self.checkString(1000, "M")

    def testSimpleRepeats(self):
        self.checkString(1, "I")
        self.checkString(2, "II")
        self.checkString(3, "III")
        self.checkString(10, "X")
        self.checkString(20, "XX")
        self.checkString(30, "XXX")

    def testSubtraction(self):
        self.checkString(4, "IV")
        self.checkString(9, "IX")
        self.checkString(40, "XL")
        self.checkString(90, "XC")

    def testOther(self):
        self.checkString(89, "LXXXIX")
        self.checkString(145, "CXLV")
        self.checkString(691, "DCXCI")
        self.checkString(1983, "MCMLXXXIII")
        self.checkString(2412, "MMCDXII")
        self.checkString(3309, "MMMCCCIX")

    def checkString(self, decimal, expected_string):
        self.assertEqual(expected_string, new_dec2roman(decimal))

Answer 1

First of all you should document the fact that your code does not work with numbers above 9999.

Then I think your code will become a bit simpler, if you add a fourth row to your d2r_table for the thousands. To avoid repetition you can use a list comprehension:

d2r_table = [
    ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'],
    ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'],
    ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'],
    ['M' * i for i in xrange(0,10) ]]

This allows you to not treat the thousands as a special case. So instead of:

thousands, hundreds, tens, units = match.groups()
result = 1000 * len(thousands)
result += d2r_table[2].index(hundreds) * 100
result += d2r_table[1].index(tens) * 10
result += d2r_table[0].index(units)

you can write:

thousands, hundreds, tens, units = match.groups()
result =  d2r_table[3].index(thousands) * 1000
result += d2r_table[2].index(hundreds) * 100
result += d2r_table[1].index(tens) * 10
result += d2r_table[0].index(units)
return result

Now you can easily notice the common pattern here: For each number from 0 to 3 you're taking the ith row of d2r_table, calling index on it with the 3-ith element of groups as the argument, then multiplying it with 10**i and lastly summing the results. You can abstract the common pattern like this if you want:

def value_for_group(i):
    group = match.groups[3-i]
    return d2r_table[i].index(group) * 10**i

return sum(value_for_group(i) for i in xrange(0,4))

You can also replace the magic numbers 3 and 4, with something more meaningful:

num_rows = len(d2r_table)

def value_for_group(i):
    group = match.groups[num_rows - 1 - i]
    return d2r_table[i].index(group) * 10**i

return sum(value_for_group(i) for i in xrange(0, num_rows))

This way your code will work without modification if you ever change d2r_table to account for extended roman numerals.

---

In your dec2roman function you're using integer arithmetic to iterate over the digits of the number. I think it'd be easier and clearer to just convert the number to a string and iterate over the digits with a for loop. By reversing the d2r_table, you can use zip to iterate over the table and the digits in parallel without any index based loops. This way your dec2roman function would look like this:

result = ''
# Make digits four digits long so it has the same number of digits
# as d2r_table has rows, then convert each digit to an int
digits = [int(digit) for digit in "%04d" % dec]

for digit, d2r_row in zip(digits, reversed(d2r_table)):
    result += d2r_row[ digit ]

return result

You can also use join with a generator expression instead of updating result imperatively:

digits = [int(digit) for digit in "%04d" % dec]
table = reversed(d2r_table)
return ''.join( d2r_row[ digit ] for digit, d2r_row in zip(digits, table) )

Again you might also want to replace the 4 in %04d with len(d2r_table), so your code will automatically adapt to a longer d2r_table.