Roman Numerals in Raku

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) }

Try it Online!

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

Try it Online!

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
comments powered by Disqus