I’ve been doing the Ruby katas, and last week, I completed the Roman numeral calculator, which tasks you with converting Arabic numbers to Roman numerals and vice versa. Upon completing the kata, I searched around for other answers. Imagine my surprise in finding this Rosetta Code example, which converts Arabic numbers to Roman in just a few lines of code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Symbols = { 1=>'I', 5=>'V', 10=>'X', 50=>'L', 100=>'C', 500=>'D', 1000=>'M' }
Subtractors = [ [1000, 100], [500, 100], [100, 10], [50, 10], [10, 1], [5, 1], [1, 0] ]
 
def roman(num)
  return Symbols[num]  if Symbols.has_key?(num)
  Subtractors.each do |cutPoint, subtractor| 
    return roman(cutPoint) + roman(num - cutPoint)      if num >  cutPoint
    return roman(subtractor) + roman(num + subtractor)  if num >= cutPoint - subtractor and num < cutPoint
  end
end
 
[1990, 2008, 1666].each do |i|
  puts "%4d => %s" % [i, roman(i)]
end

My answer was, let us say…not that efficient. So I set out to understand how the more efficient answer works.

All right. We start with a hash that matches up the standard associations (1=I, V=5, etc). We then pass these to the roman function below. The first line in the function delivers matches when a number exactly matches a symbol (i.e. x=10):

1

return Symbols[num]  if Symbols.has_key?(num)

This is actually how every Roman numeral gets assigned – when the function sees a number it has a letter for, i.e. 10=X, it assigns the correct letter. It’s easy to see how this works with numbers like 10, but most Roman numbers are compilations of several letters i.e. XV=10+5, 15. To complicate matters, certain numbers, like 4, are represented by placing a smaller number to the left of a larger number, indicating that the reader should subtract by the smaller number. For example, IV= 5-1, 4. The function deals with all this logic in 4 lines of code:

1
2
3
4

  Subtractors.each do |cutPoint, subtractor| 
    return roman(cutPoint) + roman(num - cutPoint)      if num >  cutPoint
    return roman(subtractor) + roman(num + subtractor)  if num >= cutPoint - subtractor and num < cutPoint
  end

It’s recursive as all getout. The code begins by iterating through the series of arrays nested in the Subtractors array. The function refers to the first element of each nested array as a “cutPoint”. The cutPoint represents the “normal” value (for example, 10). The second element indicates, referred to as the “subtractor”, is the amount that number would have to be reduced by if a “reducing” letter appeared to its left (for example IX= 10-1, 9). Essentially, the function iterates through the array, and begins doing calling itself on itself as soon as it finds a number smaller than the cutPoint. Let’s check it out with an example:

If I feed the number 11 into the function, this is what happens: The function sees that 11 isn’t in the Symbols, and goes on to the first line of the roman function. roman goes through its array of Subtractors, and finds that 11 is less than 10. It then does the following wizbang math:

1

  return roman(cutPoint) + roman(num - cutPoint)      if num >  cutPoint

By calling itself on itself, we get this: calling roman(cutPoint) will call the Roman numeral-assigning first line,

1

  return Symbols[num]  if Symbols.has_key?(num)

to look up the cutPoint, 10, in the Symbols hash. It will give us its value, X. We do this again when we want to add the I to the next line in the code,

1

   roman(num - cutPoint)

This calls the same function on 11-10, or 1. That gives us X+I, which is the correct Roman number value. Because the function keeps calling itself, and adding numerals, it also works for much larger numbers – i.e. 153 = CLIII. Most of our conversion is done with this line. So what’s up with the second line of code? We’re actually calling it every time, but it only runs when certain conditions are met:

1

   num >= cutPoint - subtractor and num < cutPoint

When do these conditions apply? Well, as luck would have it, only when we need to place a Roman numeral to the left. For example, the number 4 in roman numbers is IV. If we pass 4 into our function, it dutifully interates through cutPoints until it gets to 5. Using 5 and 4, we find that our number meets the criteria above and runs the code. 4>=(5-1) AND 4<5. It’s in this case only that the rest of the code runs:

1

return roman(subtractor) + roman(num + subtractor)

roman(1) gives us I, and roman(4+1)gives us V. Thus, we end up with IV.