Programming Praxis

11 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.
5. kawas said

   September 27, 2011 at 10:17 PM

   At first I thought my solution was long and ugly and than I read the praxis’ Scheme solution :)
   I read Roger’s Scheme but it is incomplete : no encode-roman
   I read FalconNL’s Haskell and subtractiveStyle doesn’t work on numbers like 1904

   So I guess I’ll roll my ugly clojure solution :

   (def *romans* {\I 1, \V 5, \X 10, \L 50, \C 100, \D 500, \M 1000})
   
   (defn from-roman [rs]
     (loop [rs (reverse rs) prev 0 dnum 0]
       (let [v (*romans* (first rs))]
         (cond
           (nil? v)   dnum
           (< v prev) (recur (next rs) v (- dnum v))
           :else      (recur (next rs) v (+ dnum v))))))
   
   (defn to-roman [d]
     (let [dq (quot d 1000) dr (rem d 1000)
           r (vec (repeat dq \M))
           romans (reverse (sort-by second *romans*))]
       (loop [d dr romans romans r r]
         (if (zero? d) (apply str r)
           (let [[[u10 v10] [u5 v5] [u1 v1]] romans dq (quot d v1) dr (rem d v1)]
             (cond
               (= dq 9) (recur dr (nnext romans) (conj r u1 u10))
               (> dq 4) (recur dr (nnext romans) (apply conj r u5 (repeat (- dq 5) u1)))
               (= dq 4) (recur dr (nnext romans) (conj r u1 u5))
               (> dq 0) (recur dr (nnext romans) (apply conj r (repeat dq u1)))
               :else    (recur d (nnext romans) r)))))))
   
   (defn add-roman [& rs]
     (to-roman (apply + (map from-roman rs))))
   

   Some use cases :

   user=> (add-roman "CCCLXIX" "CDXLVIII")
   "DCCCXVII"
   
   user=> (add-roman "MMCCCII" "MMDCII")
   "MMMMCMIV"
   
6. Pavel Bogomolenko said

   December 2, 2011 at 9:23 AM

   Hello everybody,

   I briefly walked through all posted examples and figured out that noone completely solved this task.
   kawas was very close to solution however even in his second use case user=> (add-roman “MMCCCII” “MMDCII”) result seemed to be wrong because there cannot be 4 M in a row. Please see wikipedia as a proof-link http://en.wikipedia.org/wiki/Roman_numerals

   The symbols "I", "X", "C", and "M" can be repeated three times in succession, but no more. (They may appear four times if the third and fourth are separated by a smaller value, such as XXXIX.) "D", "L", and "V" can never be repeated.
   

   So here is my solution in Python:

   rom_arab_dict = {'I' : 1, 'V' : 5, 'X' : 10, 'L' : 50, 'C' : 100, 'D' : 500, 'M' : 1000}
   limit_sum = 3999
   
   def add_roman(a, b): 
     arab_sum = roman_to_arabic(a) + roman_to_arabic(b)
     if arab_sum <= limit_sum:
       arabic_to_roman(arab_sum)
       print('Roman sum: %s + %s = %s' % (a, b, arabic_to_roman(arab_sum)))
       print('Arab sum(verification): %s + %s = %s' % (roman_to_arabic(a), roman_to_arabic(b), arab_sum))
     else:
       print('Result sum out of range of Roman numbers.\n Should be less or equal to %d' % limit_sum)
   
   def roman_to_arabic(roman_num):
     sum = 0 
     arab_lst = [rom_arab_dict[x] for x in roman_num for y in rom_arab_dict.keys() if x == y]
     for index, item in enumerate(arab_lst):
       if index + 1 < len(arab_lst):
         if item < arab_lst[index + 1]: 
           arab_lst[index] = arab_lst[index + 1] - arab_lst[index]
           del arab_lst[index + 1]
       sum += arab_lst[index]
   
     return sum 
     
   def arabic_to_roman(arab_num):
     # dict {'key':val} to list [(v, k)]
     items = [(v, k) for k, v in rom_arab_dict.items()]
     items.sort()
     # reverse order from high to low
     items.reverse()
   
     rom_lst = []
     for index, item in enumerate(items):
       v, k = item
       while arab_num - v >= 0:
         arab_num -= v
         tmp_v, tmp_k = items[index]
         rom_lst.append(tmp_k)
         if rom_lst.count(tmp_k) == 4:
           rom_lst = rom_lst[:-3]
           tmp_v, tmp_k = items[index - 1]
           rom_lst.append(tmp_k)
     
     return ''.join(rom_lst)
   
   #Test cases
   add_roman("CCCLXIX", "CDXLVIII")
   add_roman("CDXXVIII", "DLXXVIII")
   add_roman("MDCCL", "MDCLXX")
   

   Results:

   Roman sum: CCCLXIX + CDXLVIII = DCCCXVII
   Arab sum(verification): 369 + 448 = 817
   Roman sum: CDXXVIII + DLXXVIII = MVI
   Arab sum(verification): 428 + 578 = 1006
   Roman sum: MDCCL + MDCLXX = MMMCDXX
   Arab sum(verification): 1750 + 1670 = 3420

   Cheers,
   Pavel
7. Dan Prager said

   February 5, 2012 at 8:31 PM

   A nice additional constraint to the problem — at least for Roman numerals in additive form — is to forbid conversion back to decimal for the purposes of carrying out the addition. This seems more authentic, given that conversion to decimal was not an option available to the classical Romans!

   I discuss this approach to a solution along with some other (arguably) interesting connections on my new blog. Straight to the Python code.
8. wilornel said

   January 19, 2013 at 11:28 PM

   How to chose between VIV and IX? I can’t seem to think of a way to follow this convention.
9. wilornel said

   January 20, 2013 at 4:52 AM

   In coffeescript https://gist.github.com/4576731
10. András Kovács said

    January 23, 2013 at 2:14 PM

    See my code at: https://gist.github.com/4606068
11. ftt said

    January 24, 2014 at 1:08 AM

    https://github.com/ftt/programming-praxis/blob/master/20090306-roman-numerals/roman-numerals.py