AoC 2021 D19: Beacon Scanner

| Problem statement | Source code | Tags: Image processingGeometry

← Previous Back to AoC Index Next →

This is like 2020 day 20, but in 3D. We have a list of sets of coordinates, and we need to pairwise align them via rotation and translation such that there are at least 12 overlapping points. As the problem already says, there are 24 orientations possible, so for each list of coordinates, we need to compute all 24 orientations, and find one that aligns with another list.

I align based on the 3D coordinate differences $(x_j - x_i, y_j - y_i, z_j - z_i)$ between each pair of points in the list, instead of their Euclidean distances, since the latter has less information: it cannot distinguish between $(1,2,2)$ and $(3,0,0)$, for example. If two sets of beacon coordinates ($A$ and $B$) contain at least 12 overlapping beacons, then there exists some rotation of $B$ that gives rise to at least $12 \times 11 = 132$ overlapping distance vectors. After obtaining the rotation, the translation ensues just by comparing the coordinates of any overlapping beacon pair.

A set of beacons gives rise to a map from distance vectors to the associated pair of beacons (again, because JavaScript doesn't have composite keys, I serialize the distance vectors as strings). The axes parameter encodes one of the 24 orientations: which original axis maps to x, y, z, and whether each axis is negated (flipped).

type Vec3 = [x: number, y: number, z: number];
type Axes = [
  x: number,
  xSign: number,
  y: number,
  ySign: number,
  z: number,
  zSign: number,
];

function transformAxes(coords: Vec3[], axes: Axes): Vec3[] {
  const [xAxis, xSign, yAxis, ySign, zAxis, zSign] = axes;
  return coords.map(
    (p): Vec3 => [p[xAxis] * xSign, p[yAxis] * ySign, p[zAxis] * zSign],
  );
}

function getDistsMap(beacons: Vec3[], axes: Axes): Map<string, [Vec3, Vec3]> {
  const dists = new Map<string, [Vec3, Vec3]>();
  const transformedScanner = transformAxes(beacons, axes);
  for (const coords1 of transformedScanner) {
    for (const coords2 of transformedScanner) {
      if (coords1 === coords2) continue;
      const d = vecSub(coords2, coords1);
      if (dists.has(d.join(","))) throw new Error("Duplicate distance");
      dists.set(d.join(","), [coords1, coords2]);
    }
  }
  return dists;
}

I maintain a set of aligned beacons, a list of aligned scanners, and a set of remaining unaligned scanners, starting by assuming scanner 0 is at the origin with no rotation:

const remaining = new Set<number>(
  Array.from({ length: scanners.length }, (_, i) => i),
);
remaining.delete(0);
let beaconPositions = scanners[0];
const scannerPositions: Vec3[] = Array.from({ length: scanners.length }, () => [
  0, 0, 0,
]);

Now, I start finding matching scanners one at a time. Each time, I compare the distance map of the next scanner to that of all aligned beacons, so that information from multiple aligned scanners can be combined to find the next alignment (I don't think this is actually necessary, but it makes the algorithm more robust).

findScanner: while (remaining.size > 0) {
  const alignedDists = getDistsMap(beaconPositions, [0, 1, 1, 1, 2, 1]);
  for (const j of remaining) {
    // 24 orientations to test for scanner j
    for (const axes of getOrientations()) {
      const distsJ = getDistsMap(scanners[j], axes);
      const commonDists = new Map<string, [[Vec3, Vec3], [Vec3, Vec3]]>();
      for (const dist of alignedDists.keys()) {
        if (distsJ.has(dist)) {
          if (commonDists.has(dist))
            throw new Error("Duplicate common distance");
          commonDists.set(dist, [alignedDists.get(dist)!, distsJ.get(dist)!]);
        }
      }
      if (commonDists.size < 132) continue;
      // Found a matching orientation, execute alignment
      // ...
      continue findScanner;
    }
  }
  throw new Error("Cannot make progress");
}

Once a matching orientation is found, I first rotate the scanner's beacons according to axes:

scanners[j] = transformAxes(scanners[j], axes);

Now we need to find the translation. We have a list of intersection points in both the aligned coordinate system and the unaligned one.

const commonDistEntries = [...commonDists.values()];
const overlapAligned = vecDedupe(
  commonDistEntries.flatMap((pairs) => pairs[0]),
);
const overlapUnaligned = vecDedupe(
  commonDistEntries.flatMap((pairs) => pairs[1]),
);
const translation1 = vecSub(overlapAligned[0], overlapUnaligned[0]);
const translation2 = vecSub(overlapAligned[1], overlapUnaligned[1]);

commonDistEntries looks like: [[[a1, a2], [b1, b2]], [[a3, a4], [b3, b4]]...]. It tells us that a1 corresponds to b1, a2 to b2, etc. Therefore, both overlapAligned and overlapUnaligned contain the same set of points, just in different coordinate systems. If we order them the same way, then the points in overlapAligned would one-to-one correspond to those in overlapUnaligned. Ideally, we want translation1 and translation2 to be the same, but there's one case where they can differ: when the unaligned coordinate system actually has been flipped about every axis. I'm not 100% sure why this happens since I thought the coordinate systems are all right-handed, but anyway, when this happens, we just need to flip overlapUnaligned about every axis:

let translation = translation1;
if (
  translation1[0] !== translation2[0] ||
  translation1[1] !== translation2[1] ||
  translation1[2] !== translation2[2]
) {
  translation = vecAdd(
    overlapAligned[0],
    transformAxes(
      [overlapUnaligned[overlapUnaligned.length - 1]],
      [0, -1, 1, -1, 2, -1],
    )[0],
  );
}

Now we can translate scanner[j] and merge its beacons into the ensemble of aligned beacons:

beaconPositions = vecDedupe([
  ...beaconPositions,
  ...scanners[j].map((coords) => vecAdd(coords, translation)),
]);
remaining.delete(j);
scannerPositions[j] = translation;

Part 1 asks for beaconPositions.length, and part 2 is trivial given scannerPositions.

← Previous Back to AoC Index Next →