#!/usr/bin/perl

use Data::Dumper;
use Scalar::Util qw/refaddr/;

use warnings;
use strict;

local $\ = "\n";

my %rules = (
    A => [qw/B C/],
    B => [qw/A/],
    C => [qw/A A A/],
);

my @initial = qw/A A A A A A A/;

my $n_to_skip = 1;

# Construct the alphabet. We don't know all the numbers yet, but we
# can just leave variables to substitute later. In fact, we construct
# a Perl expression for each number, and evaluate them all later.

my %offsets_into_alphabet = ();
my @alphabet = ();
my $max_alphabets_per_rule = 1;

{
    local $Data::Dumper::Indent = 0;
    local $Data::Dumper::Terse = 1;
    for my $rule (sort keys %rules)
    {
        my $alphabets_required = 1;
        $offsets_into_alphabet{$rule} = scalar @alphabet;
        for my $rule_entry (@{$rules{$rule}}) {
            my $escaped_rule_entry = Dumper($rule_entry);
            
            # Output a header. This skips over the leading padding
            # (which has a fixed size of 1 alphabet), and the offset
            # for that rule entry.
            push @alphabet, 2, 1, '@alphabet + $offsets_into_alphabet{' .
                $escaped_rule_entry . '}', 0;
            # Output the portion of the leading padding that isn't a
            # misaligned part of the alphabet. This has a size sufficient
            # to replace all the parts of the alphabet that will have
            # already been output by the time we output the misaligned
            # alphabet. There are 5 numbers between here and there.
            # The content of the padding itself is arbitrary.
            push @alphabet, 1, (@alphabet + 5), 523;
            # Output the alphabets for the rule. One is misaligned, and
            # split up between the start and end padding; the others
            # provide the rule's actual alphabets.
            push @alphabet, '@alphabet', '$max_alphabets_per_rule + 1';
            $alphabets_required++;
            # Output the portion of the trailing padding that isn't a
            # misaligned part of the alphabet. This is much the same
            # as the leading padding, except we subtract from the
            # length of one alphabet. The trailing plus the leading
            # portion make up one alphabet total.
            push @alphabet, 1, ('@alphabet - '.  @alphabet), 523;
        }

        # Output the skip to the next command. The distance is the
        # rest of this alphabet, plus a number of alphabets equal to
        # the number of unused alphabets, plus the size of the
        # trailing padding (1 alphabet), plus n times the length of an
        # entire command. The length of a command is equal to 2
        # numbers + 1 alphabet leading padding +
        # max_alphabets_per_rule alphabets + 1 alphabet trailing
        # padding.
        push @alphabet, '@alphabet - ' . (scalar @alphabet + 2) .
            ' + (@alphabet * (1 + $max_alphabets_per_rule - ' .
            $alphabets_required . ')) + $n_to_skip * ' .
            '(2 + @alphabet * (2 + $max_alphabets_per_rule))', 0;

        $alphabets_required > $max_alphabets_per_rule
            and $max_alphabets_per_rule = $alphabets_required;
    }
}

# Now we have the alphabet in terms of expressions; evaluate those
# expressions.

$_ = eval for @alphabet;

# All we need now is to encode the initial rule. We use two shortcuts
# to make the output program shorter:
# - When we need to generate padding, we use additional copies of the
#   alphabet, allowing us to do this:
# - Instead of outputting the program directly, we output a program
#   that generates the program we want the first time along the queue,
#   allowing us to RLE-compress the program using the fact that
#   ResPlicate has excellent support for repeating strings.

my @program = ();

for my $command (@initial) {
    push @program, 2, 1, (@alphabet + $offsets_into_alphabet{$command}), 0,
        (scalar @alphabet), ($max_alphabets_per_rule + 2), @alphabet;
}

print "@program";