#!/usr/bin/perl -w
use strict;

my $VERSION = "0.06";

my ($dead, %dead_range);

# use Data::Dumper;
# $Data::Dumper::Indent = 0;
if (0) {
    # my @target = qw(2 3 4 1 9);
    # my @dead   = qw(7 6 8 0);
    my @target = qw(7 0 6 3 9 5);
    my @dead   = qw(8 4 1 2);

    my ($from, $to) = best_range(\@target, \@dead);
    print "y/$from/$to/d\n";
} else {
    my @lines;
    local $| = 1;
    while (<>) {
        my %set;
        if ((my $str, my $letters, @set{qw(I V X)}) = /.* => ((.*) I=\[(.*)\] V=\[(.*)\] X=\[(.*)\])\s*$/) {
            $letters =~ y/ IVX//d;
            my %dead = map {$_ => 1} split //, $letters;
            my @dead = keys %dead;

            my %map;
            while (my ($letter, $set) = each %set) {
                $map{$_} = $letter for split //, $set;
            }
            my @alive = keys %map;
            my ($from, $to) = best_range(\@alive, \@dead);
            $to =~ s/(.)/exists $map{$1} ? $map{$1} : $1/eg;
            push @lines, sprintf "%-75s %s", $str, "y/$from/$to/d";
        } elsif (my ($params) = /^\s*((?:\w+=\d+\s*,\s*)*\w+=\d*)\s*$/) {
            print "$_ $params\n" for @lines;
            @lines = ();
        } else {
            print STDERR "Could not parse $_";
        }
    }
}

sub best_range {
    my $target = ranges(shift);
    $dead      = ranges(shift);

    %dead_range = ();

    my ($from_t, $to) = opt_ranges($target);
    my $from_d = range_string($dead->[0][0], $dead->[-1][1]);
    my $best = length($from_t)+length($to)+length($from_d);
    my $from = $from_t . $from_d;
    # print STDERR "Start from /$from_t.$from_d/$to/\n";

    for my $select_dead (0..$#$dead) {
        my $first = $select_dead ? 0 : 1;
        my $last  = $select_dead == $#$dead ? $#$dead-1 : $#$dead;
        my $from_d = $first > $last ? "" :
            range_string($dead->[$first][0], $dead->[$last][1]);
        my $mix_to = $dead->[$select_dead][1];
        for my $select_target (0..$#$target) {
            next if $target->[$select_target][0] gt $mix_to;
            my $mix_from = $target->[$select_target][0];
            my @t = grep $_->[0] ne $mix_from, @$target;

            my ($from_t, $to_t) = opt_ranges(\@t);
            my $from_m = range_string($mix_from, $mix_to);
            my $to_m   = range_sequence($mix_from, $target->[$select_target][1]);
            my $l = length($from_t)+length($to_t)+length($from_m)+length($to_m)+
                length($from_d);
            # print STDERR "was: [$mix_from,$mix_to] => /$from_t.$from_m.$from_d/$to_t.$to_m/ ($l vs $best)\n";
            if ($l < $best) {
                $from = $from_t . $from_m . $from_d;
                $to   = $to_t   . $to_m;
                $best = $l;
            }
        }                                       
    }
    return ($from, $to);
}

sub ranges {
    my @set = sort @{+shift};
    my @ranges;
    while (@set) {
        my $first = shift @set;
        my $current = ord($first);
        while (@set && $current+1 == ord($set[0])) {
            $current++;
            shift @set;
        }
        push @ranges, [$first, chr($current)];
    }
    return \@ranges;
}

sub opt_ranges {
    return ("", "") unless @{$_[0]};
    opt_ranges_work($_[0], 0, $#{$_[0]});
}

sub opt_ranges_work {
    my ($ranges, $first, $last) = @_;
    # my $i = 1;
    # $i ++ while (caller($i))[3] ne "main::opt_ranges";
    # my $r = Dumper($ranges);
    # $r =~ s/;$//;
    # print STDERR "  " x $i, "opt_ranges_work($r,$first, $last)\n";
    for ($first .. $last-1) {
        if (has_dead($ranges->[$_][1]+1, $ranges->[$_+1][0]-1)) {
            # MUST split here
            my ($from_left, $to_left)  = opt_ranges_work($ranges, $first, $_);
            my ($from_right, $to_right)= opt_ranges_work($ranges, $_+1, $last);
            return ($from_left . $from_right, $to_left . $to_right);
        }
    }
    my $from = range_string($ranges->[$first][0], $ranges->[$last][1]);
    my $to = range_sequence($ranges->[$first][0], $ranges->[$last][1]);
    my $best = length($from)+length($to);
    for ($first..$last-1) {
        my $f0 = range_string(  $ranges->[$first][0], $ranges->[$_][1]);
        my $t0 = range_sequence($ranges->[$first][0], $ranges->[$_][1]);
        my ($f1, $t1) = opt_ranges_work($ranges, $_+1, $last);
        my $l = length($f0)+length($f1)+length($t0)+length($t1);
        if ($l < $best) {
            $from = $f0 . $f1;
            $to   = $t0 . $t1;
            $best = $l;
        }
    }
    # print STDERR "  " x $i, "/$from/$to/\n";
    return ($from, $to);
}

sub range_string {
    my ($from, $to) = @_;
    die "Invalid range [$from, $to]" if $from gt $to;
    return $from if $from eq $to;
    return "$from$to" if ord($from)+1 == ord($to);
    return "$from-$to";
}

sub range_sequence {
    my ($from, $to) = @_;
    die "Invalid range [$from, $to]" if $from gt $to;
    return join "" => map chr, ord($from) .. ord($to);
}

sub has_dead {
    my ($from, $to) = @_;
    return $dead_range{$from}{$to} if exists $dead_range{$from}{$to};

    # return $dead_range{$from}{$to} = 0 if @$dead && $dead->[$i][1] < $from;
    die "We should never want to check this range" if 
        @$dead && $dead->[-1][1] lt $from;
    my $i = 0;
    $i++ while $dead->[$i][1] lt $from;
    return $dead_range{$from}{$to} = $dead->[$i][0] le $to;
}