use warnings;
use strict;

# This file is a compiler from Brainpocalpyse II into a UT19 initial string.
#
# UT19 is the following 2-tag system (with states numbered 1 to 19
# inclusive, and the arrays giving the productions for states in
# numerical order):
#
# [[ 2, 3],
#  [ 4, 4], [18, 4],
#  [ 1, 1,19],
#
#  [ 7, 9], [ 8, 9],
#  [10,10], [11,10], [18,10],
#  [ 5, 6], [ 6, 5,19],
#
#  [14,14,14,14], [15],
#  [16,16], [16,17],
#  [12,13], [12,12,12,12],
#
#  [18], []]
#
# This program takes as input a Brainpocalypse II program in numerical
# syntax, and outputs a corresponding UT19 initial string.


# Parse the program.
undef $/;
my $program = <>;
$program =~ s/[^0-9+-]//g;
$program =~ s/([+-])/ $1/g;
my @program = split " ", $program;
my $maxcounter = 0;
my $mincounter = '+inf';
for my $command (@program) {
    $command =~ /([0-9]+)/ and my $counter = $1 and $command =~ /[+-]/
        or die "Invalid command '$command'";
    $counter < $mincounter and $mincounter = $counter;
    $counter > $maxcounter and $maxcounter = $counter;
}

print STDERR "Program: @program\n";
print STDERR "Counters used: $mincounter to $maxcounter inclusive\n";

++$maxcounter;
print STDERR "Adding one more counter $maxcounter to handle halting\n";

# The expanded set of commands used for compilation:
# ^  start of program
# =  idle (no-op, used for padding)
# +x increase counter x
# -x decrease counter x; if it's 0, increase it and go back to the start
# $a halt (part 1)
# $b halt (part 2)
#
# Each of these compiles to two running-xor entries for each memory
# block (here, "adj" is 1 if the location is adjacent to the affected
# counter, otherwise 0: for a halt, the "affected counter" is an extra
# "halt counter" at the end)
#
# command / before first counter / between counters / after last counter
# ^         0, 0                   0, 0               1, 0
# =         1, 0                   0, 0               1, 0
# +x        0, !adj                0, adj             0, !adj
# -x        1, adj                 0, adj             1, adj
# $a        1, adj                 0, adj             1, 0
# $b        irrelevant             irrelevant         0, 0

unshift @program, '^';
push @program, '$a', '$b';

# The program length must be a power of 2.
push @program, '=' while scalar(@program) & (scalar(@program) - 1);
print STDERR "Expanded program: @program (", scalar(@program), " commands)\n";

# Encodes a sequence of 0s and 1s into running-XOR format (i.e. a
# sequence of tag system states whose length parity on every relevant
# cycle is even or odd respectively). The sequence's length must be a
# power of 2; the number of persistent states in the output is returned.
sub encode_rx {
    if (scalar(@_) <= 1) {
        if ($_[0] == 0) {
            print ",5,6";
            return 1;
        } else {
            print ",5,6,1,1,19";
            return 2;
        }
    }
    my @first_half = splice @_, 0, scalar(@_)/2, ();
    my @second_half = @_;
    for my $i (0..$#first_half) {
        $first_half[$i] ^= $second_half[$i];
    }
    encode_rx(@first_half) + encode_rx(@second_half)
}

# Loop over the positions before, between and beyond the counters.
print "[19"; # need oddness on the first cycle
for my $before_counter ($mincounter .. ($maxcounter+1)) {
    my @rx = ();
    my $at_start = ($before_counter == $mincounter) ? 1 : 0;
    my $at_end = ($before_counter > $maxcounter) ? 1 : 0;
    for my $command (@program) {
        my $counter_number = -2;
        $command =~ /([0-9]+)/ and $counter_number = $1;
        $command =~ /^\$/ and $counter_number = $maxcounter;
        my $adjacent = ($counter_number == $before_counter ||
                        $counter_number == $before_counter - 1) ? 1 : 0;
        if ($command eq '^') {
            push @rx, $at_end, 0;
        } elsif ($command eq '=') {
            push @rx, $at_start|$at_end, 0;
        } elsif ($command =~ /^\+/) {
            push @rx, 0, $adjacent^$at_start^$at_end;
        } elsif ($command =~ /^\-/) {
            push @rx, $at_start|$at_end, $adjacent;
        } elsif ($command eq '$a') {
            push @rx, $at_start|$at_end, $adjacent&~$at_end;
        } elsif ($command eq '$b') {
            push @rx, 0, 0;
        } else {
            die "Unknown command '$command'";
        }
    }
    print STDERR "Before $before_counter: @rx\n";
    my $statecount = encode_rx(@rx);

    my $target = 4096;
    if ($before_counter == $maxcounter) {
        $target -= 2;
    } elsif ($before_counter == $mincounter) {
        $target -= 68;
    } elsif ($at_end) {
        $target -= 23;
    } else {
        $target -= 1024;
    }
    my $topup_amount = ($target - ($statecount % 2048)) % 2048;
    my $topup_statecount = $topup_amount + $statecount;
    print STDERR "State count: $statecount, adding $topup_amount to produce $topup_statecount\n";
    print ",1,1" x $topup_amount;

    if ($at_end) {
        # no counter here
    } else {
        print ",12,13,12,13";
    }
}
print "]\n";