ETOOBUSY 🚀 minimal blogging for the impatient

AoC 2021/19 - GPS is smarter - part 2

· #advent of code #coding #rakulang #algorithm

TL;DR

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

In the last post of 2021 (AoC 2021/19 - GPS is smarter) we left with a high level solution for the puzzle, but I did not include the real workhorse, that is how to match the “local” views of two different scanners.

In particular, two scanners have a positive match if it’s possible to relate at least 12 beacons from one view to the other. But how can that be done?

The first thing to be addressed is that two different scanners might have completely different orientations. What is the positive X dimension for one scanner, might be the negative Z dimension for another scanner. This means that we will have to keep one of the two fixed, while trying all different possible arrangements for the other one.

All in all, then, we have to consider:

  • 6 possible ways of arranging the three dimensions:
XYZ XZY YXZ YZX ZXY ZYX
  • for each of them, 8 possible ways of arranging the orientation, e.g. for the first:
 X  Y  Z
 X  Y -Z
 X -Y  Z
 X -Y -Z
-X  Y  Z
-X  Y -Z
-X -Y  Z
-X -Y -Z

for a total of 48 possible orientations. This is not a big deal, though, because it “just” means that we have to remix the input coordinates for the beacons seen by a scanner, possibly with a change of sign; after doing this, anyway, the matching algorithm would be the same for each of the 48 arrangements.

In our code we are representing each position with a triple of integers, with X, Y, and Z associated to positions 0, 1, and 2 in each triple. To get the first dimension to associate to X, then, we can iterate from 0 to 2; to iterate through the two orientations for X, we can iterate from 0 to 1.

So here we are with match-scanners:

sub match-scanners ($alice, $umberto) {
   for 0 .. 2 -> $xd {
      for 0, 1 -> $xdf {
         my $lm = ListsMatcher.new(
            alice => $alice<lists>[0][0],
            umberto => $umberto<lists>[$xd][$xdf],
            min-items => (12 - $umberto<repetitions>[$xd]),
         );
         while my $m = $lm.next-match {
            my @pairings;
            for @$m -> ($va, $vbc) {
               my $vb = $xdf ?? -$vbc !! $vbc;
               for $alice<byc>[0]{$va}.List X $umberto<byc>[$xd]{$vb}.List
                  -> ($ap, $bp) { @pairings.push: ($ap, $bp) }
            }
            for @pairings.combinations(12) -> $c {
               my @yzs = check-pairings($c, $xd);
               next unless @yzs.elems > 1;

               # YAY! matching, return transformed $umberto wrt $alice
               my $x = $c[0][1][$xd];
               my $xdo = $c[0][0][0] - ($xdf ?? -$x !! $x);
               #($xd, $xdf, $xdo, |@yzs).note;
               return transform($umberto, $xd, $xdf, $xdo, |@yzs);
            }
         }
      }
   }
   return;
}

As you can see, the outer loops go through to get the X-dimension ($xd 0 to 2) and the X-orientation ($xdf, i.e. the factor for the X-dimension).

OK, we now have an iteration for the X dimension, what about the other two? In our algorithm we don’t explicitly loop through them… well, not here at least. To have a successful match of 12 beacons, they must match in each dimension (modulo the different arrangements), so why not start with the X dimension only?

So, we extract two lists, one for the X dimension of the fixed scanner, one for the candidate X dimension for the “movable” scanner, along with its sign. As we already knew we would need them, we find them conveniently pre-calculated in $alice<lists>[0][0] and $umberto<lists>[$xd][$xdf].

The ListMatcher does what the name says, i.e. it compares two lists against each other to find whether they match. A match, in this case, means that the two lists have at least 11 relative gaps that are the same across the two lists, like in the following example with 3 matching gaps and 4 matching positions only:

alice   -10  -5   -1     2  5     8   13  
              |<-->|<--->|<------>|
umberto       5 7  9     12   16  18

The ListMatcher returns an iterator that will output all possible matching of 12 X positions or more, so that we can do some further checking. We are guaranteed that there will be 12 or more matches between two different scanners, but along each dimensions there might be more and we have to check them all, using the other dimensions.

This is done in the while loop inside:

while my $m = $lm.next-match {
   my @pairings;
   for @$m -> ($va, $vbc) {
      my $vb = $xdf ?? -$vbc !! $vbc;
      for $alice<byc>[0]{$va}.List X $umberto<byc>[$xd]{$vb}.List
         -> ($ap, $bp) { @pairings.push: ($ap, $bp) }
   }
   for @pairings.combinations(12) -> $c {
      my @yzs = check-pairings($c, $xd);
      next unless @yzs.elems > 1;

      # YAY! matching, return transformed $umberto wrt $alice
      my $x = $c[0][1][$xd];
      my $xdo = $c[0][0][0] - ($xdf ?? -$x !! $x);
      #($xd, $xdf, $xdo, |@yzs).note;
      return transform($umberto, $xd, $xdf, $xdo, |@yzs);
   }
}

We first extract the (12 or more) paired points into @pairings, by iterating over the match $m. The $va is the value for Alice, while the $vbc is the candidate value for Umberto.

Yes, it was initially called Berto, but Umberto was better to express the concept of unbound.

So the value for Umberto is actually $vb, calculated based on the axis flipping (which is actually a sign change).

Here we leverage something other that we pre-calculated inside the two scanners, placed in the hash associated to byc (i.e. “by coordinate”), that indexes each beacon by coordinate in a list (usually containing one single beacon, but possibly more in case of overlaps).

As there might be more than 12 pairings inside, we have also to consider all possible subsets of 12 items, so we iterate over @pairings.combinations(12). This will also take care of possible overlaps over the X dimensions of two beacon positions.

OK, now we have twelve possible associations of beacons… are they the right ones? This is what check-pairings is for. It takes them (as well as the indication of which dimension in Umberto is considered the X) and returns, if they match, what dimensions are associated to the Y and Z dimensions for Umberto, as well as their orientation. Otherwise… it does not return enough stuff, and we can check another combination.

But if it worked… it’s a match! So we can transform Umberto according to this with transform(), using for each axis:

  • what axis it comes from
  • whether the sign is flipped or not
  • what is the offset

This will eventually bring Umberto in Alice’s coordinate system, so we just have to return it.

Let’s see this transform - quite boring, I know:

sub transform ($src, $xd, $xdf, $xdo, $yd, $ydf, $ydo, $zd, $zdf, $zdo) {
   my @coords = $src<coords>.map: -> $p {
      my ($x, $y, $z) = $p[$xd, $yd, $zd];
      $x = $xdo + ($xdf ?? -$x !! $x);
      $y = $ydo + ($ydf ?? -$y !! $y);
      $z = $zdo + ($zdf ?? -$z !! $z);
      ($x, $y, $z);
   };
   return generate-scanner($src<name>, @coords, ($xdo, $ydo, $zdo));
}

We will see generate-scanner in a future post, don’t worry!

Time for check-pairings, that makes sure that the twelve associations are actually consistent, i.e. all possible with a single set of translations over the three dimensions:

sub check-pairings ($pairs, $xd) {
   my @ds = (0 .. 2).grep: * != $xd;
   OUTER-LOOP:
   for (@ds, @ds.reverse.Array) X (0, 1) X (0, 1) -> (($yd, $zd), $ydf, $zdf) {
      my ($y, $z) = $pairs[0][1][$yd, $zd];
      my $y-offset = $pairs[0][0][1] - ($ydf ?? -$y !! $y);
      my $z-offset = $pairs[0][0][2] - ($zdf ?? -$z !! $z);
      for @$pairs -> ($a, $b) {
         my ($y, $z) = $b[$yd, $zd];
         next OUTER-LOOP if $y-offset != $a[1] - ($ydf ?? -$y !! $y);
         next OUTER-LOOP if $z-offset != $a[2] - ($zdf ?? -$z !! $z);
      }
      return $yd, $ydf, $y-offset, $zd, $zdf, $z-offset;
   }
   return [];
}

As you might remember, so far we only looped over candidates for the X-dimension and the X-orientation, so it’s time to loop over the other two. We do it here because… we can’t delay this any more! Luckily we’re only dealing with 12 points, so it’s a more restricted situation.

Looping over the different dimensions is expressed in a compact way in the for loop specification: we isolate the “remaining” dimensions into @ds, and consider it as well as its reverse; then all possible values for flipping over the Y and Z dimensions. Overall a three-parts cartesian product, nifty!

Inside each loop we first calculate the offsets based on the first association, then we verify that the same offset applies to all pairs. We might skip the first one here… but who cares?

If the match is successful we return the specific arrangement along with the offset, as we already saw.

There are still a couple things that we have to iron out at this point… matching two lists of numbers, and getting the inputs. This will be, my friends, material for another post.

Stay safe in the meantime!

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

ETOOBUSY © 2023 by polettix ― Powered by Jekyll and the TextLog theme