# Subtracting, the old-fashioned way

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)

-
IX is invalid? Those aren't Roman numerals then, are they? – leftaroundabout May 29 '12 at 13:59
@leftaroundabout Depending on the era and convention of use, IX is valid in some (most) cases, but I am excluding it from this challenge. – Gaffi May 29 '12 at 14:30
VIIII was sometimes used, sometimes not, but IX is usually always valid in every usage. – vsz May 30 '12 at 6:09
Your last example has a + instead of a - – Hasturkun May 30 '12 at 10:56
IV is generally used in place of IIII. – ObsessiveSSOℲ Jul 9 '12 at 20:09

## 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.

-
 +1 for the tounge-in-cheekiness of this. :-) – Gaffi May 29 '12 at 21:15 @Gaffi: Thanks, but I guess I have to solve the NULL-constraint too. My first idea was that it would only be a few characters, but ... - more than I thought. – user unknown May 29 '12 at 21:27

### 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
-
 Your solution uses binary numbers for most calculations. If I read the spec correctly, a sumbission must be entirely free of direct arithmetic since that is nearly always implemented in binary. – FUZxxl Jun 6 '12 at 16:59

## 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

-

## 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/-*;.*\$//;
-

## 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
-

## 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;}
-

## 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)
-

## 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"
-

### Ruby, 98 chars

p \$*.map{|e|e.split(//).map{|c|[1,5,10,50,100,1000]['IVXLCDM'.index c]}.inject(:+)}.inject(:-)

I like the smile at the end :-)

Console:

.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`--> wc -c golf.rb
98 golf.rb
.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`-->  ruby ./golf.rb XVII VI
11
-
The output should be "XI" in your example. Plus, I'll have to look into it since I'm not super familiar with Ruby, but you're using numbers in your map{|c|[1,5..., which leads me to think you're working outside the scope of this challenge. – Gaffi Jul 14 '12 at 17:46
@Gaffi: You are right he is converting to the number. – Hynek -Pichi- Vychodil Apr 15 at 21:06