Roman Numerals

roman.rb

# For numbers other than the basic digits :
#
# * Break the number into its place values in base 10  and convert each place
#   value recursively. e.g 399 gets converted in 3 phases 300,90 and 9
#   
#  For each place value :
#
# * Identify the nearest position of place value in Roman digit sequence
#
# * Two different cases for every place value `x`, which have different rules
#   of conversion. Each of these cases can be further subdivided into additive
#   and subtractive subcases
#
#   1. `x` is preceded by two Roman digits of same cardinality, e.g 90 
#       (preceded by 50 and 10)
#        
#       Additive Case    : Roman digits consist of a combination of the two 
#                          preceding digits
#
#       Subtractive Case : Roman digits consist of a combination of the the 
#                          suceeding digit and the smaller of the two preceding 
#                          digits
#
#   2. `x` is preceded by one Roman digit of same cardinality, e.g 200 
#     (preceded by 100 only)
#   
#       Additive Case    : Roman digits consist of one preceding digit only
#
#
#       Subtractive Case : Roman digits consist of the greatest preceding digit
#                          and the smallest succeeding digit


ROMAN_DIGITS = { 1    => "I",
                 5    => "V",
                 10   => "X",
                 50   => "L",
                 100  => "C",
                 500  => "D",
                 1000 => "M" }

def roman(x)
  # Error conditions
  raise ArgumentError.new("Cannot be 0 or Negative") if x <= 0
  raise ArgumentError.new("Overflow! Number cannot be greater than 3999") if x > 3999
  
  # Base condition
  return ROMAN_DIGITS[x] if ROMAN_DIGITS[x]

  # Partitioning keys into two arrays
  # based on input number x
  s2 = ROMAN_DIGITS.keys.sort
  s1 = []
  s1 << s2.shift while s2.size>0 and s2[0] <= x
  
  # Break up x into its most significant place value and remaining
  case s1.size % 2
    when 0 
      most_significant = (x/s1[-2])*s1[-2]
      rest = x % s1[-2]
    when 1
      most_significant = (x/s1.last)*s1.last
      rest = x % s1.last
  end
    
  # Convert an exact place value directly into Roman
  case s1.size % 2
  when 0
    num_digits = (x-s1.last)/s1[-2]
    rm_ms =  if num_digits < 4 # additive
                ROMAN_DIGITS[s1.last] + ROMAN_DIGITS[s1[-2]]*num_digits
              else # subtractive
                ROMAN_DIGITS[s1[-2]]  + ROMAN_DIGITS[s2.first]
              end
  when 1    
    num_digits = (x/s1.last)
    rm_ms =  if num_digits < 4 # additive
                ROMAN_DIGITS[s1.last]*num_digits
              else # subtractive
                ROMAN_DIGITS[s1.last] + ROMAN_DIGITS[s2.first]
              end
  end
  
  # Recursive call unless x is exactly equal to the place value of the most
  # significant digit
  most_significant == x ? rm_ms : rm_ms + roman(rest)
end  

roman1.rb

# For numbers other than the basic digits :
#
# * Break the number into its place values in base 10  and convert each place
#   value recursively. e.g 399 gets converted in 3 phases 300,90 and 9
#   
#  For each place value :
#
# * Identify the nearest position of place value in Roman digit sequence
#
# * Two different cases for every place value `x`, which have different rules
#   of conversion. Each of these cases can be further subdivided into additive
#   and subtractive subcases
#
#   1. `x` is preceded by two Roman digits of same cardinality, e.g 90 
#       (preceded by 50 and 10)
#        
#       Additive Case    : Roman digits consist of a combination of the two 
#                          preceding digits
#
#       Subtractive Case : Roman digits consist of a combination of the 
#                          suceeding digit and the smaller of the two preceding 
#                          digits
#
#   2. `x` is preceded by one Roman digit of same cardinality, e.g 200 
#     (preceded by 100 only)
#   
#       Additive Case    : Roman digits consist of one preceding digit only
#
#
#       Subtractive Case : Roman digits consist of a combination of the 
#                          greatest preceding digit and the smallest 
#                          succeeding digit

class Fixnum
  # Converts numbers into an array of place values for base 10
  # e.g. 123 => [100,20,3]
  def to_place_values
    multiple = 1
    s = self
    pv = []
    while s > 0 do
      q,r = s/10, s%10
      pv.unshift r * multiple
      multiple = multiple * 10
      s = q
    end
    pv
  end
end

ROMAN_DIGITS = { 1    => "I",
                 5    => "V",
                 10   => "X",
                 50   => "L",
                 100  => "C",
                 500  => "D",
                 1000 => "M" }

def place_value_to_roman(x)
  # Base condition
  return ROMAN_DIGITS[x] if ROMAN_DIGITS[x]
  
  # Partitioning keys into two arrays
  # based on input number x
  s2 = ROMAN_DIGITS.keys.sort
  idx = 0 ; idx = idx + 1 while s2[idx] and s2[idx] < x
  s1 = s2.slice!(0..idx-1)
      
  # Convert an exact place value directly into Roman
  case s1.size % 2
  when 0 # `x` is preceded by two Roman digits of same cardinality
    num_digits = (x-s1.last)/s1[-2]
    if num_digits < 4 # additive
      ROMAN_DIGITS[s1[-1]] + ROMAN_DIGITS[s1[-2]]*num_digits
    else # subtractive
      ROMAN_DIGITS[s1[-2]] + ROMAN_DIGITS[s2[0]]
    end
  when 1 # `x` is preceded by one Roman digit of same cardinality
    num_digits = (x/s1.last)
    if num_digits < 4 # additive
      ROMAN_DIGITS[s1.last]*num_digits
    else # subtractive
      ROMAN_DIGITS[s1.last] + ROMAN_DIGITS[s2.first]
    end
  end
end

def roman(x)
  # Error conditions
  raise ArgumentError.new("Cannot be 0 or Negative") if x <= 0
  raise ArgumentError.new("Overflow! Number cannot be greater than 3999") if x > 3999
  
  x.to_place_values.select { |p| p > 0 }.map { |p| place_value_to_roman p }.join
end  

test_roman.rb

require 'roman'
require 'test/unit'
class TestRoman < Test::Unit::TestCase

  # The digits of the roman system are as follows:
  # 1 -> I
  # 5 -> V
  # 10 -> X
  # 50 -> L
  # 100 -> C
  # 500 -> D
  # 1000 -> M
  def test_basic_digits
    mapping = { 1    => "I",
                5    => "V",
                10   => "X",
                50   => "L",
                100  => "C",
                500  => "D",
                1000 => "M" }

    mapping.each  { |k,v| assert(roman(k) == v) }
  end
  
  # The Romans had no notation or concept of 0 or negative numbers
  def test_error_zero_or_negative
    assert_raise ArgumentError do
      roman 0
    end
    
    assert_raise ArgumentError do
      roman -10
    end
    
  end
  
  # The maximum number possible under the traditional Roman system was 3999,
  # which is represented as MMMCMXCIX.  (The Romans would later add the
  # ability to denote a number was x1000 by putting a bar over it - that's not
  # in scope for this problem.)
  
  def test_max_and_overflow
    assert_raise ArgumentError do
      roman 4000
    end
    
    assert roman(3999) == "MMMCMXCIX"
  end
  
  
  
  # Only a maximum of three of the same character can occur in sequence - for
  # example, III is legal, but IIII is not.  Instead, the Romans would use the
  # next highest value with a subtractive digit in front of it - for example
  # 4, is written as IV or "one subtracted from five" - be sure to take this
  # into account!  Examples include IX for 9, IV for 4, and XC for 90.
  
  def test_freq_char
    assert roman(3) == "III"
    assert roman(4) == "IV"
    assert roman(9) == "IX"
    assert roman(90) == "XC"
  end
  
  # The subtractive digit can only be from the next lowest cardinality - for
  # example, you cannot write IC for 99, since I is from the 1's - instead 99
  # is written as XCIX or "90 + 9".  The same goes for numbers such a 1999
  # (written as MCMXCIX) and 94 (written as XCIV), etc.
  def test_subtractive
    assert roman(99) == "XCIX"
    assert roman(1999) == "MCMXCIX"
    assert roman(94) == "XCIV"    
  end
  
end