[fpc-pascal] Re: StrUtils.RomanToInt oddities

[Alberto Narduzzi]

Premise: I didn't go through your entire implementation, thou' at first 
sight looks much better than the current one.

I know roman numerals since I was 8 or 9 yo, that makes a quick and dirt 
result of about 35 years.

Thing is:

1. in the roman numerals, not all the digits can be subtracted from the 
others
2. no more than three same roman numerals can appear in a row.

so that XM is as invalid as CCCC.
(although this amenity can be seen on some - in my opinion poor - 
wristwatches' face that uses roman numerals, for the 4h, showing IIII 
instead of the correct IV, but this is another story)

in roman numerals we have only these digits:

I(1)   V(5)
X(10)  L(50)
C(100) D(500)
M(1000) (sorry, no digit for the expected progression, for 5000)

the only digits that can be subtracted are I, X and C (only those on the 
left side of the "table" above), and they can only from the 2 digits 
immediately following them in the system, so that:

I can be subtracted only from V and X
X can be subtracted only from L and C
C can be subtracted only from D and M

so that 45 cannot be written as VL (50 - 5, as one might suspect) but 
must be written as XLV, or to better understand, as (XL)V = 40 + 5

The maximum roman numeral that can be represented is 4999, that is NOT 
MMMIM, but instead: MMM(CM)(XC)(IX) 
1000+1000+1000+(1000-900)+(100-10)+(10-1)

After this, roman numerals always begin with bigger numbers to sum up, 
and proceed to smaller, so you cannot start adding up 10, then 500, then 
again 1; like XDI (whether it be intended to be 491 or 511 - just no way)

I did an implementation some time ago, for pure fun, and provided I find 
it out (or maybe I can just rewrite it, on the basis of this knowledge) 
I will be - repository allowing ;-) - wery happy to contribute with my 
2c for it.


Cheers, A.


On 20/09/13 21:49, Bart wrote:
> On 9/20/13, Reinier Olislagers<reinierolislagers at gmail.com>  wrote:
>
>> The question however becomes "what is the
>> algorithm for deciding invalid characters" which IMO will become a mess
>> very quickly. Much better to just consider the entire input as invalid.
>>
>
> Here's my implementation:
>
> program test;
>
> {$mode objfpc}
> {$H+}
>
> uses
>    SysUtils, StrUtils;
>
>
> function TryRomanToInt(S: String; out N: Integer): Boolean;
> var
>    i, Len: Integer;
>    Terminated: Boolean;
> begin
>    Result := (False);
>    S := UpperCase(S);  //don't use AnsiUpperCase please
>    Len := Length(S);
>    if (Len = 0) then Exit;
>    i := 1;
>    N := 0;
>    Terminated := False;
>    //leading M's
>    while (i<= Len) and (S[i] = 'M') do
>    begin
>      //writeln('TryRomanToInt: Found 1000');
>      Inc(i);
>      N := N + 1000;
>    end;
>    //then CM or or CD or D or (C, CC, CCC, CCCC)
>    if (i<= Len) and (S[i] = 'D') then
>    begin
>      //writeln('TryRomanToInt: Found 500');
>      Inc(i);
>      N := N + 500;
>    end
>    else if (i + 1<= Len) and (S[i] = 'C') then
>    begin
>      if (S[i+1] = 'M') then
>      begin
>        //writeln('TryRomanToInt: Found 900');
>        Inc(i,2);
>        N := N + 900;
>      end
>      else if (S[i+1] = 'D') then
>      begin
>        //writeln('TryRomanToInt: Found 400');
>        Inc(i,2);
>        N := N + 400;
>      end;
>    end ;
>    //next max 4 C's
>    if (i<= Len) and (S[i] = 'C') then
>    begin
>      //find max 4 C's
>      //writeln('TryRomanToInt: Found 100');
>      Inc(i);
>      N := N + 100;
>      if (i<= Len) and (S[i] = 'C') then
>      begin
>        //writeln('TryRomanToInt: Found 100');
>        Inc(i);
>        N := N + 100;
>      end;
>      if (i<= Len) and (S[i] = 'C') then
>      begin
>        //writeln('TryRomanToInt: Found 100');
>        Inc(i);
>        N := N + 100;
>      end;
>      if (i<= Len) and (S[i] = 'C') then
>      begin
>        //writeln('TryRomanToInt: Found 100');
>        Inc(i);
>        N := N + 100;
>      end;
>    end;
>
>    //then XC or XL
>    if (i + 1<= Len) and (S[i] = 'X') then
>    begin
>      if (S[i+1] = 'C') then
>      begin
>        //writeln('TryRomanToInt: Found 90');
>        Inc(i,2);
>        N := N + 90;
>      end
>      else if  (S[i+1] = 'L') then
>      begin
>        //writeln('TryRomanToInt: Found 40');
>        Inc(i,2);
>        N := N + 40;
>      end;
>    end;
>
>    //then L
>    if (i<= Len) and (S[i] = 'L') then
>    begin
>      //writeln('TryRomanToInt: Found 50');
>      Inc(i);
>      N := N + 50;
>    end;
>
>    //then (X, xx, xxx, xxxx)
>    if (i<= Len) and (S[i] = 'X') then
>    begin
>      //find max 4 X's
>      //writeln('TryRomanToInt: Found 10');
>      Inc(i);
>      N := N + 10;
>      if (i<= Len) and (S[i] = 'X') then
>      begin
>        //writeln('TryRomanToInt: Found 10');
>        Inc(i);
>        N := N + 10;
>      end;
>      if (i<= Len) and (S[i] = 'X') then
>      begin
>        //writeln('TryRomanToInt: Found 10');
>        Inc(i);
>        N := N + 10;
>      end;
>      if (i<= Len) and (S[i] = 'X') then
>      begin
>        //writeln('TryRomanToInt: Found 10');
>        Inc(i);
>        N := N + 10;
>      end;
>    end;
>
>    //then IX or IV
>    if (i + 1<= Len) and (S[i] = 'I') then
>    begin
>      if (S[i+1] = 'X') then
>      begin
>        Terminated := (True);
>        //writeln('TryRomanToInt: Found 9');
>        Inc(i,2);
>        N := N + 9;
>      end
>      else if (S[i+1] = 'V') then
>      begin
>        Terminated := (True);
>        //writeln('TryRomanToInt: Found 4');
>        Inc(i,2);
>        N := N + 4;
>      end;
>    end;
>
>    //then V
>    if (not Terminated) and (i<= Len) and (S[i] = 'V') then
>    begin
>      //writeln('TryRomanToInt: Found 5');
>      Inc(i);
>      N := N + 5;
>    end;
>
>
>    //then I
>    if (not Terminated) and (i<= Len) and (S[i] = 'I') then
>    begin
>      Terminated := (True);
>      //writeln('TryRomanToInt: Found 1');
>      Inc(i);
>      N := N + 1;
>      //Find max 3 closing I's
>      if (i<= Len) and (S[i] = 'I') then
>      begin
>        //writeln('TryRomanToInt: Found 1');
>        Inc(i);
>        N := N + 1;
>      end;
>      if (i<= Len) and (S[i] = 'I') then
>      begin
>        //writeln('TryRomanToInt: Found 1');
>        Inc(i);
>        N := N + 1;
>      end;
>      if (i<= Len) and (S[i] = 'I') then
>      begin
>        //writeln('TryRomanToInt: Found 1');
>        Inc(i);
>        N := N + 1;
>      end;
>    end;
>
>    //writeln('TryRomanToInt: Len = ',Len,' i = ',i);
>    Result := (i>  Len);
>    //if Result then writeln('TryRomanToInt: N = ',N);
>
> end;
>
> var
>    S: String;
>    N1, N2: Integer;
>    B: Boolean;
>
> begin
>    repeat
>      write('Enter Roman numeral: ');
>      readln(S);
>      B := TryRomanToInt(S, N1);
>      if B then
>        write('TryRomanToInt(''',S,''') ->  ',N1)
>      else
>        write('TryRomanToInt(''',S,''') FAIL');
>      writeln;
>      N2 := StrUtils.RomanToInt(S);
>      writeln('StrUtils.RomanToInt(''',S,''') = ',N2);
>      if B and (N1<>  N2) then writeln('StrUtils.RomanToInt<>  TryRomanToInt');
>      writeln;
>    until S = '';
> end.
>
> Bart
> _______________________________________________
> fpc-pascal maillist  -  fpc-pascal at lists.freepascal.org
> http://lists.freepascal.org/mailman/listinfo/fpc-pascal
>