TL;DR

On with Advent of Code puzzle 19 from 2021: GPS is smarter, here’s why… last post!

In the latest posts we drew the lines for the algorithm, leaving a couple of details out. By the way, these posts are:

• AoC 2021/19 - GPS is smarter
• AoC 2021/19 - GPS is smarter - part 2

We were left with two remaining things: finding 12 matches in two lists of numbers, and reading the inputs.

Let’s start with ListMatcher:

class ListsMatcher {
   has $!alice     is built is required;
   has $!berto     is built is required;
   has $!min-items is built = 12;
   has $!ia-max;
   has $!ib-max;
   has $!ia;
   has $!ib;
   has %!offsets;

   submethod TWEAK (:$!alice, :$!berto) {
      $!ia-max = $!alice.elems - $!min-items;
      $!ib-max = $!berto.elems - $!min-items;
      $!ia = $!ia-max + 1;  # just to decrease it at the beginning!
      $!ib = 0;
   }

   method next-match () {
      return Nil unless defined $!ia; # no more items

      loop {
         # advance for next match
         if    $!ia > 0        { --$!ia }
         elsif $!ib < $!ib-max { ++$!ib; $!ia = $!ia-max }
         else                  { return $!ia = $!ib = Nil }

         my $offset = $!alice[$!ia] - $!berto[$!ib];
         next if %!offsets{$offset}++;
         my ($a, $b) = $!ia, $!ib;
         my @matches;
         while $a <= $!alice.end && $b <= $!berto.end {
            my $va = $!alice[$a];
            my $vb = $!berto[$b];
            my $vbo = $vb + $offset;
            if    $va < $vbo { ++$a }
            elsif $va > $vbo { ++$b }
            else             { @matches.push: ($va, $vb); $a++; $b++ }
         }

         return @matches if @matches.elems >= $!min-items;
      }
   }
}

We’re using Alice and Berto here. I know that I was using Umberto before, and that B is usually Bob, but Berto is five letters long and aligns better with Alice, as well as being a valid Italian name!

It’s probably more complicated than it should be, because I wanted to express it as an iterator. So we have an object that keeps a lot of state because we want to emit a single positive match at a time.

There are two nested loops at work. The outer loop aligns one of Berto’s elements to one of Alice’s elements. The inner one checks if this alignment makes sense trying to find at least $!min-items elements that correspond to each other. The matching here is done in linear fashion, keeping an index $a for iterating over Alice and $b to iterate over Berto, and collecting a pair in @matches when the two associated values correspond.

If there are enough elements in @matches… it’s given back, otherwise on with the next loop!

The last bit is about reading the inputs and “massaging” them to ease the following parts:

sub generate-scanner ($name, @coords, $origin = (0, 0, 0)) {
   my @by-coord;
   my @repetitions;
   for @coords -> $p {
      for 0 .. $p.end -> $d {
         @repetitions[$d] //= 0;
         @repetitions[$d]++ if @by-coord[$d]{$p[$d]}:exists;
         @by-coord[$d]{$p[$d]}.push: $p;
      }
   }
   my @sorted = @by-coord.map: {
      my @straight = $_.keys».Int.sort.List;
      my @reversed = @straight.reverse.map: -*;
      [@straight, @reversed];
   };
   return Map.new(
      'name' => $name,
      'origin' => $origin,
      'coords' => @coords,
      'byc' => @by-coord,
      'lists' => @sorted,
      'repetitions' => @repetitions,
   );
}

sub get-inputs ($filename) {
   $filename.IO.slurp.split(/\n (\n+ | $)/)
   .grep({ .chars })
   .map(
      {
         my ($header, @inputs) = .lines;
         my @coords = @inputs.map: { .split(/ ',' /)».Int.Array }
         ($header) = $header.comb: /\d+/;
         generate-scanner("$header", @coords);
      }
   );
}

Each input line is split and filtered and… OK, the real action is in generate-scanner, where we go through the lists of beacons for each probe and pre-generate a few things to put in a hash:

• name is the name of the probe.
• origin is its origin. which is actually initialized at (0, 0, 0) but might be different when called from transform.
• coords is the list of coordinates for each beacon;
• byc is a list of three items, where different beacons are arranged by coordinate values along the three axes. Each coordinate value is associated to a list of beacons, because two beacons might overlap in one or two dimensions.
• lists: these are lists of values along each dimension, both in straight and reversed order (with the sign changed). As we saw, these lists help us doing the different coordinate changes and flipping when looking for the right orientation of a scanner with respect to the reference one(s).
• repetitions: this tracks how many repetitions are there in a list by coordinates. This is because the matching algorithm in ListMatcher is looking for 12 matches, but some might be overlapping so there might be less along one dimension.

So… I guess it’s everything at this point!

If you want… the whole code with some slight changes in naming (e.g. probe instead of scanner, borged instead of bound, …) can be found here.

I hope this will inspire you to try this puzzle… it’s been quite demanding for me, but well worth the effort!