PWC 047 › Roman Calculator

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

The first challenge this week tasks us with evaluating arithmetic operations using Roman numerals. The description seems to indicate that only one operation will be given (for example, II + IV), but I have elected to support arbitrary arithmetic expressions.

First, I needed a way to convert to and from Roman and Arabic numerals. I had coded this up years ago, and adapted the code I used. Here is the Roman to Arabic converter:

my %r2a = (I => 1, V => 5, X => 10, L => 50, C => 100, D => 500, M => 1000,
                  IV => 4,IX =>  9,XL => 40,XC =>  90,CD => 400,CM =>  900);

sub roman_to_arabic { 
    sum map { $r2a{$_} } pop =~ /(I[VX]|X[LC]|C[DM]|[IVXLCDM])/g 
}

It works by using a global match for matching components of the numeral that will exist in %rom, and sums those up. Easy.

Going the other direction, perhaps surprisingly, is a little bit harder:

my @a2r = map { [ $r2a{$_} => $_ ] } sort { $r2a{$b} <=> $r2a{$a} } keys %r2a;

sub arabic_to_roman {
    my $n = shift;
    my $r = '';
    while ($n) {
        my ($val, $rom) = @{( first { $_->[0] <= $n } @a2r )};
        $n -= $val;
        $r .= $rom;
    }
    $r;
}

We create an ordered map of numbers to their Roman counterparts. @a2r will look like this:

(
  [1000, "M"],
  [900, "CM"],
  [500, "D"],
  :
  [4, "IV"],
  [1, "I"],
)

Since it is sorted in descending numerical order, we can simply greedily subtract the first value from @a2r that is less than the current value of $n, and append the Roman counterpart to the result string ($r).

With that done, we can now work on the expressions:

Expressions

Handling expressions could be done by splitting the string and then using a dispatch table on the operation, but that would mean we could only do one operation at a time, the usual arithmetic order of operations would not apply, or we’d have to write our own expression engine, which is a non-trivial task. So, I decided to use eval instead.

sub roman_expr {
    my $expr = shift;
    $expr =~ s/\b([IVXLCDM]+)\b/roman_to_arabic($1)/eg;
    die "Invalid expression" if $expr =~ m![^ 0-9+*%/()-]!;

    arabic_to_roman( eval $expr );
}

This sub works by using a substitution regex to convert any Roman numerals it sees into their Arabic versions. Then, we check to make sure $expr contains only numbers, spaces, parentheses, and arithmetic operators, so we don’t get tricked into evaling something nasty.

After that, it’s just a matter of doing a string eval $expr and feeding that through arabic_to_roman to get a result in Roman numerals, as required.

An extra unintended feature of doing it this way is that roman_expr can accept mixed Roman and Arabic expressions. roman_expr('42 * II') returns LXXXIV (84), for example.

Testing

Roman numerals can be a little bit tricky to get right, so I added some test cases. In a real application, I’d greatly expand these, but these were enough for what I needed:

use Test::More;

my %tests = (
    I           => 1,
    XXXIX       => 39,
    CLX         => 160,
    CCXXXVII    => 237,
    CDXXXVIII   => 438,
    DCCCXLVIII  => 848,
    MLXVI       => 1066,
    MM          => 2000,
    MMXX        => 2020,
);
my @order = sort { $tests{$a} <=> $tests{$b} } keys %tests;

is roman_to_arabic($_), $tests{$_}, "$_ => $tests{$_}" for @order;
is arabic_to_roman($tests{$_}), $_, "$tests{$_} => $_" for @order;

my %expr = (
    XL      => 'XXXIX + I',
    DCLXXV  => 'CCXXXVII + CDXXXVIII',
    XIV     => '(CCXXXVII + CDXXXVIII) % XIII ** II / XII',
);
is roman_expr($expr{$_}), $_, "$_ = $expr{$_}" for sort keys %expr;

done_testing;

As I do not usually implement much, if any error checking in these challenge solutions (for brevity), I did not test any failure conditions. “Exercise for the reader,” right?

!Raku

I did not do a Raku solution for this one, as I’m extremely short on time this week and I don’t immediately see how my Raku version would differ significantly. I may update this post if I get to it later.