Skip to main content
added 1779 characters in body
Source Link

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).


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).

Source Link

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.).