Doing Math with Roman Numbers

Problem

You want to convert between Arabic and Roman numbers, or do arithmetic with Roman numbers and get Roman numbers as your result.

Solution

The simplest way to define a Roman class that acts like Fixnum is to have its instances delegate most of their method calls to a real Fixnum (as seen in the previous recipe, Recipe 2.13). First we'll implement a container for the Fixnum delegate, and methods to convert between Roman and Arabic numbers:

class Roman # These arrays map all distinct substrings of Roman numbers # to their Arabic equivalents, and vice versa. @@roman_to_arabic = [['M', 1000], ['CM', 900], ['D', 500], ['CD', 400], ['C', 100], ['XC', 90], ['L', 50], ['XL', 40], ['X', 10], ['IX', 9], ['V', 5], ['IV', 4], ['I', 1]] @@arabic_to_roman = @@roman_to_arabic.collect { |x| x.reverse }.reverse # The Roman symbol for 5000 (a V with a bar over it) is not in # ASCII nor Unicode, so we won't represent numbers larger than 3999. MAX = 3999 def initialize(number) if number.respond_to? :to_str @value = Roman.to_arabic(number) else Roman.assert_within_range(number) @value = number end end # Raise an exception if a number is too large or small to be represented # as a Roman number. def Roman.assert_within_range(number) unless number.between?(1, MAX) msg = "#{number} can't be represented as a Roman number." raise RangeError.new(msg) end end #Find the Fixnum value of a string containing a Roman number. def Roman.to_arabic(s) value = s if s.respond_to? :to_str c = s.dup value = 0 invalid = ArgumentError.new("Invalid Roman number: #{s}") value_of_previous_number = MAX+1 value_from_previous_number = 0 @@roman_to_arabic.each_with_index do |(roman, arabic), i| value_from_this_number = 0 while c.index(roman) == 0 value_from_this_number += arabic if value_from_this_number >= value_of_previous_number raise invalid end c = c[roman.size..s.size] end #This one's a little tricky. We reject numbers like "IVI" and #"IXV", because they use the subtractive notation and then #tack on a number that makes the total overshoot the number #they'd have gotten without using the subtractive #notation. Those numbers should be V and XIV, respectively. if i > 2 and @@roman_to_arabic[i-1][0].size > 1 and value_from_this_number + value_from_previous_number >= @@roman_to_arabic[i-2][1] raise invalid end value += value_from_this_number value_from_previous_number = value_from_this_number value_of_previous_number = arabic break if c.size == 0 end raise invalid if c.size > 0 end return value end def to_arabic @value end #Render a Fixnum as a string depiction of a Roman number def to_ roman value = to_arabic Roman.assert_within_range(value) repr = "" @@arabic_to_roman.reverse_each do |arabic, roman| num, value = value.divmod(arabic) repr << roman * num end repr end

Next, we'll make the class respond to all of Fixnum's methods by implementing a method_missing that delegates to our internal Fixnum object. This is substantially the same method_missing as in Recipe 2.13 Whenever possible, we'll transform the results of a delegated method into Roman objects, so that operations on Roman objects will yield other Roman objects.

# Delegate all methods to the stored integer value. If the result is # a Integer, transform it into a Roman object. If it's an array # containing Integers, transform it into an array containing Roman # objects. def method_missing(m, *args) super unless @value.respond_to?(m) hex_args = args.collect do |arg| arg.kind_of?(Roman) ? arg.to_int : arg end result = @value.send(m, *hex_args) return result if m == :coerce begin case result when Integer Roman.new(result) when Array result.collect do |element| element.kind_of?(Integer) ? Roman.new(element) : element end else result end rescue RangeError # Too big or small to fit in a Roman number. Use the original number result end end

The only methods that won't trigger method_missing are methods like to_s, which we're going to override with our own implementations:

def respond_to?(method_name) super or @value.respond_to? method_name end def to_s to_ roman end def inspect to_s end end

We'll also add methods to Fixnum and String that make it easy to create Roman objects:

class Fixnum def to_roman Roman.new(self) end end class String def to_roman Roman.new(self) end end

Now we're ready to put the Roman class through its paces:

72.to_roman # => LXXII 444.to_roman # => CDXLIV 1979.to_roman # => MCMLXXIX 'MCMXLVIII'.to_roman # => MCMXLVIII Roman.to_arabic('MCMLXXIX') # => 1979 'MMI'.to_roman.to_arabic # => 2001 'MMI'.to_roman + 3 # => MMIV 'MCMXLVIII'.to_roman # => MCMXLVIII 612.to_roman * 3.to_roman # => MDCCCXXXVI (612.to_roman * 3).divmod('VII'.to_roman) # => [CCLXII, II] 612.to_roman * 10000 # => 6120000 # Too big 612.to_roman * 0 # => 0 # Too small 'MCMXCIX'.to_roman.succ # => MM ('I'.to_roman..'X'.to_roman).collect # => [I, II, III, IV, V, VI, VII, VIII, IX, X]

Here are some invalid Roman numbers that the Roman class rejects:

'IIII'.to_roman # ArgumentError: Invalid Roman number: IIII 'IVI'.to_roman # ArgumentError: Invalid Roman number: IVI 'IXV'.to_roman # ArgumentError: Invalid Roman number: IXV 'MCMM'.to_roman # ArgumentError: Invalid Roman number: MCMM 'CIVVM'.to_ roman # ArgumentError: Invalid Roman number: CIVVM -10.to_roman # RangeError: -10 can't be represented as a Roman number. 50000.to_roman # RangeError: 50000 can't be represented as a Roman number.

 

Discussion

The rules for constructing Roman numbers are more complex than those for constructing positional numbers such as the Arabic numbers we use. An algorithm for parsing an Arabic number can scan from the left, looking at each character in isolation. If you were to scan a Roman number from the left one character at a time, you'd often find yourself having to backtrack, because what you thought was "XI" (11) would frequently turn out to be "XIV" (14).

The simplest way to parse a Roman number is to adapt the algorithm so that (for instance) "IV" as treated as its own "character," distinct from "I" and "V". If you have a list of all these "characters" and their Arabic values, you can scan a Roman number from left to right with a greedy algorithm that keeps a running total. Since there are few of these "characters" (only 13 of them, for numbers up to 3,999), and none of them are longer than 2 letters, this algorithm is workable. To generate a Roman number from an Arabic number, you can reverse the process.

The Roman class given in the Solution works like Fixnum, thanks to the method_missing strategy first explained in Recipe 2.13. This lets you do math entirely in Roman numbers, except when a result is out of the supported range of the Roman class.

Since this Roman implementation only supports 3999 distinct numbers, you could make the implementation more efficient by pregenerating all of them and retrieving them from a cache as needed. The given implementation lets you extend the implementation to handle larger numbers: you just need to decide on a representation for the larger Roman characters that will work for your encoding.

The Roman numeral for 5,000 (a V with a bar over it) isn't present in ASCII, but there are Unicode characters U+2181 (the Roman numeral 5,000) and U+2182 (the Roman numeral 10,000), so that's the obvious choice for representing Roman numbers up to 39,999. If you're outputting to HTML, you can use a CSS style to put a bar above "V", "X", and so on. If you're stuck with ASCII, you might choose "_V" to represent 5,000, "_X" to represent 10,000, and so on. Whatever you chose, you'd add the appropriate "characters" to the roman_to_arabic array (remembering to add "M_V" and "_V_X" as well as "_V" and "_X"), increment MAX, and suddenly be able to instantiate Roman objects for large numbers.

The Roman#to_arabic method implements the "new" rules for Roman numbers: that is, the ones standardized in the Middle Ages. It rejects certain number representations, like IIII, used by the Romans themselves.

Roman numbers are common as toy or contest problems, but it's rare that a programmer will have to treat a Roman number as a number, as opposed to a funny-looking string. In parts of Europe, centuries and the month section of dates are written using Roman numbers. Apart from that, outline generation is probably the only real-world application where a programmer needs to treat a Roman number as a number. Outlines need several of visually distinct ways to represent the counting numbers, and Roman numbers (upper- and lowercase) provide two of them.

If you're generating an outline in plain text, you can use Roman#succ to generate a succession of Roman numbers. If your outline is in HTML format, though, you don't need to know anything about Roman numbers at all. Just give an

  1. tag a CSS style of list-style-type:lower-roman or list-style-type:upper-roman. Output the elements of your outline as

  2. tags inside the
    1. tag. All modern browsers will do the right thing:

       

      1. Primus

      2. Secundis

      3. Tertius

       

      See Also

      • Recipe 2.13, "Simulating a Subclass of Fixnum"

      • An episode of the Ruby Quiz focused on algorithms for converting between Roman and Arabic numbers; one solution uses an elegant technique to make it easier to create Roman numbers from within Ruby: it overrides Object#const_ missing to convert any undefined constant into a Roman number; this lets you issue a statement like XI + IX, and get XX as the result (http://www.rubyquiz.com/quiz22.html)

      Related

      Категории