Subtracting, the old-fashioned way

Question

Overview
Adding slightly to the complexity of working with Roman numerals... 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 sold 27 of them, 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 subtract 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.

• Since we are subtracting, negative numbers are permissible. 0s, as they have no representation in the Roman system, should be returned as NULL or an empty string.
• 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.

I do have a solution to this problem that has already been beaten, but I'll hold off on posting it for a few days to see if any other answers come up.

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 = IIII (12 - 8 = 4)
MCCXXII - MCCXXII = '' (2,222 - 2,222 = 0)
XXIIII - XXXXII = -XVIII (24 - 42 = -18)

If any further clarification is needed, please ask.

Answer 1

sed 144

Most of you will know this little episode from roman times, when Cesar invented the Cesar crypting (aka rot13) using SED.

As a big fanatic of SED, he printed the most common used commands: substitute, print, quit and read (SPQR) on signs which he carried with him to teach his soldiers the use of SED.

#  63 = sed-file
#  81 = this
# 144 summa summarum
tac a|rev|sed y/gs/sg/ >b
echo $1|sed -f a|sed "s/$(echo $2|sed -f a)//"|sed -f b

first version 181:

# 126 = 2 sed-files =126
#  55 = this
# 181 summa summarum 
echo $1|sed -f a|sed "s/$(echo $2|sed -f a)//"|sed -f b

2 files to use which count to the solution:

a:

s/M/DD/g
s/D/CCCCC/g
s/C/LL/g
s/L/XXXXX/g
s/X/VV/g
s/V/IIIII/g

b:

s/IIIII/V/g
s/VV/X/g
s/XXXXX/L/g
s/LL/C/g
s/CCCCC/D/g
s/DD/M/g

but b can be produced with the first line of the new solution from a: it is - more or less - the inverse, and so we read the file from bottom to top (tac) and from right to left (rev), and switch s and g which are now in the wrong order.

Invocation:

./cg-6061-roman-minus.sh MDCCCCLXV LXVI 
MDCCCLXXXXVIIII

I guess I can golf this further, but I liked to occupy wallstreet the sed slot. :)

Since the logic isn't only in the sed files, but in the invocation too, I sum it all up. It could be argued about echo $1, but what about the nested $2? Let's just sum it together.

The sedfiles are pretty long and very redundant in their structure. There seems to be room for optimization.

Luckily, the romans already had QVANTVM <OMPVTVVMZ, so they didn't care for the otherwise lousy performance.

tl;dr:

I convert both numbers into church numerals (IIIIII=6), remove the second from the first, and reconvert the result back.

s.e.d. - sod errat demonstrandum.

Answer 2

Ruby, 112 characters

Using the same idea - but considerably longer than the add-version:

f=->a,b{r=0;v=5;n="IVXLCDM".gsub(/./){|g|r+=a.count(g)-b.count(g);t=r%v;r/=v;v^=7;g*t}.reverse;r<0?"-"+f[b,a]:n}

It is an implementation as a function. Takes two strings and returns the result when subtracting the second from the first. Examples:

puts f["XII", "VIII"]          # -> IIII
puts f["MCCXXII", "MCCXXII"]   # -> 
puts f["XXIIII", "XXXXII"]     # -> -XVIII

Answer 3

Sed, 146 chars

:;s/M/DD/;s/D/CCCCC/;s/C/LL/;s/L/XXXXX/;s/X/VV/;s/V/IIIII/;t;s/\(I\+\)-\1/-/;:a;s/IIIII/V/;s/VV/X/;s/XXXXX/L/;s/LL/C/;s/CCCCC/D/;s/DD/M/;ta;s/-$//

This is a pure sed implementation. Input is expected to be in the following format, with no spaces

XXIIII-XXXXII

It outputs negative values correctly, and prints zeros as empty strings.

still trying to shave a bit off the code without resorting to using extended regexps

Answer 4

Sed, 154 chars

This is a table driven implementation, correctly outputs negative numbers. expects input in the form of V-VI

s/$/;,MDD,DCCCCC,CLL,LXXXXX,XVV,VIIIII,/;:;s/\([^;]\)\(.*;.*,\1\([^,]\+\),\)/\3\2/;t;s/\(I*\)-\1/-/;:b;s/\([^;]\+\)\(.*;.*,\(.\)\1,\)/\3\2/;tb;s/-*;.*$//;

Answer 5

VBA - 396

Function s(f,c)
a=Split("I,V,X,L,C,D,M",",")
For i=6 To 0 Step -1
x=Replace(f,a(i),""):y=Replace(c,a(i),""):m=Len(f)-Len(x):n=Len(c)-Len(y)
If b=0 Then b=IIf(m>=n,IIf(m=n,0,1),2)
Next
q=f:p=c
If b=1 Then:p=f:q=c
For i=0 To 6
x=Replace(p,a(i),"")
y=Replace(q,a(i),"")
t=(Len(p)-Len(x)-u)-(Len(q)-Len(y))
r=IIf(i Mod 2,2,5)
u=IIf(t<0,1,0)
t=IIf(t<0,t+r,t)
s=String(t,a(i)) & s
Next
If b=2 Then s="-" & s
End Function

Answer 6

Erlang 392

-module(r).
-export([s/2,n/1]).
e(L)->[Y||X<-L,Y<-t([X])].
-define(T(A,B),t(??A)->e(??B);).
?T(M,DD)?T(D,CCCCC)?T(C,LL)?T(L,XXXXX)?T(X,VV)?T(V,IIIII)t(L)->L.
s([H|A],[H|B])->s(A,B);s(R,[])->n(R);s([],R)->[$-|n(R)];s(A,B)->s(e(A),e(B)).
n(L)->d(c(l(x(v(i(L)))))).
-define(E(F,A,B),F(??A++X)->??B++F(X);F(X)->X).
?E(i,IIIII,V).
?E(v,VV,X).
?E(x,XXXXX,L).
?E(l,LL,C).
?E(c,CCCCC,D).
?E(d,DD,M).

Usage:

1> c(r).                                      
{ok,r}
2> r:s("XXIIII","XXXXII").
"-XVIII"
3> r:s("MCCXXII","MCCXXII").
[]
4> r:s("XII","VIII").       
"IIII"

Answer 7

JavaScript 276

I honestly thought I could make this smaller... Alas, not as easy as one might think... I'd appreciate any help with reducing this even further...

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

Answer 8

C++ 581 478

#define A [j]==a[i]?
#define B for(j=0;j<
#define C .length();j++){
#define E 1:0)
#include <iostream>
int main(){int b=0,m=0,n=0,k,l,j,i,u=0,r,t;std::string x,y,q,p,s,a="IVXLCDM";std::cin>>x>>y;for(i=6;i>=0;i--){B x C m+=(x A E;}B y C n+=(y A E;}b=(b==0?(m>=n?(m!=n?E:2):b);}if(b==1){p=x;q=y;}else{p=y;q=x;}for(i=0;i<7;i++){k=0;l=0;B p C k+=(p A E;}B q C l+=(q A E;}t=(k-u)-l;r=(i%2?2:5);u=(t<0?E;t=(t<0?t+r:t);B t;j++){s=a[i]+s;}}s=(b==2?"-"+s:s);std::cout<<s<<"\n";return 0;}

Answer 9

Python 3, 401

This is a port of my VBA solution, and the length makes me think I need to learn some more about Python. :-/

a="IVXLCDM"
f=input()
c=input()
g=range
s=x=y=z=""
b=u=0
for i in g(6,-1,-1):x,y=f.replace(a[i],z),c.replace(a[i],z);m=len(f)-len(x);n=len(c)-len(y);b=b if(b!=0)else 0 if(m==n)else 1 if(m>n)else 2
q,p=f,c
if(b==1):p,q=f,c
for i in g(7):
 x,y=p.replace(a[i],z),q.replace(a[i],z);t=(len(p)-len(x)-u)-(len(q)-len(y));r=2 if(i%2)else 5;u=1 if(t<0)else 0
 if(t<0):t+=r
 s=a[i]*t+s
if(b==2):s="-"+s
print(s)