15
\$\begingroup\$

Create the shortest function to convert a string of Roman numerals to an integer.

The rules for each letter can be found at the Wikipedia page. Letters above 1,000 will have parentheses placed around them to signal their higher value.

Requirements:

  • Must convert Roman numerals 1 to 500,000
  • Must complete in less than a minute
  • Does not use built-in functions that could provide an advantage (Ex: A function that converts Roman numerals to integers)
  • Is a function

The function does not need to support fractions. Any invalid input should return the number 0.

Shortest function wins. In the case of a tie, the one with the most votes wins.

Test Cases

Input

III

Output

3


Input

IIII

Output

0


Input

XVI

Output

16


Input

(C)(D)(L)MMI

Output

452001
\$\endgroup\$
6
  • 2
    \$\begingroup\$ Unless I'm missing something, (C)(D)(L)MMI would be 452,001. How did you get your value? Additionally, does this need to support "improper" forms (e.g. IC instead of XCIX)? \$\endgroup\$
    – Anon.
    Feb 10 '11 at 2:58
  • \$\begingroup\$ Improper to me means illegal and thus should return 0. \$\endgroup\$ Feb 10 '11 at 19:46
  • \$\begingroup\$ @Anon: The number was a mistype from when I changed the original third test case. It does not need to support improper forms, as it would be considered invalid input. \$\endgroup\$ Feb 10 '11 at 20:21
  • 1
    \$\begingroup\$ Standard practice (and the spec of this question's duplicate) is for invalid input to be undefined behavior. Since this question is four years old and had only one answer, should we change the requirements? \$\endgroup\$
    – lirtosiast
    Jun 4 '15 at 23:38
  • 1
    \$\begingroup\$ @KevinBrown I don't see a source or explanation for the parenthesised letters. I think you should change the spec to match codegolf.stackexchange.com/q/16254/43319 and then the answers from there can be migrated here. \$\endgroup\$
    – Adám
    Feb 14 '17 at 11:14
6
\$\begingroup\$

C++: 914 855 chars

#include<map>
#include<string>
#include<iostream>
#include<sstream>
#define I istream
#define T(C) if(C)throw int(1);
#define X(c,v,f,m) D[c]=v;P[c]=D[f];M[c]=m;
#define S second
using namespace std;typedef map<char,int>R;R D,P,M;struct U{U():t(0),l(0),a(0){}int t,l,a;operator int(){return t+l;}I&d(I&s){char c,b;s>>c;if(c=='('){s>>c>>b;T(b!=')')c+=32;}if(s){R::iterator f=D.find(c);T(f==D.end())if(P[c]==l){l=f->S-l;a=0;}else{T(l&&(f->S>l))a=l==f->S?a+1:1;T(a>M[c])t+=l;l=f->S;}}return s;}};I&operator>>(I&s,U&d){return d.d(s);}int main(){D[' ']=-1;X(73,1,32,3)X(86,5,73,1)X(88,10,73,3)X(76,50,88,1)X(67,100,88,3)X(68,500,67,1)X(77,1000,67,3)X(118,5000,77,1)X(120,10000,77,3)X(108,50000,120,1)X(99,100000,120,3)X(100,500000,99,1)X(109,1000000,99,3)string w;while(cin>>w){try{stringstream s(w);U c;while(s>>c);cout<<c<<"\n";}catch(int x){cout<<"0\n";}}}

It could be compressed further.

> ./a.exe
III
3
IIII
0
XVI
16
(C)(D)(L)MMI
452001

Slightly nicer formatting: 1582 char

#include<map>
#include<string>
#include<iostream>
#include<sstream>
#define I istream
#define T(C) if(C)throw int(1);
#define X(c,v,f,m) D[c]=v;P[c]=D[f];M[c]=m;
#define S second
using namespace std;

typedef map<char,int>      R;

R     D,P,M;

struct U
{
    U(): t(0), l(0), a(0) {}

    int  t,l,a;

    operator int()
    {
        return t + l;
    }
    I& d(I& s)
    {
        char c,b;
        s >> c;
        if (c == '(')
        {
            s >> c >> b;
            T(b != ')')
            c = tolower(c);
        }
        if (s)
        {
            R::iterator f = D.find(c);
            T(f == D.end())

            if (P[c] == l)
            {
                l = f->S - l;
                a = 0;
            }
            else
            {
                T(l&&(f->S > l))
                a=l==f->S?a+1:1;
                T(a>M[c])
                t   += l;
                l     = f->S;
            }
        }

        return s;
    }

};

I& operator>>(I& s,U& d)
{
    return d.d(s);
}

int main()
{
    D[' ']=-1;
    X(73,1,32,3)
    X(86,5,73,1)
    X(88,10,73,3)
    X(76,50,88,1)
    X(67,100,88,3)
    X(68,500,67,1)
    X(77,1000,67,3)
    X(118,5000,77,1)
    X(120,10000,77,3)
    X(108,50000,120,1)
    X(99,100000,120,3)
    X(100,500000,99,1)
    X(109,1000000,99,3)

    string w;
    while(cin >> w)
    {
        try
        {
            stringstream s(w);
            U    c;
            while(s >> c);
            cout << c << "\n";
        }
        catch(int x)
        {
            cout << "0\n";
        }
    }
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I don't think you need a space between the macro functions and their definitions. \$\endgroup\$
    – Adalynn
    Aug 12 '18 at 17:15
4
\$\begingroup\$

Javascript, 317 chars

function f(s){for(r=/\(?(.\)?)/g,t=e=0;a=r.exec(s);l=a[0].length,d='IXCMVLD'.indexOf(a[1][0]),e=e||d<0||l==2||d*4+l==3,t+='+'+(d>3?5:1)*Math.pow(10,d%4+3*(l>1)));t=t&&t.replace(/1(0*).(10|5)\1(?!0)/g,'$2$1-1$1');return e||/[^0](0*)\+(10|5)\1/.test(t)||/(\+10*)\1{3}(?!-)/.test(t)||/-(10*)\+\1(?!-)/.test(t)?0:eval(t)}

Explaination:

function f(s){
      // iterate over every character grabbing parens along the way
  for(r=/\(?(.\)?)/g,t=e=0;a=r.exec(s);    
        // get a numerical value for each numeral and join together in a string
    l=a[0].length,
    d='IXCMVLD'.indexOf(a[1][0]),
    e=e||d<0||l==2||d*4+l==3,    // find invalid characters, and parens
    t+='+'+(d>3?5:1)*Math.pow(10,d%4+3*(l>1))
  );
      // reorder and subtract to fix IV, IX and the like
  t=t&&t.replace(/1(0*).(10|5)\1(?!0)/g,'$2$1-1$1');
  return e||
    /[^0](0*)\+(10|5)\1/.test(t)|| // find VV,IIV,IC,...
    /(\+10*)\1{3}(?!-)/.test(t)||  // find IIII,... but not XXXIX
    /-(10*)\+\1(?!-)/.test(t)      // find IVI,... but not XCIX
      ?0:eval(t)
}

Without error detection it is only 180 chars

function g(s){for(r=/\(?(.\)?)/g,t=0;a=r.exec(s);d='IXCMVLD'.indexOf(a[1][0]),t+='+'+(d>3?5:1)+'0'.repeat(d%4+3*(a[1].length>1)));return eval(t.replace(/(1(0*).(10|5)\2)/g,'-$1'))}

This works the same way, but here is better formatting:

function g(s){
  for(r=/\(?(.\)?)/g,t=0;a=r.exec(s);
    d='IXCMVLD'.indexOf(a[1][0]),
    t+='+'+(d>3?5:1)+'0'.repeat(d%4+3*(a[1].length>1))
  );
  return eval(t.replace(/(1(0*).(10|5)\2)/g,'-$1'))
}
\$\endgroup\$
0
\$\begingroup\$

Python3 - 144 chars

Follows this question's rules, but its closed, so doesn't check for invalid input or support brackets, but thought I'd answer anyway.

def r(s):
    if not s:return 0
    l,v=[(s.split(x,1),6-i) for i,x in enumerate('MDCLXVI') if x in s][0]
    return 10**(v//2)*(v%2*4+1)-r(l[0])+r(l[1])

Explanation:

This algorithm recursively finds the next largest letter, splits the string around it, then subtracts the left side's value and adds the right side's value.

Ungolfed:

def roman(string):
    # base case. ends the recursion when either side string is empty.
    if not string:
        return 0

    split_list, value =
        [
            # splits the string with the leftmost letter of 'MDCLXVI' successively.
            # we take the first split string in the list (ignoring ones that didn't split)
            #  and use [0] and [1] as the left and right hand side parts to recurse.

            # stores the split string ('1' means first split only), and the index of the 
            #  letter used to split it in a tuple.
            ( string.split(letter, 1), 6-index )

            # loops through each letter used in roman numerals.
            for index, letter in enumerate('MDCLXVI')

            # only stores split strings which actually split
            if letter in string

        # get the first split string tuple (so it was split with the highest value letter).
        ][0]

    # takes the index of roman numeral letter and turns into its value (0->1, 1->5, 2->10).
    return 10**(value//2)*(value%2*4+1)
        # subtracts the value of the left hand side.
        - roman(split_list[0])
        # adds the value of the right hand side.
        + roman(split_list[1])
\$\endgroup\$
0
\$\begingroup\$

J, 43 bytes

1#.2([*_1^<)/\0,~(*/\1,6$5 2){~'IVXLCDM'&i.

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.