This post walks through monkey patching the Integer class to add a to_roman method that converts an integer to a Roman numeral. See the Wikipedia page for more information about Roman numerals. Pay close attention to the special Roman numeral treatment of certain numbers – for example, 40 is written as XL, not XXXX.

The code for this post is in this GitHub repository.

Monkey patching the Integer class means reopening the class to add more methods – fun! Start by defining a private roman_mapping method that maps integers (including the exception cases) to the corresponding Roman numeral.

class Integer private def roman_mapping { 1000 => "M", 900 => "CM", 500 => "D", 400 => "CD", 100 => "C", 90 => "XC", 50 => "L", 40 => "XL", 10 => "X", 9 => "IX", 5 => "V", 4 => "IV", 1 => "I" } end end

To convert the integer to a Roman numeral, iterate over all the keys in the roman_mapping hash and divide the number by the keys. If the number is divisible by the current key in the iteration, append the roman numeral corresponding to the divisor to the result. After each iteration, the number is updated to equal the remainder from the division.

Let’s use 152 as a concrete example of how the algorithm will function. The result is initially set to the empty string. We iterate over all the keys in the roman_mapping hash until we locate a key that 152 is divisible by. 152 is not divisible by 1000, so we move to the next key. 152 is not divisible by 900, so we move to the next key. We keep going until we find that 152 is divisible by 100 one time, so we append a single “C” to the result. The remainder is 52, so the number variable is updated to 52. Continuing the iteration, we find 52 is divisible by 50, so “L” is appended to the result. The number variable to updated to be the remainder of the division, which is 2. Continuing the iteration, we find 2 is not divisible by 40, so we move to the next key. The rest of the keys are skipped until the last key, where 2 is found to be divisible by 1 two times, so two “I”s are appended to the result. The result is now the Roman numeral “CLII”.

class Integer def to_roman result = "" number = self roman_mapping.keys.each do |divisor| quotient, modulus = number.divmod(divisor) result << roman_mapping[divisor] * quotient number = modulus end result end private def roman_mapping { 1000 => "M", 900 => "CM", 500 => "D", 400 => "CD", 100 => "C", 90 => "XC", 50 => "L", 40 => "XL", 10 => "X", 9 => "IX", 5 => "V", 4 => "IV", 1 => "I" } end end

The to_roman method can also be computed recursively. 152.to_roman is equivalent to “C” + 52.to_roman, which is equivalent to “CL” + 2.to_roman, which is equivalent to “CLII”.

def to_roman(number = self, result = "") return result if number == 0 roman_mapping.keys.each do |divisor| quotient, modulus = number.divmod(divisor) result << roman_mapping[divisor] * quotient return to_roman(modulus, result) if quotient > 0 end end

In each recursive step, the updated result is tracked in the result argument and the number argument is reset to the modulus. When the quotient is greater than 0, the to_roman(modulus, result) expression is returned to exit the each loop. The recursion termination case (also referred to as the base case) is when the number passed in the argument is zero and prevents the function from calling itself infinitely.

The test suite should still be passing with this refactoring.

describe Integer do context "to_roman" do it "converts 152 to 'CLII'" do expect(152.to_roman).to eq "CLII" end it "converts an integer to a roman numeral" do expect(1904.to_roman).to eq "MCMIV" end it "converts a 4 to a 'IV'" do expect(4.to_roman).to eq "IV" end it "converts a 3 to a 'III'" do expect(3.to_roman).to eq "III" end it "converts 0 to ''" do expect(0.to_roman).to eq "" end it "converts 2013 to MMXIII" do expect(2013.to_roman).to eq "MMXIII" end end end

Pingback: Roman Numeral Converter with JavaScript and underscore.js | Ruby/Rails Programming