Roman Numerals

March 6, 2009

Roman numerals are a number-notation system developed in classical Rome, chiefly used today to indicate the year in which a motion picture was made, or the sequence number of a Super Bowl.

Roman numerals use letters of the alphabet to indicate numerical value, according to the following code:

    I 1    V 5    X 10    L 50    C 100    D 500    M 1000

For example, the number 1732 is represented by Roman numerals as MDCCXXXII, and the number 1956 is represented by Roman numerals as MDCCCCLVI. Letter symbols are normally written from the largest symbol to the smallest, left to right, so the numeric values are additive. However, in order to conserve space, it is permissible to replace four of the same symbol written all in a row in a subtractive manner to the left of a higher-value symbol, so that 1956 may also be represented as MCMLVI, where the CM symbol, with C before M, indicates that C is subtracted from M, and thus indicates the numeric value 900. Wikipedia and MathWorld explain the common usage of Roman numerals.

Your task is to write a function that takes two roman numerals (character strings) as input and returns their sum as a roman numeral as output. Be sure that input can be given in either the additive or subtractive forms of Roman numerals; give output using the subtractive form. What is add-roman("CCCLXIX", "CDXLVIII")?


Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
4 Comments »

4 Responses to “Roman Numerals”

  1. Roger said
    March 9, 2009 at 7:56 PM

    I started to program thinking that constructions like “IIX” for 8 are allowed. Wikipedia says that this kind of subtractive notation exists, but it seems very rare. Whatever, here is my roman->decimal.

    
(define roman->decimal
  (lambda (x)
    (decode-roman
     (string->list x))))

(define decode-roman
  (lambda (chars)
    (letrec
        ((decode-roman-helper
          (lambda (fir res akk cur)
            (cond
              ((null? res) (+ akk cur))
              ((< (single-roman->decimal fir) (single-roman->decimal (car res)))
               (decode-roman-helper (car res)
                                    (cdr res)
                                    (- akk cur)
                                    (single-roman->decimal (car res))))
              ((> (single-roman->decimal fir) (single-roman->decimal (car res)))
               (decode-roman-helper (car res)
                                    (cdr res)
                                    (+ cur akk)
                                    (single-roman->decimal (car res))))
              (else (decode-roman-helper
                     (car res)
                     (cdr res)
                     akk
                     (+ (single-roman->decimal (car res)) cur)))))))
      (decode-roman-helper (car chars) (cdr chars) 0 (single-roman->decimal (car chars))))))

(define single-roman->decimal
  (lambda (str)
    (cond
      ((char=? str #\M) 1000)
      ((char=? str #\D) 500)
      ((char=? str #\C) 100)
      ((char=? str #\L) 50)
      ((char=? str #\X) 10)
      ((char=? str #\V) 5)
      ((char=? str #\I) 1)
      (else 0))))
  2. FalconNL said
    March 10, 2009 at 11:13 PM

    Haskell (someone more experienced than me can probably turn these into one-liners):

    import Data.Map (fromList, (!))
    import Data.Char
    import Data.List

    data Roman = I | V | X | L | C | D | M deriving (Enum, Eq, Ord, Read, Show)

    main = print $ addRoman “CCCLXIX” “CDXLVIII”

    values :: [(Roman, Int)]
    values = [(M, 1000), (D, 500), (C, 100), (L, 50), (X, 10), (V, 5), (I, 1)]

    fromRoman :: String -> Int
    fromRoman = fromRoman’ . map (read . return) where
    fromRoman’ (x:y:xs) = (if x String
    toRoman = map toLower . concatMap show . subtractiveStyle . toRoman’ values where
    toRoman’ [] _ = []
    toRoman’ ((r, v):xs) n = replicate (div n v) r ++ toRoman’ xs (mod n v)

    subtractiveStyle :: [Roman] -> [Roman]
    subtractiveStyle (x:y:ys) | y == pred x && isPrefixOf [y,y,y] ys
    = y : succ x : subtractiveStyle (drop 3 ys)
    subtractiveStyle xs = xs

    addRoman :: String -> String -> String
    addRoman a b = toRoman $ fromRoman a + fromRoman b

  3. FalconNL said
    March 10, 2009 at 11:18 PM

    Evidently there’s only a limited selection of languages that will trigger the right formatting. My apologies.

    import Data.Map (fromList, (!))
import Data.Char
import Data.List

data Roman = I | V | X | L | C | D | M deriving (Enum, Eq, Ord, Read, Show)

main = print $ addRoman "CCCLXIX" "CDXLVIII"

values :: [(Roman, Int)]
values = [(M, 1000), (D, 500), (C, 100), (L, 50), (X, 10), (V, 5), (I, 1)]

fromRoman :: String -> Int
fromRoman = fromRoman' . map (read . return) where
    fromRoman' (x:y:xs) = (if x < y then -1 else 1) * val x + fromRoman' (y:xs)
    fromRoman' xs = sum $ map val xs
    val c = fromList values ! c

toRoman :: Int -> String
toRoman = map toLower . concatMap show . subtractiveStyle . toRoman' values where
    toRoman' []          _ = []
    toRoman' ((r, v):xs) n = replicate (div n v) r ++ toRoman' xs (mod n v)

subtractiveStyle :: [Roman] -> [Roman]
subtractiveStyle (x:y:ys) | y == pred x && isPrefixOf [y,y,y] ys
                          = y : succ x : subtractiveStyle (drop 3 ys)
subtractiveStyle xs = xs

addRoman :: String -> String -> String
addRoman a b = toRoman $ fromRoman a + fromRoman b
  4. programmingpraxis said
    March 10, 2009 at 11:19 PM

    FalconNL: Haskell is not one of the supported languages for the WordPress sourcecode tag. See my HOWTO page for more about posting source code in comments.

Leave a Reply