## Roman Numerals

### March 6, 2009

Our first function converts a Roman numeral to its numeric equivalent by indexing through the string, adding the decoded value of the current character, and subtracting double the prior value (since it was already added once, it must be subtracted twice) if a higher-value character follows a lower-value character:

`(define (roman->number roman)`

(let ((romans '((#\M 1000) (#\D 500) (#\C 100) (#\L 50) (#\X 10) (#\V 5) (#\I 1))))

(let loop ((roman (map char-upcase (string->list roman))) (prior 10000) (number 0))

(cond ((null? roman) number)

((< prior (cadr (assoc (car roman) romans)))

(loop (cdr roman)

10000

(+ number (cadr (assoc (car roman) romans)) (* prior -2))))

(else (loop (cdr roman)

(cadr (assoc (car roman) romans))

(+ number (cadr (assoc (car roman) romans)))))))))

Our second function goes in the other direction. It was written by Dorai Sitaram, contributed to SLIB, and stolen (as Pablo Picasso said, “Good artists copy. Great artists steal.” Don’t worry — the file header in `format.scm`

indicates the code is in the public domain.) by us for this exercise:

`(define (number->roman n)`

(if (and (integer? n) (> n 0))

(let loop ((n n)

(romans '((1000 #\M) (500 #\D) (100 #\C) (50 #\L) (10 #\X) (5 #\V) (1 #\I)))

(boundaries '(100 100 10 10 1 1 #f))

(s '()))

(if (null? romans)

(list->string (reverse s))

(let ((roman-val (caar romans))

(roman-dgt (cadar romans))

(bdry (car boundaries)))

(let loop2 ((q (quotient n roman-val))

(r (remainder n roman-val))

(s s))

(if (= q 0)

(if (and bdry (>= r (- roman-val bdry)))

(loop (remainder r bdry) (cdr romans)

(cdr boundaries)

(cons roman-dgt

(append

(cdr (assv bdry romans))

s)))

(loop r (cdr romans) (cdr boundaries) s))

(loop2 (- q 1) r (cons roman-dgt s)))))))

(error 'number->roman "only positive integers can be romanized"))))

Then `add-roman`

converts its input arguments from Roman numerals, adds them, and converts the result back to a Roman numeral:

`(define (add-roman . xs)`

(number->roman (apply +

(map roman->number xs)))

Note that `add-roman`

takes any number of arguments, not necessarily two. It is available at http://programmingpraxis.codepad.org/FxDMoASG:

`> (add-roman "CCCLXIX" "CDXLVIII")`

"DCCCXVII"

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.

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

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

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.

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 :

Some use cases :

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

So here is my solution in Python:

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

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.

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

In coffeescript https://gist.github.com/4576731

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

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