# Roman Numerals

At the office today we did a coding dojo and the kata that we used was Roman Numerals. We actually did the kata in Java because that was what everyone was familiar with but I decided to work on doing it in Ruby.

After after 20 minutes I got a working solution. However, that's when the fun starts! I spent some time trying several refactorings on the code and didn't really get anywhere. The code that I was refactoring looked roughly like this

@value_map = { 1 => "I", 4 => "IV", 5 => "V", 9 => "IX", 10 => "X", ... } [..., 10, 9, 5, 4, 1].each do |value| while(number >= value) number -= value result += @value_map[value] end end

Because of the expressiveness of Ruby, this code is terse. However, we are covering our edge cases in an odd way. This worked and I couldn't necessarily refactor it to be better. However, I knew that if we added a feature that those edge cases would make it start to look ugly. So, I added a feature (and learned something about roman numerals!). Instead of just going to 3999, we would support 38,999. This meant we needed to add the roman numerals (V) = 5,000 and (X) = 10,000. I added the feature and then refactored and ended up with something like this

class Romans def initialize @value_map = { 1 => "I", 5 => "V", 10 => "X", 50 => "L", 100 => "C", 500 => "D", 1000 => "M", 5000 => "(V)", 10000 => "(X)", } end def convert integer result = "" [10_000, 1000, 100, 10, 1].each do |value| integer, result = convert_to_highest_significant_digit integer, value, result end result end def convert_to_highest_significant_digit integer, value, result if integer >= value * 9 result += @value_map[value] + @value_map[value * 10] integer -= value * 9 elsif integer >= value * 5 result += @value_map[value * 5] integer -= value * 5 elsif integer >= value * 4 result += @value_map[value] + @value_map[value * 5] integer -= value * 4 end while integer >= value result += @value_map[value] integer -= value end [integer, result] end end

The code above is not without problems, either. We have to lean on the Ruby feature of multiple returns. We also have that ugly if/elsif/elsif statement. We may be able to handle this with another object, though. Here is a more object oriented way

class Romans def initialize @values = [ RomanDigitGroup.new( RomanDigit.new(1, "I"), RomanDigit.new(5, "V"), RomanDigit.new(10, "X") ), RomanDigitGroup.new( RomanDigit.new(10, "X"), RomanDigit.new(50, "L"), RomanDigit.new(100, "C") ), RomanDigitGroup.new( RomanDigit.new(100, "C"), RomanDigit.new(500, "D"), RomanDigit.new(1000, "M") ), RomanDigitGroup.new( RomanDigit.new(1000, "M"), RomanDigit.new(5000, "(V)"), RomanDigit.new(10_000, "(X)") ), ] end def convert integer result = "" @values.reverse.each do |value| roman = value.convert_to_roman(integer) integer -= value.max_represented_value(integer) result += roman end result end end class RomanDigit attr_reader :value attr_reader :roman def initialize value, roman @value = value @roman = roman end end class RomanDigitGroup attr_reader :one attr_reader :five attr_reader :ten def initialize one, five, ten @one = one @five = five @ten = ten @base_value = one.value end def convert_to_roman integer result = "" while integer >= ten_x result += @ten.roman integer -= ten_x end if integer >= nine_x result += @one.roman + @ten.roman integer -= nine_x elsif integer >= five_x result += @five.roman integer -= five_x elsif integer >= four_x result += @one.roman + @five.roman integer -= four_x end while integer >= one_x result += @one.roman integer -= one_x end result end def max_represented_value integer integer_start = integer integer -= ten_x while integer >= ten_x if integer >= nine_x integer -= nine_x elsif integer >= five_x integer -= five_x elsif integer >= four_x integer -= four_x end integer -= one_x while integer >= one_x integer_start - integer end private def ten_x @base_value * 10 end def nine_x @base_value * 9 end def five_x @base_value * 5 end def four_x @base_value * 4 end def one_x @base_value end end

Unfortunately, that doesn't look exactly right either. We still have the complexity of the while and if/elsifs. The object oriented form may be easier to read and understand but I think it is a little heavy for our purposes (the RomanDigitGroup class conveys how Roman Numerals actually work). This method also allows us to get rid of the hash data structure and the duplication of data (hash and array in the prior implementations).

So, where do I go from here? I'm not really sure. Is there a clever trick to get rid of the ugly while and if statements? Is there a better abstraction that could be applied? Maybe this algorithm has irreducible complexity? I personally like the second version (non object oriented with ugly if statements) best.