Relate Roman and Arabic numerals

Question

How to relate Roman and Arabic numerals up to 899999 in a pure manner? And this time without using arithmetic! Thus without (is)/2 nor clpfd/clpz/clpq. Lacking any means to relate to integers, Arabic numerals have to be represented as a list of characters. Thus :- set_prolog_flag(double_quotes, chars).. The characters used for Roman numbers are below.

As usual, Arabic numerals do not have leading zeroes, nor spaces in between, the Roman numerals use the "common" subtractive rules. See below.

What I have tried so far was to use integers. But this here should be without them. Efficiency isn't the goal, but termination is.

The pure part includes dif/2 and dif_si/2 although 90 facts could express the inequality between decimal digits as well.

?- arabic_roman(A,R) , false.
   false.  % it terminates, we have only 899999 numbers, very finite
?- arabic_roman("0",R).
   false. % no zero
?- arabic_roman(['0'|_],R).
   false. % and in general no leading zeros
?- R=[_], arabic_roman(A,R).
   R = "I", A = "1"
;  R = "V", A = "5"
;  R = "X", A = "10"
;  R = "L", A = "50"
;  R = "C", A = "100"
;  R = "D", A = "500" % no apostrophus "IↃ"
;  R = "M", A = "1000" % no "CIↃ"
;  R = "ↁ", A = "5000" % idem
;  R = "ↂ", A = "10000"
;  R = "ↇ", A = "50000"
;  R = "ↈ", A = "100000"
;  R = "@", A = "500000" % poor support in Unicode
;  false.
?- arabic_roman("899999",R).
   R = "@ↈↈↈↂↈMↂCMXCIX" % the largest number
;  false.
?- arabic_roman(  ['9',_,_, _,_,_],R).
   false. % no six digit number starting with 9
?- arabic_roman( [_, _,_,_, _,_,_|_],R).
   false. % no seven or more digit numbers
?- setof(R,A^arabic_roman(A,R),Rs),length(Rs,N).
   Rs = ["@","@C","@CC","@CCC"|_], N = 899999.  % terms omitted at _
?- setof(A,R^arabic_roman(A,R),As),length(As,N).
   As = ["1","10","100","1000","10000","100000","100001"|_], N = 899999.
?- setof(A-R,arabic_roman(A,R),ARs),length(ARs,N).
   ARs = ["1"-"I","10"-"X","100"-"C","1000"-"M","10000"-"ↂ"|_], N = 899999.
?- arabic_roman(A,"IL").
   false. % no generalized subtractive rule
?- arabic_roman(A,"IM").
   false. % idem
?- arabic_roman(A,R), phrase((...,[X,X,X,X],...),R).
   false.

Doesn't "Efficiency isn't the goal, but termination is" mean that an answer with fewer unwanted choicepoints is preferable? — brebs, May 14 '23 at 18:46
Leftover choice points in current implementations are first of all an efficiency issue. Neither universal nor existential termination is affected by it. — false, May 14 '23 at 18:58

gusbro · Answer 1 · 2023-05-09T13:42:53.307

2

Here is my solution. I have changed some roman symbols because my setup has poor support for unicode, so P is 5000, T is 10000, F is 50000, Q is 100000 and @ is 500000.

:- set_prolog_flag(double_quotes, chars).

arabic_roman(A, R):- phrase(arabic_roman(A), R).

arabic_roman([A|As])-->
  { dif(A, '0') },
  arabic_roman_skip("Q@!TFMPCDXLIV!!", [A|As]).

arabic_roman_skip([P,_,_,P1,C1|S], As)-->
  arabic_roman_skip([P1,C1,P|S], As).
arabic_roman_skip(S, As)-->
  arabic_roman(S, As).

arabic_roman("!!I", [])-->[].
arabic_roman([P,C,N,P1,C1|S], [A|As])-->
  arabic_digit_roman(A, P,C,N),
  arabic_roman([P1,C1,P|S], As).

arabic_digit_roman('0', _,_,_) --> [].
arabic_digit_roman('1', P,_,_) --> [P].
arabic_digit_roman('2', P,_,_) --> [P,P].
arabic_digit_roman('3', P,_,_) --> [P,P,P].
arabic_digit_roman('4', P,C,_) --> [P,C].
arabic_digit_roman('5', _,C,_) --> [C].
arabic_digit_roman('6', P,C,_) --> [C,P].
arabic_digit_roman('7', P,C,_) --> [C,P,P].
arabic_digit_roman('8', P,C,_) --> [C,P,P,P].
arabic_digit_roman('9', P,_,N) --> [P,N], {dif(N,'!')}.

Sample runs:

?- arabic_roman("899999",R).
R = [@, 'Q', 'Q', 'Q', 'T', 'Q', 'M', 'T', 'C', 'M', 'X', 'C', 'I', 'X'].
?- time((setof(A1,R^A^(arabic_roman(A,R), atom_codes(A1,A)),As),length(As,N))).
% 3,118,631 inferences, 1.841 CPU in 1.879 seconds (98% CPU, 1694161 Lips)
As = ['1', '10', '100', '1000', '10000', '100000', '100001', '100002', '100003'|...],
N = 899999.

edited May 09 '23 at 13:42

answered May 08 '23 at 17:24

gusbro

22,357
35
46

These pcn-facts could be a single list. – false May 08 '23 at 17:47
`s/N \= '!'/dif(N,!)/` – false May 08 '23 at 17:50
@false: yes it could be a single list, but I'd have to tweak it to get the starting template – gusbro May 08 '23 at 18:40
I didn't understand your second comment. N at that point is always ground – gusbro May 08 '23 at 18:41
Both question and bounty are about a pure solution. And `\=` isn't. With `dif/2` or `dif_si/2` it would be. – false May 09 '23 at 06:36
The advantage of the list would be: More DRYness, and even a bit more efficient as it does not rely on deep indexing (where is that implemented?). Same for the `Rs` as non-terminal. Making arabic_digit_roman/3 a non-terminal would not increase the clause count and would avoid the `Rs` – false May 09 '23 at 06:40
You are right. I updated my answer and it is more efficient now. – gusbro May 09 '23 at 13:43
Leaves unwanted choicepoints, even when either (or both) side is ground. – brebs May 09 '23 at 13:57
`arabic_roman(A,R),false` with Scryer before 47.687s and now 3.084s. – false May 09 '23 at 14:10
This atom_code/2 should be rather a atom_chars/2. – false May 14 '23 at 05:33

brebs · Answer 2 · 2023-05-14T10:26:31.807

Doesn't quite seem worth using DCG:

% Need nan, to fill the last group of [I, V, X]
roman_chars(['I', 'V', 'X', 'L', 'C', 'D', 'M', 'ↁ', 'ↂ', 'ↇ', 'ↈ', '@', nan]).

arabic_digit_roman('0', _I, _V, _X, T, T).
arabic_digit_roman('1', I, _, _, [I|T], T).
arabic_digit_roman('2', I, _, _, [I, I|T], T).
arabic_digit_roman('3', I, _, _, [I, I, I|T], T).
arabic_digit_roman('4', I, V, _, [I, V|T], T).
arabic_digit_roman('5', _, V, _, [V|T], T).
arabic_digit_roman('6', I, V, _, [V, I|T], T).
arabic_digit_roman('7', I, V, _, [V, I, I|T], T).
arabic_digit_roman('8', I, V, _, [V, I, I, I|T], T).
arabic_digit_roman('9', I, _, X, [I, X|T], T) :-
    dif(X, nan).

arabic_roman(A, R) :-
    % No leading zero
    A = [First|_],
    dif(First, '0'),
    roman_chars(RCs),
    arabic_roman_(A, RCs, R).

arabic_roman_([], _, []).
arabic_roman_([AH|AT], RCs, R) :-
    arabic_length(AT, RCs, I, V, X, RCs0),
    arabic_digit_roman(AH, I, V, X, R, T),
    arabic_roman_(AT, RCs0, T).
    
arabic_length([], [I, V, X|_], I, V, X, [I]).
arabic_length([_|T], [II, VV|R], I, V, X, [II, VV|RC]) :-
    arabic_length(T, R, I, V, X, RC).

There are no unwanted choicepoints when the Arabic list is ground, e.g.:

?- arabic_roman(['1', '2', '3', '4', '5', '6'], R).
R = [ↈ, ↂ, ↂ, 'M', 'M', 'M', 'C', 'D', 'L', 'V', 'I'].

Performance in swi-prolog:

?- time((bagof(A-R, arabic_roman(A, R), ARs), length(ARs, N))).
% 2,312,762 inferences, 0.726 CPU in 0.726 seconds (100% CPU, 3184610 Lips)
ARs = [['1']-['I'], ['2']-['I', 'I'], ['3']-['I', 'I', 'I'], ...
N = 899999.

Only because e.g. ↂ doesn't have its spacing quite correct, when viewed in Linux terminal. Can change later. — brebs, May 09 '23 at 13:20
Improved termination when Arabic list is ground (not relying on JIT indexing). — brebs, May 13 '23 at 18:36

notoria · Accepted Answer · 2023-05-14T09:44:09.003

1

With 15 clauses (depending how we are counting). It terminates.

:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(dif)).

foldl(G__3, [], S, S) --> [].
foldl(G__3, [E|Es], S0, S) --> call(G__3, E, S0, S1), foldl(G__3, Es, S1, S).

d5u('0', s([R10|Rs],[R5,R1|Ds]), s([R1,R5,R10|Rs],Ds)) --> [].
d5u('1', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R1].
d5u('2', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R1,R1].
d5u('3', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R1,R1,R1].
d5u('4', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R1,R5].
d5u('5', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R5].
d5u('6', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R5,R1].
d5u('7', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R5,R1,R1].
d5u('8', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R5,R1,R1,R1].
d5u('9', s([R10|Rs],[R5,R1|Ds]), s([R1,R5,R10|Rs],Ds)) --> [R1,R10].

au5(_, s([R1,R5|Rs0],Rs), s(Rs0,[R5,R1|Rs])).

arabic_roman([C|Cs]) -->
    { foldl(au5, [C|Cs], s("IVXLCDMↁↂↇↈ@",[]), S0) },
    foldl(d5u,[C|Cs], S0, s([_|_],[])),
    { dif(C, '0') }.

arabic_roman(A, R) :-
    phrase(arabic_roman(A), R).

edited May 14 '23 at 09:44

answered May 08 '23 at 16:10

notoria

2,053
1
4
15

Stylistic comment: `R5->V,R1->I,R10->X`. But I am really impressed... – false May 08 '23 at 17:52
`foldl//4` gives me some headaches. After all, what does this call//4 construct mean? The variable name suggests, that its first argument is a non-terminal lacking three arguments. Currently we have only call//1, and the argument is a goal (not a non-terminal) lacking two arguments. So there is this distinction between non-terminals and predicates. And this call//4 mixes this up. – false May 09 '23 at 15:12
Just to be clear, it works... – false May 09 '23 at 15:13
`call//N` is like `call/N` but for DCGs. – notoria May 09 '23 at 15:24
So what is the first argument of `call//4`? Is it a non-terminal or a goal? – false May 09 '23 at 18:47
It's a non-terminal. – notoria May 09 '23 at 18:50
You use it like it would be one. But you could equally well use it as a goal lacking the corresponding arguments. – false May 09 '23 at 18:53
One way out would be to define `phrase//2,3,...` – false May 14 '23 at 07:45
But with `call//N` not much change is needed to adopt it but `phrase//N` would be like `maplist/N`. – notoria May 14 '23 at 09:50
actually the (internal) implementation would be almost identical, thus phrase(NT__1, A1, S0,S) :- call(NT__1, A1, S0,S). phrase(NT__2, A1, A2, S0,S) :- call(NT__2, A1, A2, S0,S). phrase(NT__3, A1, A2, A3, S0,S) :- call(NT__3, A1, A2, A3, S0,S). etc. Except that for NT__1 and NT__2 there would be some extra checking for control constructs. No such check is necessary from NT__3 on. – false May 14 '23 at 10:49

Relate Roman and Arabic numerals

3 Answers3