8
\$\begingroup\$

Overview
The ancient Romans devised a number system using Latin letters, which served them well, and which is still used by modern civilization, though to a much smaller degree. In the time of its use, Romans would have had to learn to use and manipulate these numbers in order to be of much use for many applications. For example, if a man owned 35 oxen, and he procured 27 more, how would he know the new total other than counting them all? (Ok, that and using an abacus...) If the Romans could do it, surely we can figure it out as well.

Objective
Write the shortest algorithm/function/program that will add two Roman numerals together and output the result without converting the string representation of either input into a number.

Rules/Constraints
Because of historical/pre-medieval inconsistencies in formatting, I'm going to outline some non-standard (per modern usage) rules for orthography. See the value guide below as an example.

  • The letters I, X, C, and M can be repeated up to four times in succession, but no more. D, L, and V can never be repeated.
  • The letter immediately to the right of another letter in the Roman representation will be of the same or lesser value than that to its left.
    • In other words, VIIII == 9 but IX != 9 and is invalid/not allowed.
  • All input values will be 2,000 (MM) or less; no representation for numbers greater than M is necessary.
  • All input values will be a valid Roman numeral, pursuant to the rules above.
  • You may not convert any numbers to decimal, binary, or any other number system as part of your solution (you are welcome to use such a method to VERIFY your results).
  • This is code golf, so shortest code wins.

Value Guide

Symbol        Value
I             1
II            2
III           3
IIII          4
V             5
VIIII         9
X             10
XIIII         14
XXXXIIII      44
L             50
LXXXXVIIII    99
C             100
D             500
M             1,000

Examples

XII + VIII = XX (12 + 8 = 20)
MCCXXII + MCCXXII = MMCCCCXXXXIIII (1,222 + 1,222 = 2,444)
XXIIII + XXXXII = LXVI (24 + 42 = 66)

If any further clarification is needed, please ask.

\$\endgroup\$
  • 2
    \$\begingroup\$ XXXXIIII -> 44 or XIIII -> 14? \$\endgroup\$ – Paul Richter May 28 '12 at 5:37
  • 1
    \$\begingroup\$ I think he's referring to a mistake in the value guide. \$\endgroup\$ – grc May 28 '12 at 6:02
  • \$\begingroup\$ @grc Oh. Silly me... Fixed. \$\endgroup\$ – Gaffi May 28 '12 at 6:04
  • 1
    \$\begingroup\$ Why would anyone want to convert to a different base? Did you actually mean to prohibit parsing the string to a number? \$\endgroup\$ – Peter Taylor May 28 '12 at 21:45
  • \$\begingroup\$ @PeterTaylor Yes, that is correct. \$\endgroup\$ – Gaffi May 28 '12 at 23:58

12 Answers 12

5
\$\begingroup\$

APL (59 56)

,/N⍴⍨¨{∨/K←⍵≥D←7⍴5 2:∇⍵+(1⌽K)-K×D⋄⍵}⊃+/(N←'MDCLXVI')∘=¨⍞

Input on one line (i.e. XII + XII, though the + is not necessary).

Edit: changed shift to rotate to save three characters - it only matters when the answer ≥ 5000, which should never happen as the question says the input values will always be ≤ 2000. The only effect is it now "overflows" at 5000, giving 5000=1, 5001=2, etc.

(I don't really think the Romans did it this way... APL is more something for Ancient Egyptians I think :) )

Explanation:

  • : get user input
  • (N←'MDCLXVI')∘=¨: store 'MDCLXVI' in N. Return, for each character of the input string, a vector with a 1 in the place where the character corresponds to one of 'MDCLXVI', and 0 otherwise.
  • ⊃+/: Sum the vectors and de-encapsulate. We now have a vector with information about how many of each Roman numeral we have. I.e, if the input was XXII XIIII, we now have:
     M D C L X V I
     0 0 0 0 3 0 6
  • Note that this is not converting the values.
  • {...:......} is a function with an if-else construct.
  • D←7⍴5 2: D is the vector 5 2 5 2 5 2 5. This is how many of a Roman numeral are not allowed. I.e. if you have 5 Is, that's too many, and if you have 2 Vs that's also too many. This vector also happens to be the multiplication factor for each Roman numeral, i.e. a V is worth 5 Is and an X is worth 2 Vs.

  • ∨/K←⍵≥D: K is the vector where there's a 1 if we have too many Roman numerals of a certain kind. ∨/ ORs this vector together.

  • If this vector is not all zeroes:
  • K×D: Multiply K by D. This vector has zeroes where we don't have too many Roman numerals, and the amount of Roman numerals where we do.
  • ⍵+(1⌽K): Rotate K to the left by 1, and add it to the input. For each Roman numeral we have too many, this will add one of the next-higher one.
  • ⍵+(1⌽K)-K×D: Subtract this from the other vector. The effect is, for example if you have 6 Is, it will add one V and remove 4 Is.
  • : Recurse.
  • ⋄⍵: But if K was all zeroes, then ⍵ represents a valid Roman numeral, so return ⍵.
  • N⍴⍨¨: For each element of the resulting vector, create that many of the corresponding Roman numeral.
  • ,/: Join these vectors together to get rid of the ugly spaces in the output.
\$\endgroup\$
5
\$\begingroup\$

Python, 100

s="IVXLCDM"
r=raw_input()
a=""
i=2
u=0
for c in s:r+=u/i*c;i=7-i;u=r.count(c);a+=u%i*c
print a[::-1]

Takes one string from input (e.g. VIII + XII or VIII + XII =).

\$\endgroup\$
3
\$\begingroup\$

Perl, 132 chars

sub s{@a=VXLCDM=~/./g;@z=(IIIII,VV,XXXXX,LL,CCCCC,DD);$r=join"",@_;
$r=~s/$a[-$_]/$z[-$_]/gfor-5..0;$r=~s/$z[$_]/$a[$_]/gfor 0..5;$r}

Declares function s which takes any number of arguments and sums them. Pretty straightforward: it appends the input, reduces everything to Is and then immediately restores the Roman numerals. (Hopefully this doesn't count as using the unary number system!)

\$\endgroup\$
3
\$\begingroup\$

Ruby, 85 82 characters

gets;r=0;v=5;puts"IVXLCDM".gsub(/./){|g|r+=$_.count g;t=r%v;r/=v;v^=7;g*t}.reverse

This version takes input on STDIN as a single string (e.g. XXIIII + XXXXII) and prints output to STDOUT.

f=->*a{r=0;v=5;"IVXLCDM".gsub(/./){|g|r+=(a*'').count g;t=r%v;r/=v;v^=7;g*t}.reverse}

The second one is an implementation as a function. Takes two (or more) strings and returns the summed values. Usage:

puts f["XXIIII", "XXXXII"]     # -> LXVI
\$\endgroup\$
3
\$\begingroup\$

GNU Sed, 131 chars

:;s/M/DD/;s/D/CCCCC/;s/C/LL/;s/L/XXXXX/;s/X/VV/;s/V/IIIII/;t;s/\W//g;:b;s/IIIII/V/;s/VV/X/;s/XXXXX/L/;s/LL/C/;s/CCCCC/D/;s/DD/M/;tb
\$\endgroup\$
1
\$\begingroup\$

Python, 174 chars

A very simple algorithm - count each digit, loop to handle overflow to the next, print.
Reads from standard input. Something like XVI + CXX would work (ignores anything except numerals, so the + isn't really needed).

x="IVXLCDM"
i=raw_input()
d=dict((c,i.count(c))for c in x)
for c in x:
    n=2+3*(c in x[::2])
    if d[c]>=n:d[c]-=n;d[x[x.find(c)+1]]+=1
print"".join(c*d[c]for c in reversed(x))
\$\endgroup\$
1
\$\begingroup\$

Scala 150

val c="IVXLCDM"
def a(t:String,u:String)=((t+u).sortBy(7-c.indexOf(_))/:c.init)((s,z)=>{val i=c.indexOf(z)+1
s.replaceAll((""+z)*(2+i%2*3),""+c(i))})

invocation:

a("MDCCCCLXXXXVIIII", "MDCCCCLXXXXVIIII")

ungolfed Version:

val c = "IVXLCDM"
def add (t:String, u:String) = (
  (t+u).  // "MDCCCCLXXXXVIIIIMDCCCCLXXXXVIIII"
  sortBy(7-c.indexOf(_)) // MMDDCCCCCCCCLLXXXXXXXXVVIIIIIIII
  /: // left-fold operator to be used: (start /: rest) ((a,b)=> f (a,b)) 
  c.init) /* init is everything except the rest, so c.init = "IVXLCD"
    (because M has no follower to be replaced with */
  ((s, z) => { /* the left fold produces 2 elements in each step, 
    and the result is repeatedly s, on initialisation 
    MMDDCCCCCCCCLLXXXXXXXXVVIIIIIIII 
    and z is the iterated element from c.init, namely I, V, X, L, C, D
    in sequence */
    val i = c.indexOf (z) + 1 // 1, 2, ..., 7
    /* i % 2 produces 1 0 1 0 1 0
       *3 => 3 0 3 0 
       +2 => 5 2 5 2 
       (""+ 'I') * 5 is "IIIII", ("" + 'V') * 2 is "VV", ...
       ""+c(i) is "V", "X", ...
    */ 
    s.replaceAll (("" + z) * (2+i%2*3), "" + c (i))
    }
  )
\$\endgroup\$
1
\$\begingroup\$

JavaScript 195 179

My system is fairly rudimentary, reduce all Roman numerals to a series of I for both numbers, join them up and then reverse the process turning certain blocks of I into their respective larger versions...

Iteration 1 a="IIIII0VV0XXXXX0LL0CCCCC0DD0M".split(0);d=b=>x.replace(g=RegExp((c=z)>b?a[c][0]:a[c],"g"),c>b?a[b]:a[b][0]);x=prompt().replace("+","");for(z=6;0<z;z--)x=d(z-1);for(z=0;6>z;z++)x=d(z+1);alert(x)

Iteration 2 a="IIIII0VV0XXXXX0LL0CCCCC0DD0M".split(0);x=prompt().replace("+","");for(z=-6;6>z;z++)b=0>z?-z:z,c=0>z?~z:z+1,x=x.replace(g=RegExp(b>c?a[b][0]:a[b],"g"),b>c?a[c]:a[c][0]);alert(x)

Features:

  • Zero delimited array string, quicker than setting up a string array.
  • Reduced the two recursions to the one, and recalculating the parameters for the specific regex.
  • More ternary operators than you can poke a stick at!

Input is entered via prompt in the form of <first roman number>+<second roman number> (no spaces), output in the form of an alert.

e.g.

XVI+VII // alert shows XXIII, correct!
MCCXXXIIII+DCCLXVI // alert shows MM, also correct!
\$\endgroup\$
1
\$\begingroup\$

VBA, 187 chars

Function c(f,s)
a=Split("I,V,X,L,C,D,M",",")
z=f & s
For i=0 To 6
x=Replace(z,a(i),"")
n=Len(z)-Len(x)+m
r=IIf(i Mod 2,2,5)
o=n Mod r
m=Int(n/r)
c=String(o,a(i)) & c
z=x
Next
End Function
\$\endgroup\$
  • \$\begingroup\$ As o is only used once, you cans save 3 bytes by removing the assignment and evaluation of it and plugging n Mod r Directly into the String( function call \$\endgroup\$ – Taylor Scott May 31 '17 at 15:29
1
\$\begingroup\$

JavaScript, 190

x=prompt(r=[]);p=RegExp;s="MDCLXVI";for(i=-1;++i<7;){u=x.match(new p(s[i],'g'));if(u)r=r.concat(u)};for(r=r.join("");--i>0;){r=r.replace(new p(s[i]+'{'+(i%2==0?5:2)+'}','g'),s[i-1])}alert(r)

Putting some instruction inside the third slot of the for operator let me save some semicolons!

When the input prompts, you insert the two numbers (the + and spaces are not necessary, but if you put them you don't get an error). Then the alert show you the sum.

\$\endgroup\$
0
\$\begingroup\$

C++, 319 chars

#define A for(j=0;j<
#define B .length();j++){ 
#define C [j]==a[i]?1:0);}
#include <iostream>
int main(){std::string x,y,s,a="IVXLCDM";int i,j,k,l,m=0,n;std::cin>>x>>y;for(i=0;i<7;i++){k=0;l=0;A x B k+=(x C A y B l+=(y C n=k+l+m;m=(n)%(i%2?2:5);for(j=0;j<m;j++){s=a[i]+s;}m=(n)/(i%2?2:5);}std::cout<<s<<"\n";return 0;}
\$\endgroup\$
0
\$\begingroup\$

PHP, 136 Bytes

for($r=join($argv);$c=($n=IVXLCDM)[$i];$r.=$p($n[++$i],$z/$d))$t=($p=str_repeat)($c,($z=substr_count($r,$c))%($d="52"[$i&1])).$t;echo$t;

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.