# ETOOBUSY đźš€ minimal blogging for the impatient

# AoC 2022/16 - Paying a debt

**TL;DR**

Paying a debt left with AoC 2022/16 - Pressured shame, regarding the secondo part of Advent of Code puzzle 16 from 2022.

In AoC 2022/16 - Pressured shame, I left with this:

So yeah, I still have to go some way before I have a general solution program.

I guess that many times I just went on with my life, leaving a dangling
point*AHEM*sentence. Well, not this time!

As a recap, the insight I got from the solution MEGATHREAD is to
consider every possible pair of single-player solutions and take the
best two that are *compatible* with one another, i.e. that donâ€™t share
any valve. This basically means that the player and the elephant operate
on different valves.

I guess that just doing that would have led me to the solution, and
quickly. Alas, this was not working for the example input, because it
contains *too few* valves, and for increasing available times all of
them end up appearing in all solutions, making all of them have at least
one element in common.

As I said, in the full input this is probably not a problem, but weâ€™re aiming for complete solutions and quiet sleep nights, right? So more ideas are needed.

My boring idea is to *cut* longer solution so that they donâ€™t overlap
with each other, and see what happens. Imagine we have something like
this:

```
player 1> AA BB CC DD EE FF
player 2> AA GG HH II JJ BB
```

Ignoring the initial `AA`

, the do overlap, but itâ€™s easy to get rid of
the `BB`

in player 2 and get an acceptable pair of non-overlapping
solutions.

This adds more computation, because the evaluation of each pair of
solutions requires also this *backtracking*, which might happen in two
directions i.e. removing BB and what follows from player 2 (as in the
example above), or removing BB and what follows from player 1 (we canâ€™t
know beforehand which is better).

We remove the offending element and all elements after in the specific solution, because otherwise we would have to re-calculalate the solution itself without the single element, but this is probably part of

anothersolution that we will check later, so we donâ€™t need bothering.

## The pre-computed search tree

Just to make my life a bit more miserable, I opted for saving all
possible acceptable solutions (i.e. solutions within the time bound) as
a *tree* instead of a list of self-contained solutions. So I have a
first pass where I pre-compute all these solutions, saving also the
score for *intermediate* solutions, i.e. those sub-paths of a full
solutions that might be handy in our two-players scenario. As a matter
of fact, this is *just* a pre-computing caching phase.

```
sub fas ($graph, $minutes, $entry-node = 'AA') {
my %weight-for;
my $next-weight = 0x00; # avoid tracking the entry node
my $following-weight = 0x01;
my @parent-for = Nil,;
my @children-for = [];
my @node-at = Nil;
my @weight-at = Nil;
my @set-at = 0;
my @score-at = 0;
my %positions-for;
my @leaves;
my %seen;
sub r-fas ($parent-pos, $node, $minutes) {
return if $minutes <= 0;
return if %seen{$node}++;
if %weight-for{$node}:!exists {
%weight-for{$node} = $next-weight +| 0x00;
$next-weight = $following-weight +| 0x00;
$following-weight +<= 1;
}
my $node-wg = %weight-for{$node};
@node-at.push: $node;
@weight-at.push: $node-wg;
@parent-for.push: $parent-pos;
@score-at.push: @score-at[$parent-pos] + $graph<nodes>{$node}<rate> * $minutes;
@children-for.push: [];
@set-at.push: @set-at[$parent-pos] +| $node-wg;
my $my-pos = @parent-for.end;
%positions-for{$node-wg}.push: $my-pos;
@children-for[$parent-pos].push: $my-pos;
# recurse
for $graph<edges>{$node}.kv -> $neighbor, $cost {
samewith($my-pos, $neighbor, $minutes - 1 - $cost);
}
@leaves.push: $my-pos if $my-pos == @parent-for.end;
%seen{$node} = 0; # free up this $node
}
r-fas(0, $entry-node, $minutes);
return {
:@parent-for,
:@children-for,
:@node-at,
:@set-at,
:@score-at,
:%positions-for,
:@leaves,
:@weight-at,
};
}
```

Not the best in readability, mostly because of all the different
variables. I decided to go for an *inside-out* approach, where there are
different containers (mostly arrays) for different features, indexed by
the position of the specific path in the tree. In other terms, the tree
is represented as a collection of arrays; slot `i`

in these arrays
represents the data associated with a node of the search tree, arranged
linearly.

Nodes are represented as *weights*, which are powers of two (except
`AA`

, which has weight 0). This allows us to define *sets* as bit
fields, i.e. store in `@set-at`

the set of all nodes included so far in
the a path, so that we will be able to compare two solutions for
intersections in a quick way (a bitwise-AND operation). We also save the
weight/valve in a step inside `@weight-at`

.

As weâ€™re producing a tree, we keep both the `@parent-for`

each path
step, as well as all path steps children. This made me a bit uneasy,
because were not for keeping track of the children, this solution would
have been translated in C quite easily.

As anticipated, weâ€™re keeping the `@score-at`

each step of a path, so
that we can quickly compute the score of a sub-path in case we have to
cut part of the tail.

The `@node-at`

array keeps track of the valve that is opened at a
specific step, and itâ€™s not striclty needed, except if we want to print
the solution.

Variable `%positions-for`

keeps track of all positions in the â€śtreeâ€ť
where a specific valve is opened. We will see later that this comes
handy to do some pruning on the tree, while still keeping all
alternatives that might give us a meaningful solution.

Last, variable `@leaves`

gives us a view of all leaf nodes in the search
tree, i.e. those nodes that have no children because we run out of time.
This, too, will come handy later.

Operations to build the three are pretty straightforward, as they only require saving some info and moving on to children. A few caveats:

- we use
`%seen`

to avoid opening the same valve over and over in a path. It is checked and possibly set when entering a node recursively, then reset upon exiting. Itâ€™s just*depth-first*. - Running out of time means ignoring an alternative, so itâ€™s our stop-and-backtrack condition for building the tree.
- The â€śnodeâ€ť in the search tree at position 0 is a fake one, left there
to make it easy to always have a â€śparentâ€ť node for real search nodes.
We might probably turn the
`AA`

node to have this role, but I could not think of an easy way of doing this, and so Iâ€™m dedicating a slot to this ease of mind.

## Pairing solutions and computing the optimal pair

At this point, we can go over the search tree and look for the best pair of solutions.

The particular shape of the tree allows us to consider each possible
path as a candidate solution, even those that are stopped at an
intermediate valve and could be made longer *by themselves*. In other
terms, if this is an allowed solution within the 26 minutes time bound:

```
AA BB CC DD EE
```

then all of the following sub-paths can be considered valid solutions too:

```
AA
AA BB
AA BB CC
AA BB CC DD
```

The first one corresponds to a player not moving at all, leaving the other player to do all the work. Intuitively, this is hardly a valid solution, but I failed to find a reasonable way to express this in a pruning condition.

Another feature of the data structure for the search tree is that it
allows us to avoid comparing the same pair twice in an easy way. Each
path has an implicit integer associated, i.e. its position in the tree
array; it will suffice to compare a path *only* with paths that have a
higher position in the tree, so that we only do *forward* comparisons.
Not really improving on the complexity, but at least weâ€™re cutting half
of the time!

For each intermediate step, we can keep track of a list of candidate
*alternatives* that are compatible with our step. As an example, at the
very beginning, when player 1 is still on the initial valve `AA`

, *all*
viable solutions (i.e. all *leaves*) are valid pairings, and we can
compute the best score out of them.

As we move one step towards a valve, we have to remove all solutions (complete or partial) that include that valve. Again, this removal operation gives us a list of paths that are compatible, so that we can compute the total pairing score again and keep the best, and so on.

Letâ€™s take a look at the code:

```
sub fas-best ($solutions) {
my $best-score = 0;
my ($p1, $p2);
sub r-fas-best ($position, $leaves) {
my $base-score = $solutions<score-at>[$position];
my $weight = $solutions<weight-at>[$position];
my $set = $solutions<set-at>[$position];
# establish applicable leaves for calculations, start with inherited ones
my @leaves;
for @$leaves -> $leaf {
next if $leaf < $position; # cut duplicate checks
next if $solutions<set-at>[$leaf] +& $set; # intersection
@leaves.push: $leaf;
my $score = $base-score + $solutions<score-at>[$leaf];
if $score > $best-score {
$best-score = $score;
$p1 = $position;
$p2 = $leaf;
}
}
# add nodes before intersections
for $solutions<positions-for>{$weight}.Slip -> $after-leaf {
my $leaf = $solutions<parent-for>[$after-leaf];
# the following checks are the same as above for leaf nodes.
# Yes, this might use some refactoring...
next if $leaf < $position; # cut duplicate checks
next if $solutions<set-at>[$leaf] +& $set; # intersection
@leaves.push: $leaf;
my $score = $base-score + $solutions<score-at>[$leaf];
if $score > $best-score {
$best-score = $score;
$p1 = $position;
$p2 = $leaf;
}
}
# the very first run finds the best single-track solution, so we
# bothering further here, as "no leaves" means "single track".
return unless @leaves > 0;
samewith($_, @leaves) for $solutions<children-for>[$position].Slip;
}
r-fas-best(1, $solutions<leaves>);
say expand-path($solutions, $_) for $p1, $p2;
return $best-score;
}
```

At each (recursive) step, we get a list of *leaves* that were good for
the parent node. These leaves are also valid candidates when visiting a
node, except that we have to filter them for removing overlapping
solutions. This removal is done in the `for @$leaves -> $leaf`

loop.

If we stopped here, we would rely on actual optimal solutions to be
*complete* (i.e. span the whole time range of 26 minutes) and
*disjoint*. As already discussed, this is not true in the general case,
so we canâ€™t just blindly cut out *leaves*.

This is what the second `for`

loop is for. We go through all positions
where the node weâ€™re visiting appears for the first time (we saved this
in hash `positions-for`

, right?) and take the *previous* node as our new
*leaf*. Itâ€™s not a real leaf in the whole search tree, but it can be
considered a leaf node in the scenario where the following node in the
path cannot be used, right?

In both cases, leaf nodes are removed if there is any overlap, as well as if their identifier is lower than the position weâ€™re analyzing. This gives us the improvement we already discussed above.

If our filtering *leaves us with no leaves* (pun intended), it means
that the best we can do is go up to the leaf node of the path ourselves,
i.e. that the specific position (and all positions below) do not allow
for a valid pairing, so it only makes sense to consider the best leaf
node below. On the other hand, we already take the best out of *all*
leaf nodes when visiting the very first node `AA`

(remember? Player 1
remains in valve `AA`

, so player 2 is free to go through every possible
single-player solution), so thereâ€™s no need to look further into
single-player solutions. This accounts for the ```
return unless @leaves >
0
```

, just before recurring over all children nodes.

At the end of the function, weâ€™re printing the solutions, thanks to the following function:

```
sub expand-path ($solutions, $p is rw) {
my @path;
while ($p // 0) > 0 {
@path.unshift: $solutions<node-at>[$p];
$p = $solutions<parent-for>[$p];
}
return @path;
}
```

Itâ€™s just *cosmetics* and not strictly needed, but it helps inspecting
the solution for inconsistencies (e.g. the same valve appearing in both
solutions).

## Conclusion

The code above is not exceptionally fast, taking about 10 minutes to complete the search over my input. Anyway, this is an acceptable time by my standards, so I call it a win.

For this reason, Iâ€™m not ashamed any more of the full solution!

UPDATEnot happy with waiting 10 minutes, and would rather spend 20 seconds? Make sure to take a look at AoC 2022/16 - OMG what an improvement, then!

Thanks for enduring so farâ€¦ and stay safe!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*