TL;DR

On with Advent of Code puzzle 11 from 2016: implementing graph functions.

In previous post AoC 2016/11 - Initial algorithm: Dijkstra we saw how to address our problem by leveraging the Dijkstra Algorithm for finding the shortest path from the initial state to the goal. We left with the need to provide two functions:

• id_of to generate a unique and consistent identifier for states, and
• successors_for, to generate the list of states that can be reached from a given one.

Identifier

Let’s start with the easier one, which is just a one-liner:

sub id_of { join "\n", '---', reverse map { join '', $_->@*} $_[0]->@* }

Each floor’s contents are merged together inside the map, with no spaces; then, all floors are joined together with newlines. This representation doubles down to provide a visual representation of the specific state! The three-hyphens string at the beginning is useful to separate different identifier when printed one after another.

This is really it!

Successors

My initial idea for finding out successors was based on two halves:

• enumerate all potential moves possible in a given state;
• filter out those that lead to frying any microchip.

The enumeration part is easy to do… naïvely, like this:

• find where the elevator is - only the elevator can determine a move;
• check moves for the elevator that goes up or down one single floor, when possible;
• in each possible move direction, evaluate:
  • each item singularly
  • each pair of items

I know that this is very crude, but it works (at the expense of some checking). The code below basically implements this approach:

sub successors_for ($node) {
   my $cidx = elevator_floor_idx($node);
   my $cfloor = $node->[$cidx];
   my @successors;
   for my $tidx ($cidx - 1, $cidx + 1) {
      next if $tidx < 0 || $#$node < $tidx;
      my $tfloor = $node->[$tidx];
      for my $i (1 .. $#$cfloor) {
         next unless $cfloor->[$i];

         # try to move only this one
         if (my @new = move($node, $cidx, $tidx, $i)) {
            push @successors, \@new;
         }

         # now try to move this one with another one
         for my $j ($i + 1 .. $#$cfloor) {
            next unless $cfloor->[$j];
            if (my @new = move($node, $cidx, $tidx, $i, $j)) {
               push @successors, \@new;
            }
         }
      }
   }
   return @successors;
}

Finding out where the elevator is does not put any particular problem, it’s a matter of looking for it. Yes, I know that I could track it, but bear with me OK?!?

sub elevator_floor_idx ($node) {
   for my $candidate (0 .. 4) {
      next unless $node->[$candidate][0];
      return $candidate;
   }
   die "wtf?!?";
}

The whole logic for filtering out impossible moves is encapsulated in the move sub, which both builds up the landing state and checks for its validity:

sub move ($state, $cidx, $tidx, $i, $j = undef) {
   my @new = $state->@*; # shallow copy here
   $new[$_] = [$new[$_]->@*] for ($cidx, $tidx); # deep copy here
   for my $slot (0, $i, $j) {
      next unless defined $slot;
      $new[$cidx][$slot] = 0;
      $new[$tidx][$slot] = 1;
   }
   return @new if is_floor_safe($new[$cidx]) && is_floor_safe($new[$tidx]);
   return;
}

The first part builds up the new landing state. Note that two floors are always copied from the original ones - they are not changed, so it makes sense to reuse them - while two other are created anew to avoid overwriting the previous one. Yes, this might be taxing for the memory, but we’re in developer time saving mode here!

The check about the new state only needs to look at the two floors that got a change; they are verified through the calls to is_floor_safe:

sub is_floor_safe ($floor) {
   my $ng = grep {$floor->[2 * $_]} 1 .. $#$floor / 2 or return 1;
   for my $midx (1 .. $#$floor / 2) {
      next unless $floor->[$midx * 2 - 1];
      return 0 unless $floor->[$midx * 2];
   }
   return 1;
}

The algorithm here is… working. First we count how many generators we have on the floor and put the value in $ng. If there is none… the floor is safe by definition, so we can return immediately.

Otherwise, we have to check that each microchip on the floor is powered by the corresponding generator (a powered microchip is also a protected microchip). For this reason, we iterate over all the microchip slots, and return a false value if we find a microchip without the corresponding generator.

If all these checks are fine… we can return a success!

Time to run it!

The whole code can be found in the local version here.

Running it actually gives us the answer to the first part of the puzzle for day 11. First, a warm-up with the example in the puzzle text:

$ cat 11.tmp
The first floor contains a hydrogen-compatible microchip and a lithium-compatible microchip.
The second floor contains a hydrogen generator.
The third floor contains a lithium generator.
The fourth floor contains nothing relevant.
poletti@polebian:2016 (posts-11 *)$ time perl 11.pl 11.tmp 
11

real  0m0.078s
user  0m0.072s
sys	  0m0.004s

Then, on with the real input:

$ cat 11.input
The first floor contains a promethium generator and a promethium-compatible microchip.
The second floor contains a cobalt generator, a curium generator, a ruthenium generator, and a plutonium generator.
The third floor contains a cobalt-compatible microchip, a curium-compatible microchip, a ruthenium-compatible microchip, and a plutonium-compatible microchip.
The fourth floor contains nothing relevant.
poletti@polebian:2016 (posts-11 *)$ time perl 11.pl 11.input
33

real  0m31.129s
user  0m30.636s
sys   0m0.292s

We completed part 1, yay!