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.

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 615 other followers

%d bloggers like this: