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:
#include <stdio.h> #include <assert.h> template<char M, int N> static inline const char *scan1(const char *p, int &total) { while (*p == M) { p++; total += N; } return p; } template<char I, char V, char X, int N> static inline const char *scan3(const char *p, int &total) { if (*p == V) { p++; total += 5*N; goto ones; } if (*p == I) { p++; if (*p == X) { p++; total += 9*N; } else if (*p == V) { p++; total += 4*N; } else { total += N; ones: while (*p == I) { p++; total += N; } } } return p; } int fromroman(const char *p) { int total = 0; p = scan1<'M',1000>(p,total); p = scan3<'C','D','M',100>(p,total); p = scan3<'X','L','C',10>(p,total); p = scan3<'I','V','X',1>(p,total); if (*p != 0) fprintf(stderr,"Invalid input at '%s'\n", p); return total; } template<char M, int N> static inline char *put1(char *p, int &n) { while(n >= N) { *p++ = M; n -= N; } return p; } template<char I, char V, char X, int N> static inline char *put3(char *p, int &n, bool t = true) { if (t && n >= 9*N) { *p++ = I; *p++ = X; n -= 9*N; } if (n >= 5*N) { *p++ = V; n -= 5*N; } if (t && n >= 4*N) { *p++ = I; *p++ = V; n -= 4*N; } while (n >= N) { *p++ = I; n -= N; } return p; } void toroman(char *p, int n, bool t = true) { p = put1<'M',1000>(p,n); p = put3<'C','D','M',100>(p,n,t); p = put3<'X','L','C',10>(p,n,t); p = put3<'I','V','X',1>(p,n,t); *p++ = 0; } int main(int argc, char *argv[]) { char buffer[32]; for (int i = 0; i <= 2000; i++) { toroman(buffer, i); int j = fromroman(buffer); printf("%d %d %s\n", i, j, buffer); assert(i == j); toroman(buffer, i, false); j = fromroman(buffer); printf("%d %d %s\n", i, j, buffer); assert(i == j); } }Here’s my Scala solution.
def romanToInt(roman: String) = { val digits = roman map Map( 'M' -> 1000, 'D' -> 500, 'C' -> 100, 'L' -> 50, 'X' -> 10, 'V' -> 5, 'I' -> 1) val (prev, total) = digits.foldLeft((1001, 0)){ case ((prev, total), digit) => if (digit > prev) (digit, total + digit - 2 * prev) else (digit, total + digit) } total } def intToRoman(number: Int): String = { if (number <= 0) return "" val conversions = List( (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")) val (decimal, roman) = (conversions dropWhile (_._1 > number)).head roman + intToRoman(number - decimal) }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.)
-module(roman). -export([to_int/1, from_int/1, test/0]). to_int(Str) -> roman_int(Str, 0). roman_int([], N) -> N; roman_int([$M | Rest], N) -> roman_int(Rest, N + 1000); roman_int([$C,$M | Rest], N) -> roman_int(Rest, N + 900); roman_int([$D | Rest], N) -> roman_int(Rest, N + 500); roman_int([$C,$D | Rest], N) -> roman_int(Rest, N + 400); roman_int([$C | Rest], N) -> roman_int(Rest, N + 100); roman_int([$X,$C | Rest], N) -> roman_int(Rest, N + 90); roman_int([$L | Rest], N) -> roman_int(Rest, N + 50); roman_int([$X,$L | Rest], N) -> roman_int(Rest, N + 40); roman_int([$X | Rest], N) -> roman_int(Rest, N + 10); roman_int([$I,$X | Rest], N) -> roman_int(Rest, N + 9); roman_int([$V | Rest], N) -> roman_int(Rest, N + 5); roman_int([$I,$V | Rest], N) -> roman_int(Rest, N + 4); roman_int([$I | Rest], N) -> roman_int(Rest, N + 1). from_int(N) -> int_roman(N, ""). int_roman(0, Str) -> lists:reverse(Str); int_roman(N, Str) when N >= 1000 -> int_roman(N - 1000, [$M | Str]); int_roman(N, Str) when N >= 900 -> int_roman(N - 900, [$M,$C | Str]); int_roman(N, Str) when N >= 500 -> int_roman(N - 500, [$D | Str]); int_roman(N, Str) when N >= 400 -> int_roman(N - 400, [$D,$C | Str]); int_roman(N, Str) when N >= 100 -> int_roman(N - 100, [$C | Str]); int_roman(N, Str) when N >= 90 -> int_roman(N - 90, [$C,$X | Str]); int_roman(N, Str) when N >= 50 -> int_roman(N - 50, [$L | Str]); int_roman(N, Str) when N >= 40 -> int_roman(N - 40, [$L,$X | Str]); int_roman(N, Str) when N >= 10 -> int_roman(N - 10, [$X | Str]); int_roman(N, Str) when N >= 9 -> int_roman(N - 9, [$X,$I | Str]); int_roman(N, Str) when N >= 5 -> int_roman(N - 5, [$V | Str]); int_roman(N, Str) when N >= 4 -> int_roman(N - 4, [$V,$I | Str]); int_roman(N, Str) when N >= 1 -> int_roman(N - 1, [$I | Str]). test() -> test(3000). test(0) -> ok; test(K) -> K = to_int(from_int(K)), test(K-1).Erlang command shell:
25> c(roman). {ok,roman} 26> roman:test(). ok 27> roman:from_int(1975). "MCMLXXV" 28> roman:to_int("MCMXLVI"). 1946 29>