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.