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: