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 pointAHEMsentence. 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 another solution 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!

UPDATE not 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!