Converting an Integer to a Roman Numeral

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
Advertisements

One thought on “Converting an Integer to a Roman Numeral

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s