4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ In this case: |(key, numeral)| -> |key, numeral| \$\endgroup\$ – tokland Oct 25 '13 at 6:49
  • \$\begingroup\$ @tokland Good catch. I've corrected it in the question. \$\endgroup\$ – ahuth Oct 25 '13 at 10:25
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ There's some good stuff I learned in this answer (such as unpacking arguments. Constructing an array with reduce/inject feels wrong, though, doesn't it? Even though that's what I did in mine, it seems like there should be a good map solution. \$\endgroup\$ – ahuth Oct 25 '13 at 1:09
  • \$\begingroup\$ Also, I benchmarked constructing an array and then joining it versus string concatenation. For trivial examples, there's almost no difference. For a number in the 100-trillions, though, joining was much quicker (0.4s vs 2.5s). \$\endgroup\$ – ahuth Oct 25 '13 at 1:10
  • \$\begingroup\$ Finally, while it is cumbersome, it's also very clever to use the accumulator to pass state from one iteration to the next. Avoids modifying anything external to the block. Maybe it's just me, though, but it seems like it's not obvious what's going on here at first glance. I'd be worried about doing something like this on a real project, because someone else might struggle to figure it out... and I might struggle to figure it out 6 months from now. \$\endgroup\$ – ahuth Oct 25 '13 at 1:17
  • \$\begingroup\$ @ahuth: Indeed for a programmer not familiary with functional style this may be hard to grasp at first. I don't think you can do it with map because there is state in the computation. In functional languages you'd probably write it with a recursive function (but it would be completely equivalent, a fold is a recursive abstraction). Instead of state you'd have the two arguments (output/num). I've used a hash instead of an array pair to try to make it more clear. \$\endgroup\$ – tokland Oct 25 '13 at 6:47
  • \$\begingroup\$ digits.reduce([[], num]) do |(output, current), (key, numeral)| ? Looks better than hash. \$\endgroup\$ – Victor Moroz Oct 27 '13 at 0:49
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Thanks for the recursive solution. If I'm not mistaken, this is tail-call optimized, too? \$\endgroup\$ – ahuth Nov 5 '13 at 15:01
  • \$\begingroup\$ Sorry, but I can't help you with that. In fact, this is the first time I've heard that term. I looked it up and get the general idea, but best for someone else to answer that. \$\endgroup\$ – Cary Swoveland Nov 8 '13 at 5:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.