R
Ruby Quiz
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...
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...