#!/usr/bin/perl

use warnings;
use strict;

my @a = ('M','D','C','L','X','V','I');
my $max = 0;
my %a_val=map { $_ => $max++ } split //,'MDCLXVI';

sub search_biggest {
    my ($array,$model)= @_;
    my $begin=7;
    my $pos = 0;
    my $j;

    for (my $i = 0; $i < @$array; $i++) {
        $j = 0;
        while ($j < @$model) {
            if ($array->[$i] eq $model->[$j] and $a_val{$array->[$i]} 
+< $begin){
                $begin = $a_val{$array->[$i]};
                $pos = $i;
                $j++;
                last;
            }
            $j++;
        }
    }
    return $pos;
}

while(my $line = <DATA>){
    my ($b,$expect) = split /\s+/, $line;
    my @b_arr = split(//,$b);

    my $count = 0;
    my %val=map { $_ => $count++ } split //, $b;

    my @results = ('.') x @a;

    my $searched="0";
    my $j = 0;
    my $pos = search_biggest(\@b_arr, \@a);
    for (my $i = $pos; $i < @b_arr; $i++) {
        my $found = 0;
        while ($j < @a) {
            last if $b_arr[$i] =~ /$searched/;
            if ($b_arr[$i] eq $a[$j]){
                $found = 1;
                $results[$j]=$a[$j];
                $searched .= $a[$j];
            }
            $j++;
            if($found and $i < @b_arr){
                my @new = ( $i + 1 < @b_arr  ? @b_arr[ $i +1 ..  $#b_a
+rr ] : ($b_arr[$#b_arr]) );
                my @new2 = @a;
                $i = search_biggest(\@new,\@new2) if not @new = 1;
                last;
            }
        }
        $j = 0 unless $found;
    }
    my $result = join "",@results;
    printf "%7s => %7s  ( %7s : %-3s)\n",
        $b, $expect, $result, $result eq $expect ? "Ok" : "Not Ok";
}
print "\n";
__DATA__
I       ......I
IV      .....V.
V       .....V.
VI      .....VI
IX      ....X..
X       ....X..
XI      ....X.I
XIV     ....XV.
XV      ....XV.
XVI     ....XVI
XIX     ....X.I
X       ....X..
XL      ....X..
LX      ...LX..
XC      ....X..
CLXIX   ..CLX.I
CDXLVI  .D..XVI
MCMXCVI M.C.XVI
MDCLI   MDCL..I
[download]