The question posed for part 2 was: what is the Manhattan Distance between the two scanners that are furthest apart.

This means finding all the scanners' positions relative to each other, which in turn means we need to determine each scanner's orientation in 3D space.

Not the easiest thing to reason about, but I didn't think it would challenge me as much as it did.

I iterated over this problem more times than I care to admit, and as it was approaching Christmas, quite often with some alcohol inside me. I'll describe the approach that eventually worked for me in this post.

At a high level, I arbitrarily decide the first scanner is located at (0, 0). All other scanners have a position of null at this point. Then the main routine is basically trying to locate scanner's positions relative to each other. It compares scanners with unknown positions with scanners that have a known position.

while (Scanners.Any(s => s.Value.Position == null))
{
    for (var s1 = 0; s1 < Scanners.Count; s1++)
    {
        var originScanner = Scanners[s1];

        if (originScanner.Position == null)
        {
            continue;
        }

        for (var s2 = 0; s2 < Scanners.Count; s2++)
        {
            if (s1 == s2 || Scanners[s2].Position != null)
            {
                continue;
            }

            Scanners[s2].LocateRelativeTo(originScanner);
        }
    }
}

Okay, reasonable starting point. So, LocateRelativeTo compares the distances of each scanner's beacons as described in part 1. If there are enough matching beacon distances, we know that the scanner's areas overlap and can now try and work out the rest of the puzzle.

So, after calling methods GetMatchingDistances and ResolveMatchingBeacons which I have previously covered, LocateRelativeTo then calls FindTranslation.

FindTranslation take a list of pairs of beacon coordinates (a pair being the coordinates from scanner A's perspective and scanner B's perspective). It creates two PointCloud classes, one with scanner A's beacons the other with scanner B's.

The class finds a centre point of all the beacons and calls this (0, 0), it then translates all the beacons' coordinates relative to this.

One of the clouds can now be rotated around this centre point until all the beacons line up with the other. We now know how the scanners are oriented relative to each other. This is done in CheckCloudsMatch.

private bool CheckCloudsMatch(TransformParameters parameters)
{
    foreach (var targetPoint in _target.Points)
    {
        var transformed = RotatePoint(targetPoint, parameters);

        var match = _origin.Points.SingleOrDefault(p => p.Equals(transformed));

        if (match == null)
        {
            return false;
        }
    }

    return true;
}

The parameters are generated in the following fashion:

var permutations = new List<TransformParameters>();

var axisPermutations = new[] { Axis.X, Axis.Y, Axis.Z }.GetPermutations();

foreach (var axisPermutation in axisPermutations)
{
    permutations.Add(new TransformParameters(axisPermutation, new[] { Sign.Positive, Sign.Positive, Sign.Positive }));

    permutations.Add(new TransformParameters(axisPermutation, new[] { Sign.Positive, Sign.Positive, Sign.Negative }));

    permutations.Add(new TransformParameters(axisPermutation, new[] { Sign.Positive, Sign.Negative, Sign.Positive }));

    permutations.Add(new TransformParameters(axisPermutation, new[] { Sign.Positive, Sign.Negative, Sign.Negative }));

    permutations.Add(new TransformParameters(axisPermutation, new[] { Sign.Negative, Sign.Positive, Sign.Positive }));

    permutations.Add(new TransformParameters(axisPermutation, new[] { Sign.Negative, Sign.Positive, Sign.Negative }));

    permutations.Add(new TransformParameters(axisPermutation, new[] { Sign.Negative, Sign.Negative, Sign.Positive }));

    permutations.Add(new TransformParameters(axisPermutation, new[] { Sign.Negative, Sign.Negative, Sign.Negative }));
}

return permutations;

Once we know the scanners' orientation relative to each other and which beacon on scanner A maps to which beacon on scanner B, we can calculate their positions relative to each other.

Having done this, we now have a complete map of the space with all beacons and scanners locations relative to a fixed point.

After that, it is just a case of calculating the Manhattan distances between the scanners and returning the largest.

var highestDistance = 0;

for (var s1 = 0; s1 < Scanners.Count; s1++)
{
    var originScanner = Scanners[s1];

    for (var s2 = 0; s2 < Scanners.Count; s2++)
    {
        if (s1 == s2)
        {
            continue;
        }

        var distance = originScanner.GetManhattanDistanceFrom(Scanners[s2]);

        if (distance > highestDistance)
        {
            highestDistance = distance;
        }
    }
}

I had all this code in place, and it seemed to return expected results for one or two scanners, but not for all of them.

I tried tweaking all sorts of things to get this to work, all to no avail. This was driving me quite mad. It all looked like it should work.

After a long time and a lot of hair pulling, I spotted the issue and was able to move on.

The bug was in CheckCloudsMatch...

- foreach (var originPoint in _origin.Points)
+ foreach (var targetPoint in _target.Points)
  {
-     var transformed = RotatePoint(originPoint, parameters);
+     var transformed = RotatePoint(targetPoint, parameters);

-     var match = _origin.Points.SingleOrDefault(p => p.Equals(transformed));
+     var match = _target.Points.SingleOrDefault(p => p.Equals(transformed));

      if (match == null)
      {
          return false;
      }
  }

  return true;

Because this comparison was the wrong way around, I'd get the correct result for any scanner that overlaps with the arbitrary origin but incorrect results for scanners further along the chain.

Fudge.