Roman Numerals in Perl 6

My first shot at the Perl Weekly Challenge with a Roman numeral encoder in 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.

  say [+] %r2i{ $roman.match(/ ( <{%r2i.keys}> )* /).flat>>.Str }
  ./roman.pl6 decode CCXLVI
  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.pl6 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

  #!/usr/bin/env perl6

  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.pl6 decode MMXIX
  2019

  ./roman.pl6 decode MCMLXXXIV
  1984

  ./roman.pl6 encode 2019
  MMXIX

  ./roman.pl6 encode 1984
  MCMLXXXIV
perl6 
comments powered by Disqus