# Compiler from The Waterfall Model to Flooding Waterfall Model
#
# See also <https://esolangs.org/wiki/Flooding_Waterfall_Model> for more
# information about Flooding Waterfall Model and about the principles behind
# this compiler.
#
# Takes a program in The Waterfall Model, in the standard JSON syntax, as input.
#
# The output is a Flooding Waterfall Model program that halts if and only if the
# original program halted.

use 5.012;
use warnings;
use strict;
use bigint try=>"GMP";

# JSON::PP is used because a) it ships with Perl, b) it is compatible with the
# `use bigint;` pragma.
use JSON::PP qw/decode_json/;

####### Command-line options
#
# The only option in use here is "-d" which specifies what debugging output to
# show. It's a regular expression of debugging output that you want to see.
#
# To see all the debugging output, use "-d .".

my $debug_regexp = qr/(?!)/;
if ($ARGV[0] eq '-d') {
    shift @ARGV;
    $debug_regexp = shift @ARGV;
}

####### Parsing the program
#
# This section of code just converts the input from text into a nested Perl
# array reference, and verifies that it has the correct shape and data type
# (meaning that the rest of the program can assume that it's correct without
# checking).

undef $/;
my $program = decode_json <>;

# decode_json reads very large numbers as strings, cast to bigint; also verify
# that this is an array of arrays of ints, not some other sort of JSON object
ref $program eq 'ARRAY' or die "input must be an array of arrays";
for my $row (@$program) {
    ref $row eq 'ARRAY' or die "input must be an array of arrays";
    for my $cell (@$row) {
        (ref $cell eq 'ARRAY' or ref $cell eq 'HASH' or !defined $cell)
            and die "input cells must be integers";
        $cell += 0;
        $cell->is_nan() and die "input cells must be integers";
    }
}

# verify the array is the correct size
my $waterclock_count = $program->[0][1];
my $array_size = $waterclock_count + 1;
scalar @$program == $array_size or die
    "Program must have $array_size rows to match the first line";
while (my ($nth, $row) = each @$program) {
    scalar @$row == $array_size or die
        "Row $nth must have $array_size columns to match the first line";
}

####### Calculating velocities
#
##### About velocities
#
# This construction divides the flooding counters into two "clusters". Program
# exceution alternates between the clusters: when a flooding counter in either
# cluster floods, then no flooding counters from the other cluster will flood
# until all the flooding counters in the original cluster have become zero.
#
# In this construction, the quantity used to store data is the point in time at
# which each flooding counter has most recently become nonzero; this quantity is
# measured relative to sum(i=1..=c) b**i, where b is a constant (that's the same
# for all flooding counters) chosen based on the size of the program and c is
# the number of cluster runs that have occurred, and the difference is known as
# the flooding counter's "position".
#
# When a flooding counter eventually counts down to zero and floods, it might
# cause some other flooding counters to become nonzero in the process, thus
# giving them a new position; in the case that this section of code is
# interested in, this will happen during the next cluster run , so will be
# measured relative to sum(i=1..=c+1) b**i, i.e. a point b**(c+1) cycles later.
# The difference between the old and new positions will be based on the number
# of cycles the flooding counter was nonzero for, which is also equal to the
# number added to it since it was last zero, i.e. it is the same as the flood
# size.  Because this specifies a new position relative to an old position, it
# is known as the flooding counter's "velocity".
#
# In this construction, the velocity of each flooding counter follows a simple
# repeating pattern based on the number of cluster runs.  This section's job is
# to work out what that pattern is.
#
##### The counter configuration
#
# In order to calculate the flooding counters' velocities, we need to know which
# flooding counters are in use.  In each of the two clusters, there are the
# following flooding counters:
#
# * A set of "baseline" flooding counters, consisting of a "negative baseline",
#   a "neutral baseline", and a set of "positive baseline" counters (one for
#   each original waterclock).  These each have a position of -c.  This set is
#   self-contained (in the sense that baseline counters are only ever
#   incremented by other baseline counters, from the other cluster), and its
#   purpose is to adjust flooding counter velocities by adding to them.
#   Baseline counters can increment non-baseline flooding counters, but only do
#   so when the non-baseline counter in question has a nonzero value (thus, they
#   never affect the position of non-baseline flooding counters, only ever the
#   velocity).
#
#   The neutral baseline counter has a velocity of b**c.  The negative baseline
#   counter's velocity is b**c-1, and the positive baseline counters take turns
#   having a value of b**c+1 (the positive baseline counter corresponding to the
#   original waterclock currently being zero-tested is b**c+1, the others are
#   b**c, and the execution cycles through each original waterclock in sequence
#   and zero-tests it).  The move from one counter to the next happens when
#   changing from cluster A to cluster B – the zero-tested counter stays the
#   same when changing back from cluster B to cluster A.
#
# * A "zero" flooding counter that specifies what position is considered to
#   represent a waterclock with value 0 (a position of +2 relative to "zero"
#   means value 0, of +4 means value 1, of +6 means value 2, etc.; these values
#   are sufficient to ensure that "normal" is always at or later than "zero" and
#   thus never equals "comparison").  The positions of all the waterclocks must
#   fit between "zero" and "negative baseline".  This in turn means that the
#   velocity of "zero" must be substantially lower than that of the baseline
#   counters, to ensure that there is always space; it is a fixed value, b**c-r,
#   where r is a value based on the program.  (r can be calculated as follows:
#   work out the velocities of the counters relative to that of "zero"; then
#   pick the minimum r for which these velocities are always lower than that of
#   "negative baseline".)  The position of "zero" in one cluster is based on the
#   position of "zero" of the previous cluster, but the velocity causes it to be
#   earlier by r, meaning that "zero"'s position is -c*r plus a constant (the
#   constant is chosen to allow the initial positions of the waterclocks to fit
#   between the positions of "zero" and "baseline").
#
# * For each original waterclock, cluster A has two flooding counters with the
#   same position (which specifies the waterclocks' value based on the position
#   relative to "zero") but different velocities, called "normal" and "boosted".
#   "Normal" will be the flooding counter that sets the position of the
#   waterclock's flooding counters in the next cluster in the case where the
#   waterclock being zero-tested (which might be the same waterclock, or a
#   different one) was not zero.  "Boosted" sets the position of those counters
#   in the case where a waterclock was zero-tested and found to be zero.
#
#   Cluster B also represents each original waterclock with two flooding
#   counters with the same position but different velocities, but they have
#   diferent purposes.  "Value" is what sets the positions of the cluster A
#   flooding counters that represent the waterclock, and has a velocity equal to
#   that of "zero".  "Test" is used to determine which waterclock is being
#   tested: it has velocity 3 lower than "value" (thus "zero") if this is the
#   waterclock being tested, and equal velocity otherwise.
#
# * "Comparison" exists only in cluster A, and its position is based on the
#   lowest position of the "test" flooding counters (thus, this will be earlier
#   than "zero"'s position if the counter being zero-tested is zero, and later
#   otherwise).  Its velocity is equal to that of "zero".  Exception: a halt
#   waterclock's "test" counter does not contribute position to "comparison",
#   but rather to "halt comparison".
#
# * "Halt comparison" exists only in cluster A, and its position is based on
#   the lowest position of the "test" flooding counters that correspond to halt
#   waterclocks.  Its velocity is equal to that of "zero".  This serves the same
#   role as "comparison", but with different effects if its position falls
#   before "zero" (instead of running zeroing triggers, it halts the program).
#
# * "Sustain" is part of neither cluster, and is the sustain counter for the
#   Flooding Waterfall Model program (i.e. when it zeroes, the program halts).
#   Because it can never become zero during program execution, it does not have
#   a position in the sense that other counters do.  Except when a halt
#   situation has been detected, its value is always exactly 1 more than the
#   value of the higher "zero" counter (something that is implemented by having
#   almost everything that adds to the higher "zero" counter also add to
#   "sustain").  Halting is implemented by having "halt comparison" add to the
#   "zero" of cluster A, its own cluster (rather than adding to the other
#   cluster, like most counters do): if "halt comparison" has a later position
#   than "zero", this will add to the *lower* "zero" counter and thus not mess
#   up the relationship between "sustain" and the higher "zero" counter; but if
#   "halt comparison" has an earlier position than "zero", the "zero" counter
#   that it adds to will have the higher value at the time, messing up the
#   invariant and allowing "sustain" to fall to value 0 and end the program.
#
# Although velocities and positions are ultimately measured relative to those of
# "baseline", most are calculated in terms of that of "zero" (and only then
# converted to "baseline"-based units, so this section starts by working out the
# velocities of the "zero"-based counters, and then working out the value of *r*
# and converting to "baseline"-based units.
#
# Some velocities vary depending on which counter is currently being zero-tested
# and thus are stored as a map from 1-based counter numbers to velocity values.
# Others are constant, and stored as integers.

##### Zero-relative velocities

my %zero_relative_velocities;

$zero_relative_velocities{"A zero"} = 0; # by definition
$zero_relative_velocities{"B zero"} = 0; # by definition
$zero_relative_velocities{"A comparison"} = 0;
$zero_relative_velocities{"A halt comparison"} = 0;
# loop over the waterclocks the counter pertains to...
for my $waterclock (1..$waterclock_count) {
    $zero_relative_velocities{"B value $waterclock"} = 0;
    # and the waterclock being zero-tested.
    for my $ztw (1..$waterclock_count) {
        my $minus_2_if_zero_tested = $ztw == $waterclock ? -2 : 0;
        # The test waterclock has a position before the waterclock that's being
        # zero-tested (or possibly equal to that of a waterclock with lower
        # value, but it will still be higher than "zero" in that case).
        $zero_relative_velocities{"B test $waterclock"}{$ztw} =
            $ztw == $waterclock ? -3 : 0;
        # Normal behaviour of a waterclock is to decrement when it is
        # zero-tested (implementing the steady decrement) and remain the same
        # otherwise.
        $zero_relative_velocities{"A normal $waterclock"}{$ztw} =
            $minus_2_if_zero_tested;
        # Boosted behaviour of a waterclock depends on the zeroing trigger.
        # Note that the steady decrement still occurs, so the self-reset
        # needs to be decremented. Exception: a halt counter halts the
        # program, meaning that its subsequent value doesn't actually matter,
        # and it is better to not decrement it in order to ensure that no
        # counter position falls before that of "zero".
        my $boost_value = 2 * $program->[$ztw][$waterclock] +
            $minus_2_if_zero_tested;
        $boost_value = 0 if $boost_value < 0;
        $zero_relative_velocities{"A boosted $waterclock"}{$ztw} =
            $boost_value;
    }
}

sub print_countermap {
    my $map = shift;
    for my $countername (sort keys %$map) {
        my $value = $map->{$countername};
        print STDERR "$countername: ";
        if (ref $value eq 'HASH') {
            print STDERR "{";
            my $first = 1;
            for my $timing (sort {$a <=> $b} keys %$value) {
                print STDERR ", " unless $first;
                print STDERR "$timing: ", $value->{$timing};
                undef $first;
            }
            print STDERR "}\n";
        } else {
            print STDERR "$value\n";
        }
    }
}

if ('zero-relative velocities' =~ $debug_regexp) {
    print STDERR "Counter velocities, relative to 'zero':\n";
    print_countermap(\%zero_relative_velocities);
    print STDERR "\n";
}

##### Baseline-relative velocities

### Calculating r
#
# This needs to be large enough that the baseline-relative velocity of all
# non-baseline counters is strictly smaller than that of all baseline counters.
# The minimum baseline-relative baseline velocity is -1 (for the negative
# baseline), thus r needs to be at least 2 greater than the maximum
# zero-relative velocity.

my $max_zrv = 0; # maximum "zero"-relative velocity
for my $velocity (values %zero_relative_velocities) {
    my $vmap = $velocity;
    $vmap = {0 => $velocity} unless ref $velocity eq 'HASH';
    $max_zrv > $_ or $max_zrv = $_ for values %$vmap;
}
my $r = $max_zrv + 2;

if ('r value' =~ $debug_regexp) {
    print STDERR "Highest 'zero'-relative velocity is $max_zrv\n";
    print STDERR "Thus, value of 'r' is $max_zrv + 2 = $r\n\n";
}

### Converting zero-relative velocities to baseline-relative velocities
#
# This is simply a case of subtracting r.

my %baseline_relative_velocities;
while (my ($countername, $velocity) = each %zero_relative_velocities) {
    if (ref $velocity eq 'HASH') {
        $baseline_relative_velocities{$countername}{$_} =
            $zero_relative_velocities{$countername}{$_} - $r
            for keys %{$zero_relative_velocities{$countername}};
    } else {
        $baseline_relative_velocities{$countername} =
            $zero_relative_velocities{$countername} - $r;
    }
}

### Velocities naturally defined in terms of the baseline
$baseline_relative_velocities{"A baseline neutral"} = 0; # by definition
$baseline_relative_velocities{"B baseline neutral"} = 0; # by definition
$baseline_relative_velocities{"A baseline negative"} = -1;
$baseline_relative_velocities{"B baseline negative"} = -1;
for my $waterclock (1..$waterclock_count) {
    for my $ztw (1..$waterclock_count) {
        $baseline_relative_velocities{"A baseline $waterclock positive"}{$ztw} =
            $ztw == $waterclock ? 1 : 0;
        $baseline_relative_velocities{"B baseline $waterclock positive"}{$ztw} =
            $ztw == $waterclock ? 1 : 0;
    }
}

if ('baseline-relative velocities' =~ $debug_regexp) {
    print STDERR "Counter velocities, relative to 'neutral baseline':\n";
    print_countermap(\%baseline_relative_velocities);
    print STDERR "\n";
}

####### Calculating the flooding zeroing triggers
#
##### Non-baseline, non-sustain flooding zeroing triggers
#
# A flooding zeroing trigger has effects on both position and velocity.
# However, the effect on position is a digital effect: either one cell of the
# trigger is non-zero (causing the affected flooding counter to be given a
# position that's no greater than the position + velocity of the counter that
# flooded), or else it's zero (not having such an effect).  In this
# construction, the velocity is always statically known, and is set by the
# zeroing triggers of the baseline flooding counters, which do so by cancelling
# out the statically known effect on velocity of the non-baseline flooding
# zeroing triggers.  (The key observation is that the resulting velocity does
# not care about the order in which the flooding zeroing triggers within a
# cluster run, nor the positions of anything within the cluster (as long as the
# cluster becomes entirely zero before the other cluster starts to zero), even
# if some of the flooding counters within the cluster increase each other.)
#
# As such, this section is just a listing of which entries of the flooding
# zeroing triggers for the non-baseline counters are nonzero.  The entries that
# need to be nonzero are:
#
# * For each counter: its "normal" and "boosted" both increment its
#   "value" and "test"; and its "value" increments its "normal" and "boosted".
#
# * For each counter: its "test" increments "comparison" or "halt comparison"
#   (depending on whether or not it is a halt counter).
#
# * "halt comparison" increments the "zero" within the same cluster, which
#   increments the "comparison" within the same cluster, which increments all
#   the "normal" flooding counters within the same cluster.  This means that if
#   "halt comparison" is before "zero", it breaks the invariant between "zero"
#   and "sustain" and the program halts; if "zero" is before "comparison", it
#   postpones "comparison"'s zeroing until after the "normal" counters have
#   zeroed, meaning that the "normal" counters are what affects the waterclocks'
#   "value"s; otherwise, "comparison" arrives before both "normal" and "zero",
#   delaying the "normal" counters until after the "boosted" counters, meaning
#   that those are what affects the waterclocks' "value"s.
#
# * Each cluster's "zero" sets the position for the other cluster's "zero".
#
# These relationships are (and must be, due to being hardcoded) independent of
# which counter is being zero-tested.

my %flood_triggers;
$flood_triggers{"A halt comparison"}{"A zero"} = 1;
$flood_triggers{"A zero"}{"A comparison"} = 1;
$flood_triggers{"A zero"}{"B zero"} = 1;
$flood_triggers{"B zero"}{"A zero"} = 1;
for my $waterclock (1..$waterclock_count) {
    $flood_triggers{"A normal $waterclock"}{"B value $waterclock"} = 1;
    $flood_triggers{"A normal $waterclock"}{"B test $waterclock"} = 1;
    $flood_triggers{"A boosted $waterclock"}{"B value $waterclock"} = 1;
    $flood_triggers{"A boosted $waterclock"}{"B test $waterclock"} = 1;
    $flood_triggers{"B value $waterclock"}{"A normal $waterclock"} = 1;
    $flood_triggers{"B value $waterclock"}{"A boosted $waterclock"} = 1;
    if ($program->[$waterclock][$waterclock] == 0) {
        # It's a halt counter.
        $flood_triggers{"B test $waterclock"}{"A halt comparison"} = 1;
    } else {
        $flood_triggers{"B test $waterclock"}{"A comparison"} = 1;
    }
    $flood_triggers{"A comparison"}{"A normal $waterclock"} = 1;
}

if ('position triggers' =~ $debug_regexp) {
    print STDERR "Flooding zeroing triggers that affect position:\n";
    for my $triggering_counter (sort keys %flood_triggers) {
        print STDERR "$triggering_counter affects: ";
        local $, = ", ";
        print STDERR sort keys %{$flood_triggers{$triggering_counter}};
        print STDERR "\n";
    }
    print STDERR "\n";
}

##### Baseline flooding zeroing triggers
#
### Calculating the non-baseline flood triggers' effects on velocity
#
# One of the roles of the baseline counters' flooding zeroing triggers is to
# cancel out the effects that the non-baseline flooding zeroing triggers have on
# velocity.  As such, we need to work out what those effects are so that they
# can be cancelled out.
#
# When a flooding zeroing trigger in one cluster affects a flooding counter in
# the other cluster, this effect is very simple: it adds its velocity to that
# counter's velocity.
#
# When a flooding zeroing trigger in one cluster affects a flooding counter in
# the same cluster, the effect is a bit more complicated: it will add its
# velocity to everything in the other cluster that that counter affects (even
# indirectly).
#
# One other thing that's worth noting: velocity has two components (the
# baseline-relative component that's stored in %baseline_relative_velocities,
# and the baseline itself, b**c).  Both components need to be accounted for,
# so there are two hashes, one for each component.

# *always* split into a hash based on which waterclock is being zero-tested
my %baseline_relative_velocity_effect;
my %absolute_velocity_effect; # in units of b**c

sub same_cluster {
    my $countername1 = shift;
    my $countername2 = shift;
    substr($countername1, 0, 1) eq substr($countername2, 0, 1)
}

# When one counter affects another counter in a different cluster, works out
# what the zero-tested waterclock will be in the new cluster based on what the
# zero-tested waterclock was in the old cluster.
sub affected_ztw {
    my $new_countername = shift;
    my $old_ztw = shift;
    # The zero-tested waterclock does not change between cluster B and cluster
    # A.
    return $old_ztw if $new_countername =~ /^A/;

    # The zero-tested waterclock increments (wrapping around) between cluster A
    # and cluster B.
    ($old_ztw % $waterclock_count) + 1
}

# Updates the values of the velocity_effect hashes, at the given key, for each
# counter in the other cluster that the given flooding counter affects (even
# indirectly) by adding $baseline_relative_velocity + 1 absolute velocity.
#
# This subroutine will enter an infinite recursive loop if two counters from the
# same cluster affect each other, but that is to be expected, as that situation
# wouldn't work in the Flooding Waterfall Model either (they would set up a
# self-sustaining loop that made it impossible for the cluster to zero).
sub update_velocity_effect;
sub update_velocity_effect {
    my $affected_by = shift;
    my $baseline_relative_velocity = shift;

    for my $affects (keys %{$flood_triggers{$affected_by}}) {
        if (same_cluster $affects, $affected_by) {
            # A same-cluster effect: recurse.
            update_velocity_effect $affects,
                $baseline_relative_velocity;
        } else {
            # A different-cluster effect: apply it.
            $absolute_velocity_effect{$affects} //= 0;
            $absolute_velocity_effect{$affects} += 1;

            for my $ztw (1..$waterclock_count) {
                my $brv = $baseline_relative_velocity;
                $brv = $brv->{$ztw} if ref $brv eq 'HASH';
                my $new_ztw = affected_ztw $affects, $ztw;
                $baseline_relative_velocity_effect{$affects}{$new_ztw} //= 0;
                $baseline_relative_velocity_effect{$affects}{$new_ztw} += $brv;
            }
        }
    }
}
for my $counter_that_zeroed (keys %flood_triggers) {
    update_velocity_effect $counter_that_zeroed,
        $baseline_relative_velocities{$counter_that_zeroed};
}

if ('trigger velocity effects' =~ $debug_regexp) {
    print STDERR "Effects of position triggers on velocities:\n";
    print STDERR "In units of the baseline (approximately):\n";
    print_countermap(\%absolute_velocity_effect);
    print STDERR "Modulo the baseline:\n";
    print_countermap(\%baseline_relative_velocity_effect);
    print STDERR "\n";
}

### Working out the required velocity change from the baseline flood triggers
#
# There is now enough information to know that velocity is required for each
# flooding counter (for a particular zero-tested waterclock), and what velocity
# it will have in the absence of baseline flood triggers.  Subtracting makes it
# possible to determine what effect the baseline flood triggers will need to
# have.

my %required_velocity_change;
for my $countername (keys %baseline_relative_velocities) {
    for my $old_ztw (1 .. $waterclock_count) {
        my $new_ztw = affected_ztw $countername, $old_ztw;
        my $desired_velocity = $baseline_relative_velocities{$countername};
        $desired_velocity = $desired_velocity->{$new_ztw} if
            ref $desired_velocity eq 'HASH';
        my $velocity_without_baseline =
            $baseline_relative_velocity_effect{$countername}{$new_ztw} // 0;
        my $required_change = $desired_velocity - $velocity_without_baseline;
        $required_velocity_change{$countername}{$new_ztw} = $required_change;
    }
}

if ('required velocity change' =~ $debug_regexp) {
    print STDERR "Required velocity change from baseline (modulo baseline):\n";
    print_countermap(\%required_velocity_change);
    print STDERR "\n";
}

### Working out the non-neutral baseline flood triggers
#
# This is almost simply a case of "find the minimum required velocity change
# from baseline (or 0 if lower), and minus that is the flood trigger from the
# negative baseline; then for each ZTW, the difference from the minimum value
# and that ZTW's value gives the flood trigger from that ZTW's positive
# baseline". There are three subtleties:
#
# * The neutral and positive baselines don't need any input from the negative
#   baseline for velocity reasons. However, they do need such an input for
#   position reasons, to stop their position drifting away from the negative
#   baseline's.  Thus, 0 is calculated as -1 + 1 (and 1 as -1 + 2), rather than
#   the more obvious calculations of 0 + 0 and 0 + 1.
#
# * Each cluster is taking its velocities from the other cluster's baselines.
#   In cluster B, the ZTW will have changed, so the triggers from cluster A for
#   cluster B will need to cyclically shift the positive baselines. The easiest
#   way to handle this is to loop over the baselines and see what they affect,
#   rather than vice versa (which might be more natural).
#
# * Every use of a flooding counter, whether baseline or not, will add the b**c
#   that the velocities are measured relative to.  These need to be counted in
#   order to get the neutral baselines correct later.

my %absolute_velocity_change_so_far = (%absolute_velocity_effect);

for my $negative_baseline ("A baseline negative", "B baseline negative") {
    for my $countername (keys %required_velocity_change) {
        same_cluster $countername, $negative_baseline and next;
        my $minimum = $countername =~ /\bbaseline\b/ ? -1 : 0;
        for my $required_change (values %{
            $required_velocity_change{$countername}}) {
            $required_change < $minimum and $minimum = $required_change;
        }
        # this shouldn't be set yet: assert that it isn't
        $flood_triggers{$negative_baseline}{$countername} and die;
        $flood_triggers{$negative_baseline}{$countername} = -$minimum
            unless $minimum == 0;
        $absolute_velocity_change_so_far{$countername} //= 0;
        $absolute_velocity_change_so_far{$countername} += -$minimum;
    }
}
for my $positive_baseline (keys %baseline_relative_velocities) {
    $positive_baseline =~ /^([AB]) baseline (\d+) positive\b/ or next;
    my $old_cluster = $1;
    my $old_ztw = $2;
    for my $countername (keys %required_velocity_change) {
        same_cluster $countername, $positive_baseline and next;
        my $new_ztw = affected_ztw $countername, $old_ztw;
        # positive amount required = enough to do the required velocity change
        # plus enough to cancel out any negative amount
        my $required = $required_velocity_change{$countername}{$new_ztw} +
            $flood_triggers{"$old_cluster baseline negative"}{$countername};
        # again, this shouldn't be set yet
        $flood_triggers{$positive_baseline}{$countername} and die;
        $flood_triggers{$positive_baseline}{$countername} = $required
            unless $required == 0;
        $absolute_velocity_change_so_far{$countername} //= 0;
        $absolute_velocity_change_so_far{$countername} += $required;
    }
}

if ('early flood triggers' =~ $debug_regexp) {
    print STDERR
        "Flood triggers, except for neutral baseline, startup and sustain:\n";
    for my $countername (sort keys %flood_triggers) {
        print STDERR "$countername:\n";
        for my $affected (sort keys %{$flood_triggers{$countername}}) {
            print STDERR "  $affected: ",
                $flood_triggers{$countername}{$affected}, "\n";
        }
    }
    print STDERR "\n";
}

### Working out b
#
# Every counter's velocity, which was previously measured relative to b**c, will
# need to be measured relative to b**(c+1) in the next cluster.  That means that
# each counter's absolute velocity change needs to be b.  It is possible to
# increase the absolute velocity change (using the flood trigger of the neutral
# baseline), but not to decrease it; thus b must be at least as large as the
# highest absolute velocity change so far.

my $b = 0;
$b < $_ and $b = $_ for values %absolute_velocity_change_so_far;

if ('b value' =~ $debug_regexp) {
    print STDERR "Value of 'b' = highest velocity change in " .
        "units of b**c = $b\n\n";
}

### Working out the neutral baseline flood triggers
#
# Just take the absolute velocity change so far, and subtract from b.

for my $neutral_baseline ("A baseline neutral", "B baseline neutral") {
    for my $countername (keys %baseline_relative_velocities) {
        same_cluster $countername, $neutral_baseline and next;
        $absolute_velocity_change_so_far{$countername} //= 0;
        $flood_triggers{$neutral_baseline}{$countername} =
            $b - $absolute_velocity_change_so_far{$countername};
    }
}

if ('neutral baseline flood triggers' =~ $debug_regexp) {
    print STDERR "Neutral baseline flood triggers:\n";
    for my $countername ("A baseline neutral", "B baseline neutral") {
        print STDERR "$countername:\n";
        for my $affected (sort keys %{$flood_triggers{$countername}}) {
            print STDERR "  $affected: ",
                $flood_triggers{$countername}{$affected}, "\n";
        }
    }
    print STDERR "\n";
}

##### Sustain
#
# The sustain counter is always supposed to have the same value as the larger
# zero counter.  As such, any flood trigger in which a counter in one cluster
# affects the zero counter of the other needs to be changed to also affect the
# sustain counter.
for my $countername (keys %flood_triggers) {
    for my $affected_counter (keys %{$flood_triggers{$countername}}) {
        $affected_counter =~ /\bzero\b/ or next;
        same_cluster $countername, $affected_counter and next;
        $flood_triggers{$countername}{"sustain"} =
            $flood_triggers{$countername}{$affected_counter};
    }
}

if ('sustain flood triggers' =~ $debug_regexp) {
    print STDERR "Flood triggers affecting sustain:\n";
    for my $countername (sort keys %flood_triggers) {
        next unless $flood_triggers{$countername}{"sustain"};
        print STDERR "$countername:\n";
        print STDERR "  sustain: ",
            $flood_triggers{$countername}{"sustain"}, "\n";
    }
    print STDERR "\n";
}

####### Initial state
#
# We need to pick some arbitrary state to start the program up in.  The choice
# here is to use cluster B, with the first counter being zero-tested (cluster B
# is a better choice for startup because it has fewer distinct position/velocity
# pairs among its counters, meaning that it is an easier state to start in).
# Once that choice has been made, it is possible to gradually calculate the
# other components of the initial state:
#
##### Initial position of "zero" relative to the baselines
#
# The initial position of "zero" needs some care, because a) it hasn't been
# determined yet, b) it depends on something that has not yet been relevant in
# the code (the starting values of the counters), and c) it indirectly
# determines the starting value of c.  The first step is to calculate its
# position relative to the baselines; this relative position is (-c*r--c)-z
# (despite not knowing c, it is possible to calculate and fix z because it's OK
# for the zero position to be too early, just not too late, so a sufficiently
# large z will work regardless of the value of c as long as r is at least 1, and
# it must be for any non-degenerate program). z needs to be large enough to
# accomodate twice the starting value of any counter, plus 2 (because the
# encoding is 2n+2), plus another 1 (to ensure that the counters are strictly
# before the baseline).
#
# For the time being, we just calculate z, and the initial position of zero can
# be calculated once c is known.

$r < 1 and die "r < 1: the input program must have been entirely degenerate";

my $max_initial_value = 1;
for my $waterclock (1..$waterclock_count) {
    my $initial_value = $program->[$waterclock][0];
    $initial_value > $max_initial_value and
        $max_initial_value = $initial_value;
}
my $z = $max_initial_value * 2 + 3;

if ('z value' =~ $debug_regexp) {
    print STDERR "Highest initial waterclock value is $max_initial_value\n";
    print STDERR "Thus, value of 'z' is $max_initial_value * 2 + 3 = $z\n\n";
}

##### Initial value of c
#
# Some startup states are impossible, and others inefficient. In order to make
# startup work efficiently, the difference between the smallest and largest
# position across the various nonzero counters needs to be less than (one half
# of the smallest nonzero velocity) minus (one third of the largest nonzero
# velocity).  Increasing c increases the latter quantity much faster than it
# increases the former, so it is possible to produce a viable startup state by
# using a sufficiently large c.
#
# The difference between the smallest position (that of "zero") and of the
# largest position (that of the baselines) is c*r-c+z.  The velocities relative
# to b**c are known, so it is possible to test any given value of c by adding
# the smallest and largest to b**c.
#
# It is very likely that small values of c will be sufficient, so rather than
# messing around with logarithms, the integers are tested in turn until we find
# one that works.

my $min_brv = 0;
my $max_brv = 0;
for my $countername (keys %baseline_relative_velocities) {
    $countername =~ /^B\b/ or next;
    my $velocity = $baseline_relative_velocities{$countername};
    $velocity = $velocity->{1} if ref $velocity eq 'HASH';
    $velocity < $min_brv and $min_brv = $velocity;
    $velocity > $max_brv and $max_brv = $velocity;
}

my $c = 0;
# be sure to round in the way that increases rather than reduces the safety
# margin
++$c while $c*$r-$c+$z >= ($b**$c+$min_brv)/2 - ($b**$c+$max_brv+2)/3;

if ('c value' =~ $debug_regexp) {
    print STDERR "Minimum baseline-relative velocity in B1 is $min_brv\n";
    print STDERR "Maximum baseline-relative velocity in B1 is $max_brv\n";
    print STDERR "Value of 'c' is $c\n";
    print STDERR "This is chosen so that c*r-c+z (", $c*$r-$c+$z,
        ") < floor(b**c+min)/2 - ceil(b**c+max)/3 (",
        ($b**$c+$min_brv)/2 - ($b**$c+$max_brv+2)/3, ")\n\n";
}

##### Initial positions and velocities
#
### Initial relative positions
#
# The expected positions at this point were listed in comments earlier, but not
# yet in code, so those are listed here.  Only nonzero counters have a position;
# that's the cluster B counters, plus the sustain counter.  Counters in cluster
# A start with zero velocity and an undefined position.  Positions have no
# meaning in an absolute sense (only their relative values matter), but the
# comments so far have been considering them as being measured relative to
# sum(i=1..=c) b**i.

my %relative_position;

# baselines are at position -c relative to the position anchor
$relative_position{"B baseline neutral"} = -$c;
$relative_position{"B baseline negative"} = -$c;
for my $waterclock (1..$waterclock_count) {
    $relative_position{"B baseline $waterclock positive"} = -$c;
}
# zero is at -c*r-z
my $zero_position = -$c*$r-$z;
$relative_position{"B zero"} = $zero_position;
# waterclock positions are $zero_position + 2 + 2 * w where w is the value
# exception: waterclock 1's test position is 2 spaces earlier
for my $waterclock (1..$waterclock_count) {
    my $initial_value = $program->[$waterclock][0];
    my $position = $zero_position + 2 + 2 * $initial_value;
    $relative_position{"B value $waterclock"} = $position;
    $relative_position{"B test $waterclock"} =
        $waterclock == 1 ? $position - 2 : $position;
}
# sustain has absolute position of 0; its relative position is not calculated

if ('relative initial position' =~ $debug_regexp) {
    print STDERR "Relative initial positions:\n";
    print_countermap(\%relative_position);
    print STDERR "\n";
}

### Initial absolute positions
#
# The position anchor used so far is in many cases not ideal for startup: in
# order to make startup work, a flooding waterclock's position needs to be
# between one third and one half of its velocity (making it possible to
# initialise it by adding first its position to it, at time equal to its
# position; then its velocity minus position to it, at time equal to its
# velocity minus position; with a position greater than one half, the additions
# would happen in the wrong order, and with a position less than one third, the
# counter would zero before the second addition happened).
#
# As such, the positions are moved so that the smallest position
# ($zero_position) is moved to the ceiling of one third of the maximum velocity
# (the maximum velocity is $max_brv + b**c).

my $position_anchor = ($max_brv + $b**$c + 2) / 3 - $zero_position;

my %absolute_position;
$absolute_position{$_} = $relative_position{$_} + $position_anchor
    for keys %relative_position;

# the sustain counter has an absolute position of 0 (otherwise the program would
# halt before it even started)
$absolute_position{"sustain"} = 0;

# sanity check that all non-cluster-B counters have positions
defined $absolute_position{$_} or $_ =~ /^A\b/ or die
    for keys %baseline_relative_velocities;

if ('absolute initial position' =~ $debug_regexp) {
    print STDERR "Absolute initial positions:\n";
    print_countermap(\%absolute_position);
    print STDERR "\n";
}

### Initial absolute velocities
#
# These are trivial; we just need to add b**c (the baseline velocity) to the
# baseline-relative velocity, which are all known quantities at this point.

my %absolute_velocity;
for my $countername (keys %absolute_position) {
    my $velocity = $baseline_relative_velocities{$countername};
    $velocity = $velocity->{1} if ref $velocity eq 'HASH';
    $absolute_velocity{$countername} = $velocity + $b**$c;
}

# the sustain counter needs to have value 1 when zero B has value 0, so its
# velocity is equal to the position + velocity of zero B + 1
$absolute_velocity{"sustain"} =
    $absolute_position{"B zero"} + $absolute_velocity{"B zero"} + 1;

if ('absolute initial velocity' =~ $debug_regexp) {
    print STDERR "Absolute initial velocities:\n";
    print_countermap(\%absolute_velocity);
    print STDERR "\n";
}

####### Startup code and output
#
##### Calculating the startup counters
#
# Now that we know the initial positions and velocities, the next step is to
# design startup code that will give all those flooding counters those positions
# and velocities before any of them zero.
#
# The basic idea is simple: our "startup flooding counters" each have an initial
# position of 0 and set velocity V, and are not incremented by anything (they
# just count down their velocity and do nothing thereafter).  Each non-startup
# non-sustain flooding counter that needs initialising to a nonzero position is
# listed in the flood triggers of two startup counters (or the same startup
# counter twice): that with V = its position, and that with V = its velocity
# minus its position.  When both of them flood, the first sets its position, and
# the latter will top up its velocity.
#
# This is implemented by adding the flood triggers first, and then looking at
# the flood triggers hash to see which startup counters are needed.

my %startup_velocities;

sub add_startup_counter {
    my $affected_counter = shift;
    my $startup_v = shift;
    $flood_triggers{"startup $startup_v"}{$affected_counter} //= 0;
    $flood_triggers{"startup $startup_v"}{$affected_counter}++;
    $startup_velocities{"startup $startup_v"} = $startup_v;
}

for my $countername (keys %absolute_position) {
    my $position = $absolute_position{$countername};
    # if the counter starts at position 0 it doesn't need a startup counter,
    # just start it out with value equal to its velocity
    unless ($position) {
        $startup_velocities{$countername} = $absolute_velocity{$countername};
        next;
    }

    add_startup_counter $countername, $position;
    add_startup_counter $countername,
        $absolute_velocity{$countername} - $position;
}

if ('startup flood triggers' =~ $debug_regexp) {
    print STDERR "Startup counters' flood triggers:\n";
    for my $countername (sort keys %flood_triggers) {
        next unless $countername =~ /^startup\b/;
        print STDERR "$countername:\n";
        for my $affected (sort keys %{$flood_triggers{$countername}}) {
            print STDERR "  $affected: ",
                $flood_triggers{$countername}{$affected}, "\n";
        }
    }
    print STDERR "\n";
}

##### Calculating the initial-value-and-flood-trigger matrix
#
### Giving indexes to the counters
#
# All the quantities needed have now been calculated; they just need to be put
# into matrix form. This means assigning a row/column index to each counter.
#
# A counter exists if a) it's a startup counter (in %startup_velocities) or b)
# it's in one of the clusters (in %baseline_relative_velocities). These have no
# overlap (the sustain counter doesn't really have a velocity, and the other
# startup counters zero before the main loop is entered and thus don't have a
# velocity relative to the baseline).

my %counter_indexes;
my $row_count = 1; # the header row / initial value column
for my $countername (sort(keys(%baseline_relative_velocities)),
                     sort(keys(%startup_velocities))) {
    $counter_indexes{$countername} = $row_count++;
}

if ('matrix indexes' =~ $debug_regexp) {
    print STDERR "Matrix rows assigned to each counter:\n";
    print_countermap(\%counter_indexes);
    print STDERR "\n";
}

### Creating the bulk of the matrix

my @output_matrix;

for my $row (0..$row_count-1) {
    for my $column (0..$row_count-1) {
        $output_matrix[$row][$column] = 0;
    }
}
for my $countername (keys %startup_velocities) {
    $output_matrix[$counter_indexes{$countername}][0] =
        $startup_velocities{$countername};
}
while (my ($affecting, $trigger) = each %flood_triggers) {
    while (my ($affected, $ratio) = each %$trigger) {
        $output_matrix[$counter_indexes{$affecting}]
            [$counter_indexes{$affected}] = $ratio;
    }
}

### Creating the header line

for my $column (1..$row_count) {
    $output_matrix[0][$column] = $row_count-1;
}
for my $row (0..$row_count) {
    for my $column (0..$row_count) {
        $output_matrix[$row][$column] >= $output_matrix[0][0]
            and $output_matrix[0][0] = $output_matrix[$row][$column] + 1;
    }
}

print "[[";
for my $row (0..$row_count-1) {
    $row and print "],\n [";
    for my $column (0..$row_count-1) {
        $column and print ",";
        print $output_matrix[$row][$column];
    }
}
print "]]\n";