Erlang Central

Difference between revisions of "Roman Numerals"

From ErlangCentral Wiki

 
Line 99:Line 99:
 
Once we determine which condition we are dealing with, we just sum the decimal values of the symbol that we have recognized.  
 
Once we determine which condition we are dealing with, we just sum the decimal values of the symbol that we have recognized.  
  
[[Category:CookBook]]
+
[[Category:CookBook]][[Category:NumberRecipes]]

Revision as of 23:05, 3 September 2006

Problem

You want to convert decimal numbers to Roman numerals and Roman numerals to decimal numbers.

Solution

Here is some example code illustrating the conversion between decimals numbers and Roman numerals.

% dec_to_roman/1 : integer -> string
%   format the integer num using roman numerals
decimal_to_roman(Num) ->
    decimal_to_roman(Num, "",
        [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1],
        ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX",
         "V", "IV", "I"]).

% dec_to_roman/4 : integer string [t number) (list string) -> string
%   append the numbers num formatted as roman numerals to the string s,
%   using the roman numerals in roman-numbers with corresponding
%   decimal values in decimal-values
decimal_to_roman(0, Accum, Decimals, Romans) -> Accum;
decimal_to_roman(Num, Accum, Decimals, Romans) ->
    F_el = hd(Decimals),
    if
        F_el =< Num -> decimal_to_roman(Num - F_el,
                                        Accum ++ hd(Romans),                    
                                        Decimals, Romans);
        true -> dec_to_roman(Num, Accum, tl(Decimals), tl(Romans))
    end.

% Example of use:
1> decimal_to_roman(1997).
"MCMXCVII"
2> decimal_to_roman(1929).
"MCMXXIX"
3> decimal_to_roman(2112).
"MMCXII"

And here is the reverse transformation (converting between Roman numerals and decimal numbers):

% roman_to_decimal : string -> integer
%  convert a string with (uppercase) roman numerals to an integer
roman_to_decimal("") -> 0;
roman_to_decimal(Str) ->
    case length(Str) of
        1 ->
            case list_to_atom(Str) of
                'I' ->    1;
                'V' ->    5;
                'X' ->   10;
                'L' ->   50;
                'C' ->  100;
                'D' ->  500;
                'M' -> 1000;
                _   -> 0
            end;
        _ ->
            roman_to_decimal( string:substr(Str, 3) )
            + case list_to_atom( string:substr(Str, 1, 2) ) of
                'IV' ->   4;
                'IX' ->   9;
                'XL' ->  40;
                'XC' ->  90;
                'CD' -> 400;
                'CN' -> 900;
                _    -> roman_to_decimal( string:substr(Str, 1, 1) )
                        + roman_to_decimal( string:substr(Str, 2, 1) )
            end
    end.
% Example of use:
4> roman_to_decimal("MM").
2000
5> roman_to_decimal("MMIII").
2003
6> roman_to_decimal("MMIIII").
2004
7> roman_to_decimal("MCMXM"). 
3110 


In the first code sample we show a very simple solution; the main procedure takes the number to be converted. It then calls an auxilliary procedure that performs the actual conversion. The auxilliary procedure takes four arguments: (1) the number we want to convert, (2) an accumulator string that will (eventually) contain the result, (3) a list containing the decimal integers that we can represent as roman numerals, and (4) a list of corresponding roman numeral representations of the decimal values.

We have three cases to consider:

If the input number is zero, we just return the accumulator string, which is the value we are seeking. Otherwise, we need to make a recursive call. There are two possibilities: If the number is greater than or equal to the first element of the decimals list: Use the difference of the first argument (the number to be converted) and the "value" of the roman numeral we are currently considering for the first argument. Append the roman numeral character currently being considered to the accumulator and pass this as the second argument. The other two arguments are the decimal and roman lists without changes. Otherwise, the number must be less than the first element of the decimal list: Use the input number without changes for the first argument. Use the existing accumulator string for the second argument. The final two arguments are the decimal and roman numeral lists (without their first element).

In the second code example we use Erlangs term matching features to take pairs of roman numerals for evaluation, until there is only one character left. If the pair of numerals matches a known valid roman number (i.e., IV, IX, XL, XC, CD, CM), we do the conversion; otherwise we interpret the first of the two characters as a number (i.e., I,V,X,L,C,D,M), and then do a recursive call on the remaining elements of the string. Note that the second character from the pair we just evaluated is included in the remaining numerals to be evaluated. This problem would be difficult to solve without Erlang pattern matching features.

Once we determine which condition we are dealing with, we just sum the decimal values of the symbol that we have recognized.