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.

Posted by programmingpraxis

Filed in Exercises

4 Comments »

4 Responses to “Roman Numerals, Revisited”

Felipe Ceotto said
June 3, 2014 at 11:04 AM
My C# solution from a while ago: https://gist.github.com/ceottaki/8650187

matthew said

June 3, 2014 at 7:12 PM

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

Karl Bielefeldt said

June 6, 2014 at 4:01 AM

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

David said

July 19, 2014 at 5:55 PM

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>

Programming Praxis