My first shot at the Perl Weekly Challenge with a Roman numeral encoder in Raku (nee Perl 6).
I have been watching the Perl Weekly Challenge with interest since it was first announced, but without the time to actually participate. This week there are three challenges, the first of which is to write an encoder for Roman numerals:
Write a script to encode/decode Roman numerals. For example, given Roman numeral CCXLVI, it should return 246. Similarly, for decimal number 39, it should return XXXIX. Checkout wikipedia page for more informaiton.
Roman to Decimal
A Roman numeral can be decoded by splitting it into symbols, converting each to a decimal then
adding the decimals to give a result. 'One-before' numerals such as IX can be handled as a single symbol,
giving this list of symbols:
my %r2i =
'I' => 1, 'IV' => 4, 'V' => 5, 'IX' => 9,
'X' => 10, 'XL' => 40, 'L' => 50, 'XC' => 90,
'C' => 100, 'D' => 500, 'CM' => 900, 'M' => 1000;The decode algorithm can be implemented by matching all the symbols, taking a slice of the conversion map and then reducing the slice to its sum.
my $roman = 'CCXLVI';
say [+] %r2i{ $roman.match(/ ( <{%r2i.keys}> )* /).flat>>.Str } ./roman-decode.raku
246
That works fine but is surprisingly slow, more so for long numerals. Instead of using a regex
match, we can use split and keep the delimiter values with :v – though we do need to filter out
all the zero length strings between the delimiters.
say [+] %r2i{ $roman.split(%r2i.keys, :v).grep(*.Bool) }
Str.split uses the longest delimiter matches, filtering out the matches that are wholly contained
within a longer match – though this does not appear to be documented in the split documentation.
It would be nice if there was a version of Str.match that took a list of literal strings to match.
Decimal to Roman
The encode algorithm can be implemented by using integer arithmetic to find how many of each
symbol is required, starting with the numerically largest symbol M and then concatenating the
symbols together.
say [~] gather {
for %i2r.keys.sort: -* -> $radix {
take %i2r{$radix} x $number / $radix;
$number %= $radix;
}
} ./roman.raku encode 39
XXXIX
It's kinda nice using gather / take here but I'd prefer a functional solution over this
explicit iterative solution. Enough time spent already so that will be for another day.
The Resulting Program
use v6;
my %r2i =
'I' => 1, 'IV' => 4, 'V' => 5, 'IX' => 9,
'X' => 10, 'XL' => 40, 'L' => 50, 'XC' => 90,
'C' => 100, 'D' => 500, 'CM' => 900, 'M' => 1000;
multi MAIN('decode', Str $roman) {
say [+] %r2i{ $roman.split(%r2i.keys, :v).grep(*.Bool) }
}
my %i2r = %r2i.antipairs;
multi MAIN('encode', Int $number is copy where 0 <= $number <= 3999) {
say [~] gather {
for %i2r.keys.sort: -* -> $radix {
take %i2r{$radix} x $number / $radix;
$number %= $radix;
}
}
} ./roman.raku decode MMXIX
2019
./roman.raku decode MCMLXXXIV
1984
./roman.raku encode 2019
MMXIX
./roman.raku encode 1984
MCMLXXXIV