Roman numeral converter in Ruby

Question

For a Project Euler problem, I made a Ruby roman numeral converter:

def romanize(num)
    digits = {
        1000 => "M",
        900  => "CM", 500 => "D", 400 => "CD", 100 => "C",
        90   => "XC", 50  => "L", 40  => "XL", 10  => "X",
        9    => "IX", 5   => "V", 4   => "IV", 1   => "I"
    }
    digits.reduce("") do |acc, digit|
        key, numeral = digit
        occurances, num = num.divmod(key)
        acc + (numeral * occurances)
    end
end

This works great, but I'm not sure it's good Ruby. Specifically, I'm wondering if the body of the reduce block could be shortened, and if it could made more clear.

For example, I don't think its that obvious that num is being modified in the middle of the reduce block.

Also, I know I can monkey patch this into the Fixnum class, but that's not what I'm looking for.

Update #1

@Tokland's answer taught me some new things. His answer works well, and is pretty clever.

If I take just two of his concepts and apply them to mine, the digits.reduce("") ... block can be simplified to:

digits.map do |key, numeral|
    occurances, num = num.divmod(key)
    numeral * occurances
end.join

This needs one less line because it deconstructs the digit key/value in the block arguments. Also, it creates an array which is joined into a string at the end. For big numbers (around 100-trillion), this is much quicker.

The only problem I still see is that it's modifying the num variable, which is essentially global state to the block.

Answer 1

Some notes:

• Use 2 spaces for indentation, not 4.
• key, numeral = digit: You can unpack block arguments: do |acc, (key, numeral)|.
• Concating strings is costly, better build an array and finally join it.
• You are using inject, which is great because it'a functional abstraction, but you are modifying num on each iteration, so it ends up being a weird mixture of functional and imperative style. I know it's a bit cumbersome, but conceptually it's better to keep also num in the accumulator.

I'd write:

digits.reduce(:output => [], :num => num) do |state, (key, numeral)|
  ocurrences, remainder = state[:num].divmod(key)
  {:output => state[:output] << (numeral * ocurrences), :num => remainder} 
end[:output].join

Answer 2

Rather than looping through digits, you could break down num in a loop, like this:

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

def romanize(num)
  @digits.keys.each_with_object('') do |key, str|
    nbr, num = num.divmod(key)
    str << @digits[key]*nbr
  end
end

romanize(888) # => "DCCCLXXXVIII" 
romanize(999) # => "CMXCIX"

Note that

str << @digits[key]*nbr

leaves str unchanged if nbr = 0.

You could also do this using recursion:

 def romanize(num, str='')
  return str if num == 0
  key = @digits.keys.find { |k| k <= num }
  str << @digits[key]
  romanize(num-key, str)
end

romanize(888) # => "DCCCLXXXVIII" 
romanize(999) # => "CMXCIX"

Note both of these methods require Ruby 1.9+. Since 1.9, hash pairs have been kept in the order in which they were added. For Ruby 1.8x you would need to replace @digits with an array of key-value pairs or order its keys in an array keys and for each key key in keys, extract its value with @digits[key].