From: Ruby Quiz <james@...>
Date: 2005-03-10T22:43:31+09:00
Subject: [SUMMARY] Roman Numerals (#22)

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...