Module aoc::year2021::day19

Beacon Scanner

A brute force approach is:

• Choose an arbitrary starting scanner, then add its beacons to a “known” set.
• For each remaining scanner, then for each of its possible 24 rotations, check its beacons by translating against every other beacon in the known set.
• If we find a match of 12 or more overlapping beacons, then merge the beacons into the known set.

This approach will work but is a little slow as the number of potential comparisions is quite high. We can speed things up by first creating a “signature” for each beacon similar to how a hash is computed for an item in a hash map. Ideally this signature should be the same no matter what the rotation of the beacons, as this will reduce the number of comparisons by a factor of 24.

The set of Euclidean distance squared between all beacons is a good choice, as it’s invariant under rotation and translation, quick to calculate and a good discriminant. To check for an overlap of 12 beacons, we look for an overlap of a least 12 * 11 / 2 = 66 distances. (12 beacons gives 12 * 11 = 132 pairs of distances but divided by 2 since the distance from a -> b is the same as b -> a).

An overlap indicates a potential match, but we need to confirm by checking the beacons against each other in two steps. First confirming orientation by matching the deltas between points, then by translating the beacons until 12 overlap.

Structs

• Found 🔒
  Returns the correct orientation and translation to link a new scanner to an existing reference scanner.
• Located
  Represents a known scanner with the same orientation and a known translation from our initial reference scanner.
• Point3D 🔒
  Stores coordinates in x, y, z order.
• Scanner 🔒
  Represents an unknown scanner that could be at any orientation and translation from our initial reference scanner.

Functions

• check 🔒
  At least 66 Euclidean distances must overlap for a potential match.
• detailed_check 🔒
  The correct translation and orientation is found when we have at least 12 beacons overlapping.
• parse
  Convert the raw input into a vec of unknown scanners, then do all the heavy lifting of figuring out the relative orientations and translations of each scanner.
• part1
  Calculate the total number of distinct beacons.
• part2
  Calculate the maximum manhattan distance between any two scanners.