Roman Numerals, Revisited
June 3, 2014
We studied the problem of converting between integers and roman numerals in a previous exercise. We’ll do it again today because it’s a fun exercise, it appears frequently in lists of interview questions, we have an improved algorithm, and it lets us highlight a useful piece of the Standard Prelude.
Your task is to write functions that convert an integer to its equivalent in roman numerals and vice versa. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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>