This week's quiz is to write a converter to and from Roman numerals.
The script should be a standard Unix filter, reading from files specified on the command-line or STDIN and writing to STDOUT. Each line of input will contain one integer (between 1 and 3999) expressed as an Arabic or Roman numeral. There should be one line of output for each line of input, containing the original number in the opposite format.
For example, given the following input:
III
29
38
CCXCI
1999
The correct output is:
3
XXIX
XXXVIII
291
MCMXCIX
If you're not familiar with or need a refresher on Roman numerals, the rules are simple. First, there are seven letters associated with seven values:
I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000
You can combine letters to add values, by listing them largest to smallest from left to right:
II is 2
VIII is 8
XXXI is 31
However, you may only list three consecutive identical letters. That requires a special rule to express numbers like 4 and 900. That rule is that a single lower value may proceed a larger value, to indicate subtraction. This rule is only used to build values not reachable by the previous rules:
IV is 4
CM is 900
But 15 is XV, not XVX.
Quiz Summary
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:
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:
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:
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:
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:
["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:
# 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:
Fun, but there's more. For Dave's final magic trick he defines a class:
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 + 5 # => IX
Even better though, is that Dave removes the need for that first step with:
# 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...
