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.

About these ads

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);
      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);
      }
    }
    
  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) = 
        (conversions dropWhile (_._1 > number)).head
    
      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> 
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 628 other followers

%d bloggers like this: