[SUMMARY] Roman Numerals (#22)

Discussion in 'Ruby' started by Ruby Quiz, Mar 10, 2005.

  1. Ruby Quiz

    Ruby Quiz Guest

    I like these easy problems. The barrier to entry is low, so we see lots of
    attempts and as a result, some great tricks. I'll see if I can hit the
    highlights below.

    First, I said solving this is easy, but how easy? Well, the problem gives us
    the conversion chart, which is just crying out to be a Hash:

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

    That's the version from my code, but most people used something very similar.

    From there we just need to_roman() and to_arabic() methods, right? Sounded like
    too much work for a lazy bum like me, so I cheated. If you build a conversion
    table, you can get away with just doing the conversion one way:

    ROMAN_NUMERALS = Array.new(3999) do |index|
    target = index + 1
    ROMAN_MAP.keys.sort { |a, b| b <=> a }.inject("") do |roman, div|
    times, target = target.divmod(div)
    roman << ROMAN_MAP[div] * times
    end
    end

    This is the to_roman() method many solutions hit on. I just used mine to fill
    an Array. The algorithm here isn't too tough. Divide the target number by each
    value there is a roman numeral for; copy the numeral that many times; reduce the
    target and repeat. Ruby's divmod() is great for this.

    From there, it's trivial to wrap a Unix filter around the Array. However, I do
    like to validate input, so I did one more little prep task:

    IS_ROMAN = /^#{ROMAN_MAP.keys.sort { |a,b| b<=>a }.inject("") do |exp, n|
    num = ROMAN_MAP[n]
    exp << if num.length == 2 then "(?:#{num})?" else num + "{0,3}" end
    end}$/
    IS_ARABIC = /^(?:[123]\d{3}|[1-9]\d{0,2})$/

    That first Regexp is a little ugly and it sure didn't save me any typing, but it
    did keep me from having to think, which is almost as good. It builds the
    validating Regexp from my Array by tacking a "{0,3}" onto single letters and
    wrapping double letters in "(?:...)?".

    The second Regexp is a much more straight forward. It's just a hand coded
    pattern to match 1..3999, a number in the range we can convert to and from.

    Now, we're ready for the Unix filter wrapper:

    if __FILE__ == $0
    ARGF.each_line do |line|
    line.chomp!
    case line
    when IS_ROMAN then puts ROMAN_NUMERALS.index(line) + 1
    when IS_ARABIC then puts ROMAN_NUMERALS[line.to_i - 1]
    else raise "Invalid input: #{line}"
    end
    end
    end

    In English that says, for each line of input see if if matches IS_ROMAN and if
    it does, look it up in the Array. If it doesn't match IS_ROMAN but does match
    IS_ARABIC, index into the Array to get the match. If none of that is true,
    complain about the broken input. Simple stuff.

    If you don't want to build the Array, you just need to create the other
    converter. It's not hard. Here's the version from Jason Bailey's script:

    @data = [
    ["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]
    ]

    # ...

    def toArabic(rom)
    reply = 0
    for key, value in @data
    while rom.index(key) == 0
    reply += value
    rom.slice!(key)
    end
    end
    reply
    end

    The method starts by setting a reply variable to 0, to hold the answer. Then it
    hunts for each roman numeral in in the rom String, increments reply by that
    value, and removes that numeral from the String. The ordering of the @data
    Array ensures that a "XL" or "IV" will be found before an "X" or "I".

    Those are simple solutions, but let's jump over to Dave Burt's code for a little
    Ruby voodoo. Dave's code builds a module RomanNumerals (not shown) with
    to_integer() and from_integer(), similar to what we've discussed above. The
    module also defines is_roman_numeral?() and some helpful constants like DIGITS,
    MAX, and REGEXP. (Dave deserves an extra cookie for his clever dance to keep
    things like "IV" out of DIGITS.)

    Anyway, the module is a small chunk of Dave's code and the rest is fun. Let's
    see him put it to use:

    class String
    # Considers string a roman numeral numeral,
    # and converts it to the corresponding integer.
    def to_i_roman
    RomanNumerals.to_integer(self)
    end
    # Returns true iif the subject is a roman numeral.
    def is_roman_numeral?
    RomanNumerals.is_roman_numeral?(self)
    end
    end
    class Integer
    # Converts this integer to a roman numeral.
    def to_s_roman
    RomanNumerals.from_integer(self) || ''
    end
    end

    First, he adds converters to String and Integer. This allows you to code things
    like:

    puts "In the year #{1999.to_s_roman} ..."

    Fun, but there's more. For Dave's final magic trick he defines a class:

    # Integers that look like roman numerals
    class RomanNumeral
    attr_reader :to_s, :to_i

    @@all_roman_numerals = []

    # May be initialized with either a string or an integer
    def initialize(value)
    case value
    when Integer
    @to_s = value.to_s_roman
    @to_i = value
    else
    @to_s = value.to_s
    @to_i = value.to_s.to_i_roman
    end
    @@all_roman_numerals[to_i] = self
    end

    # Factory method: returns an equivalent existing object
    # if such exists, or a new one
    def self.get(value)
    if value.is_a?(Integer)
    to_i = value
    else
    to_i = value.to_s.to_i_roman
    end
    @@all_roman_numerals[to_i] || RomanNumeral.new(to_i)
    end

    def inspect
    to_s
    end

    # Delegates missing methods to Integer, converting arguments
    # to Integer, and converting results back to RomanNumeral
    def method_missing(sym, *args)
    unless to_i.respond_to?(sym)
    raise NoMethodError.new(
    "undefined method '#{sym}' for #{self}:#{self.class}")
    end
    result = to_i.send(sym,
    *args.map {|arg| arg.is_a?(RomanNumeral) ? arg.to_i : arg })
    case result
    when Integer
    RomanNumeral.get(result)
    when Enumerable
    result.map do |element|
    element.is_a?(Integer) ? RomanNumeral.get(element) :
    element
    end
    else
    result
    end
    end
    end

    If you use the factory method get() to create these objects, it's efficient with
    reuse, always giving you the same object for the same value.

    Note that method_missing() basically delegates to Integer at the end there,
    allowing you to treat these objects mostly as Integers. This class allows you
    to code things like:

    IV = RomanNumeral.get(4)
    IV + 5 # => IX

    Even better though, is that Dave removes the need for that first step with:

    # Enables uppercase roman numerals to be used interchangeably
    # with integers. They are auto-vivified RomanNumeral constants
    # Synopsis:
    # 4 + IV #=> VIII
    # VIII + 7 #=> XV
    # III ** III #=> XXVII
    # VIII.divmod(III) #=> [II, II]
    def Object.const_missing sym
    unless RomanNumerals::REGEXP === sym.to_s
    raise NameError.new("uninitialized constant: #{sym}")
    end
    const_set(sym, RomanNumeral.get(sym))
    end

    This makes it so that Ruby will automatically turn constants like IX into
    RomanNumeral objects as needed. That's just smooth.

    My thanks go out to friends and Romans alike.

    Tomorrows quiz is about a constantly used but rarely implemented encoding, so
    stay tuned...
    Ruby Quiz, Mar 10, 2005
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Christopher Benson-Manica

    Roman numerals to ints

    Christopher Benson-Manica, Sep 12, 2003, in forum: C Programming
    Replies:
    13
    Views:
    730
    MikeyD
    Sep 17, 2003
  2. ARMAS

    Decimal to Roman Numerals

    ARMAS, Jan 24, 2007, in forum: C Programming
    Replies:
    31
    Views:
    1,736
    Dave Thompson
    Feb 6, 2007
  3. Roman Numerals

    , Aug 17, 2007, in forum: Java
    Replies:
    10
    Views:
    944
    Roedy Green
    Aug 18, 2007
  4. Replies:
    26
    Views:
    1,621
    CBFalconer
    Jan 28, 2008
  5. Ruby Quiz

    [QUIZ] Roman Numerals (#22)

    Ruby Quiz, Mar 4, 2005, in forum: Ruby
    Replies:
    25
    Views:
    364
    James Edward Gray II
    Mar 9, 2005
Loading...

Share This Page