Translating Roman numerals into Arabic ones

Question

I have built a predicate, which converts Roman numerals into Arabic ones. The only problem is that the predicate is limited: if I want to convert more than 3 Arabic numerals at once it does not work anymore.

This is how the predicate should work:

?- convert([v,i,i],Arabic).
Arabic = 7.

My solution so far:

tran([],0).
tran(i,1).
tran(v,5).
tran(x,10).

convert([],X) :- X is 0, !.
convert([T],X) :- tran(T,E), X is E,!.
convert([T|Ts],X) :- tran(T,E), tran(Ts,Es), X is E+Es,!.
convert([T,Ts,Tss],X) :- tran(T,E), tran(Ts,Es), tran(Tss,Ess), X is E+Es+Ess.

I know why the predicate does not work with more than 3 numerals and I could also expand the convert-predicate, but with the same pattern as shown above.

How can I make the convert-predicate more "general" (so that it could work independently of the number of numerals)? Or do you have other ideas how to write the predicate? Thanks :)

Answer 1

I haven't tested this too much, but I've tried it on several numbers and it seems to work.

The code obeys "subtractive pair rule", described, for example, at https://projecteuler.net/about=roman_numerals

The code uses "accumulator" technique to pass information what was the sum of digits seen before. Initial call just sets the accumulator to 0.

digit(i, 1).
digit(v, 5).
digit(x, 10).
digit(l, 50).
digit(c, 100).
digit(d, 500).
digit(m, 1000).

convert(Roman, Arabic) :-
    convert(Roman, 0, Arabic).

convert([], Acc, Acc).

convert([A], Acc, Arabic) :-
    digit(A, AVal),
    Arabic is Acc + AVal.

convert([A, B | Rest], Acc, Arabic) :-
    digit(A, AVal), digit(B, BVal),
    AVal < BVal,
    NewAcc is Acc + BVal - AVal,
    convert(Rest, NewAcc, Arabic).

convert([A, B | Rest], Acc, Arabic) :-
    digit(A, AVal), digit(B, BVal),
    AVal >= BVal,
    NewAcc is Acc + AVal,
    convert([B | Rest], NewAcc, Arabic).

Some tests:

convert([v, i, i], Arabic).
Arabic = 7 

?- convert([x, i, x], Arabic).
Arabic = 19 

?- convert([m, d, c, v, i], Arabic).
Arabic = 1606 

It's probably possible to write a predicate convert that works both ways in true Prolog spirit using constraint programming, but I haven't tried this approach.

Answer 2

It might help if you consider the number of discrete "digits" in the Roman numbering system is more than just I, X and V, viz:

roman( "M"   , 1000 ) .
roman( "CM"  ,  900 ) .
roman( "D"   ,  500 ) .
roman( "CD"  ,  400 ) .
roman( "C"   ,  100 ) .
roman( "XC"  ,   90 ) .
roman( "L"   ,   50 ) .
roman( "XL"  ,   40 ) .
roman( "X"   ,   10 ) .
roman( "IX"  ,    9 ) .
roman( "V"   ,    5 ) .
roman( "IV"  ,    4 ) .
roman( "I"   ,    1 ) .

Then you can write something like

roman_to_decimal( R , D ) :-
  roman_to_decimal( R , 0 , D )
  .

roman_to_decimal( [] , D , D ) :- .
roman_to_decimal( R  , T , D ) :-
  roman(P,V) ,
  append(P,S,R) ,
  ! ,
  T1 is T+V ,
  roman_to_decimal(S,T1,D)
  .

Invoke it as

roman_to_decimal( "MCM" , D ) .

This does have some shortcomings, to whit:

• It doesn't enforce syntax: the Roman numbering system required the discrete components to be ordered left-to-right in descending order of value. This doesn't take that into consideration.

• It doesn't take into account the many variations. Should 999 be represented as the compact IM or as the rather more verborse CMXCIX?

Answer 3

Just to add a variant to the mix, this version uses the scheme in Sergey's answer (which also allows more arbitrary subtractive sequences), and allows a more human-readable input like Nicholas' answer.

numeral('I', 1).
numeral('V', 5).
numeral('X', 10).
numeral('L', 50).
numeral('C', 100).
numeral('D', 100).
numeral('M', 1000).

r2n(R, N) :-
    char_code(A, R),
    lower_upper(A, C),
    numeral(C, N).

trans(R, N) :-
    maplist(r2n, R, Rn),    % Pre-calculate a numeric list representation
    trans(Rn, 0, N).
trans([X,Y|T], Acc, N) :-
    X >= Y,
    Acc1 is Acc + X,
    trans([Y|T], Acc1, N).
trans([X,Y|T], Acc, N) :-
    X < Y,
    Acc1 is Acc - X,
    trans([Y|T], Acc1, N).
trans([X], Acc, N) :-
    N is Acc + X.
trans([], N, N).   % Optional rule: needed only if you want trans("", 0). to succeed

Note these rules will allow any valid Roman numeral, but will also do something with and succeed on some improperly formed Roman numerals. So it is not a set of rules to validate proper Roman numerals.

Sample output:

| ?- trans("mmxiv", X).

X = 2014 ? ;

no
| ?- trans("CMXCIX", X).

X = 999 ? ;

no
| ?- trans("IM", X).

X = 999 ? ;

no
| ?- trans("IVX", X).   % Not a properly-formed Roman numeral

X = 4 ? ;   % Uh... ok... I guess

no