Created
January 12, 2010 08:32
-
-
Save deepakjois/275015 to your computer and use it in GitHub Desktop.
Roman Numerals
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment