## Roman Numerals, Revisited

### June 3, 2014

To convert an integer to a roman numeral, index through a list of roman numerals in descending order, adding the roman numeral to the accumulating output whenever it is less than the remaining integer. We handle two-character subtractive sequences as if they were a single number, adding the characters to the output in reverse order:

`(define (integer->roman n)`

(let loop ((n n) (nums '((1000 #\M) (900 #\M #\C)

(500 #\D) (400 #\D #\C) (100 #\C) (90 #\C #\X)

(50 #\L) (40 #\L #\X) (10 #\X) (9 #\X #\I)

(5 #\V) (4 #\V #\I) (1 #\I))) (xs '()))

(cond ((zero? n) (list->string (reverse xs)))

((<= (caar nums) n)

(loop (- n (caar nums))

nums (append (cdar nums) xs)))

(else (loop n (cdr nums) xs)))))

You might want to compare this code to the code of the previous exercise and contemplate how a small change in the structure of the data can lead to such a large simplification in the structure of the algorithm.

The inverse function uses the pattern-matching macro of the Standard Prelude:

`(define (roman->integer str)`

(let loop ((cs (string->list str)) (n 0))

(list-match cs

(() n)

((#\M. rest) (loop rest (+ n 1000)))

((#\C #\M . rest) (loop rest (+ n 900)))

((#\D . rest) (loop rest (+ n 500)))

((#\C #\D . rest) (loop rest (+ n 400)))

((#\C . rest) (loop rest (+ n 100)))

((#\X #\C . rest) (loop rest (+ n 90)))

((#\L . rest) (loop rest (+ n 50)))

((#\X #\L . rest) (loop rest (+ n 40)))

((#\X . rest) (loop rest (+ n 10)))

((#\I #\X . rest) (loop rest (+ n 9)))

((#\V . rest) (loop rest (+ n 5)))

((#\I #\V . rest) (loop rest (+ n 4)))

((#\I . rest) (loop rest (+ n 1)))

(else (error 'roman->integer "invalid character")))))

Again, a small change in the algorithm makes a large change in the readability of the code. Here we check that the two functions are inverses of each other, using the assert macro from the Standard Prelude:

`> (do ((i 1 (+ i 1))) ((= i 5000))`

(assert i (roman->integer (integer->roman i))))

You can run the program at http://programmingpraxis.codepad.org/tAMHXbsq.

My C# solution from a while ago: https://gist.github.com/ceottaki/8650187

“Standard” Roman numerals follow the regular expression:

M*((D?C*)|CM|CD)?((L?X*)|XC|XL)?((V?I*)|IX|IV)?

& we can write a simple recognizer, using templates to take advantage of the similarity of the 100s, 10s and 1s parts:

Here’s my Scala solution.

Explicit pattern matching and guards in Erlang make this really easy. The “=” operator in the test function behaves like an assert macro (if the two terms don’t match it throws a run-time exception.)

Erlang command shell: