## 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.

Pages: 1 2

### 4 Responses to “Roman Numerals, Revisited”

1. Felipe Ceotto said

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

2. matthew said

“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);
}

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;
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);
}
}
```
3. 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) =

roman + intToRoman(number - decimal)
}
```
4. David said

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>
```