Advent of Code 2021 - Day 19

Useful Links

Concepts and Packages Demonstrated

Countercombinationsunpack / splatvisualisation

Problem Intro

After the trauma of dealing with Fish Math, you could reasonably expect that today’s challenge would be relatively simple. WRONG.

I spent several hours working on this. And then I ran it. It took 20 minutes to run, and came up with the wrong answer! So then I spent a couple more hours on it, finally producing a solution that gives the right answer, along with some cool visualisations. Phew! It takes under a minute to run.

So, we fired our probe into the deep, dark trench. Our probe has released a number of beacons and scanners into the water. The beacons and scanners remain motionless, in the water. We’re told:

Scanners can detect any beacons within 1000 units.
Scanners report back the locations of those beacons, relative to itself.
Scanners don’t know their own positions, or the positions of any other scanners.
We don’t know the orientation of any scanner. But we do know that all scanners will have some sort of orthogonal orientation, relative to other scanners.
We’re guaranteed at least 12 overlapping beacons per scanner. E.g. scanner x will be able to see many beacons, and scanner y will be able to see many beacons. Of the superset of those beacons, scanner x and scanner y should be able to see at least 12 in common.

The input data is in the form of blocks of scanner data (i.e. scanner 0, scanner 1, scanner 2, etc), where each block contains all the beacon coordinates that can be seen by that scanner, in x,y,z format. For example, our sample data (which I’ve trimmed for brevity) looks like this:

--- scanner 0 ---
404,-588,-901
528,-643,409
-838,591,734
390,-675,-793
-537,-823,-458
... etc

--- scanner 1 ---
686,422,578
605,423,415
515,917,-361
-336,658,858
95,138,22
... etc

Part 1

We’re asked to assemble the full map of scanners and beacons, and determine how many becaons there are.

Here’s my game plan:

Get all the beacon positions, relative to each scanner. This will be in the form of vectors.
The scanners can be of any orientation relative to one another. Ultimately, we need all the scanners and beacons to be in a common orientation. So I’m going to orient all scanners relative to Scanner 0.
For at least two scanners, we know that there will be at least 12 beacons where:
- ‘Scanner 0 -> beacon vector + beacon -> Scanner x vector’ will be the same vector.
- Or, alternatively, ‘Scanner 0 -> beacon vector - Scanner x -> beacon vector` will be the same vector. (I.e. if we’re going from Scanner x to the common beacon, the vector is in reverse, so subtracting has the same effect.)
But because we don’t know the relative orientations of Scanner 0 and Scanner x, we can’t simply subtract the Scanner x -> beacon vector, because we don’t know the orientation of this vector.
So, let’s just try ALL the different permutations of Scanner x -> beacon, for all the beacons connected to Scanner x. If we do that, we should find there’s only orientation that gives us at least 12 beacons in common.
Once we know this orientation, we then know where Scanner x is relative to Scaner 0, and consequently, we can now determine the location of all of Scanner x’s beacons, relative to Scanner 0.

Setup

There’s nothing much to say about this. We’re just using modules and functions we’ve used before.

from __future__ import annotations
import logging
from pathlib import Path
import time
import re
from collections import Counter, defaultdict
from typing import NamedTuple
from itertools import combinations, permutations
import matplotlib.pyplot as plt

logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s", 
                    datefmt='%H:%M:%S')
logger = logging.getLogger(__name__)
logger.setLevel(logging.DEBUG)

SCRIPT_DIR = Path(__file__).parent
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")

RENDER = False
OUTPUT_DIR = Path(SCRIPT_DIR, "output/")
OUTPUT_FILE = Path(OUTPUT_DIR, "trajectory.png")

MIN_OVERLAPPING_BEACONS = 12

I am using Matplotlib to plot the final solution in 3D space. I’m using RENDER to determine whether I render the plot interactively, or whether to save the plot as a file. More on this later.

Solution

Let’s create a Vector class, to store the relative vectors from each scanner to each beacon. We’ll include the capability to create new Vectors by adding or subtracting existing vectors:

class Vector(NamedTuple):
    """ Tuple that represents vector and knows how to add and subtract other vectors """
    x: int
    y: int
    z: int
    
    def __sub__(self, other):
        """ Subtract other vector from this vector, returning new vector """
        return Vector(self.x - other.x,
                      self.y - other.y,
                      self.z - other.z,)
        
    def __add__(self, other):
        """ Add other vector from this vector, returning new vector """
        return Vector(self.x + other.x, 
                      self.y + other.y,
                      self.z + other.z)

    def __str__(self):
        return f"({self.x},{self.y},{self.z})"

Here we’re overriding __sub__() and __add__() methods, allowing us to use the - and + operators, in order to add Vectors, respectively.

Now, let’s read in all the scanners and their relative beacon locations, as a dictionary of {scanner number, set(beacon vectors)}.

def get_beacons_and_scanners(data: str) -> dict[int, set[Vector]]:
    """ Return dict containing {scanner_num, set(Vector) """
    scanner_pattern = re.compile(r"--- scanner (\d+) ---")
    
    beacons_by_scanner = defaultdict(set)
    scanner_num = 0
    for line in [line.strip() for line in data.splitlines() if line != ""]:
        if "scanner" in line:
            if match := scanner_pattern.match(line):
                scanner_num = int(match.group(1))
        else:
            x, y, z = map(int, line.split(","))
            vec = Vector(x,y,z)
            beacons_by_scanner[scanner_num].add(vec)
    
    return beacons_by_scanner

with open(INPUT_FILE, mode="rt") as f:
    data = f.read()

beacons_by_scanner = get_beacons_and_scanners(data)  # {int: set(Vector)}

total_scanners = len(beacons_by_scanner)
all_located_beacons = set(beacons_by_scanner[0]) # initialise with all beacons for scanner 0
scanner_locations: dict[int, Vector] = {}   # scanners we have locations for
scanners_not_located = set(int(scanner) for scanner in beacons_by_scanner)  # Scanner numbers
    
scanner_locations[0] = Vector(0, 0, 0)  # store our known scanner location
scanners_not_located.remove(0)

The get_beacons_and_scanners() method processes the input data, building up a dictionary where the keys are scaner numbers, and the values are a set of Vectors to each beacon, from this scanner.

Then we:

Create a set of all located beacon vectors, relative to scanner 0. At first, this set will only contain the vectors to get from Scanner 0 to all of Scanner 0’s beacons. But as we progress and determine the locations of other beacons relative to Scanner 0, we’ll add them to this set.
Assume Scanner 0 is at Point 0,0,0.
Create a dictionary of {located scanner number, vector relative to Scanner 0}, called scanner_locations.
Create a set of unlocated scanners.

Next, we prepopulate all possible orientations that we can apply to any vector. We want these orientations to be applicable in a repeatable and consistent order.

# Prepopulate all orientations per that can be applied to any vector.
# First, get the 48 possible (x,y,z) orientations, in predictable order
orientations = get_orientations()   # ( ((0,1,2), (inv,inv,inv)), ... )

def get_orientations() -> tuple:
    """ Creates a set of 48 orientation parameters that can be applied to any vector
    to deliver a consistent list of re-oriented vectors.
    
    There are six permutations of (x,y,z), and for each, there are 8 permutations of inversions of axes x,y,z.

    Returns:
        tuple[tuple]: ( ((x,y,z permutation), (x,y,z axis inversion)), ...)
    """
    orientations = []
    # The perms are the [x, y, z] index positions, i.e.
    # [(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
    for perm in list(permutations([0, 1, 2])):
        orientations.append((perm, (0,0,0))) # e.g. ((0, 1, 2), (0, 0, 0))
        orientations.append((perm, (1,0,0)))
        orientations.append((perm, (0,1,0)))
        orientations.append((perm, (0,0,1)))
        orientations.append((perm, (1,1,0)))
        orientations.append((perm, (0,1,1)))
        orientations.append((perm, (1,0,1)))
        orientations.append((perm, (1,1,1)))  # This one IS needed!    
    
    return tuple(orientations) # (((0, 1, 2), (0, 0, 0)), ...)

In the instructions, we’re told:

“Each scanner could be in any of 24 different orientations: facing positive or negative x, y, or z, and considering any of four directions ‘up’ from that facing.”

I couldn’t get quite work out how to get to get 24 different orientations. So, my method generates 48 different permutations of any given orientation:

6 different ways of orienting any set of x,y,z coordinates.
Plus, for all 6 permutations, we have inversions of axes: -x -y -z
- x and y
- y and z
- x and z
- x, y and z

Thus, a total of 6 permutations, and 8 different inversion combinations; thus 6 * 8 = 48 different orientations.

In our input data, we have 40 scanners and approximately 30 beacons per scanner. So that gives us about 1200 vectors to work with, and 48 different orientations of those vectors to apply. So in total, that’s only about 60000 vector orientations. A small number for a computer, and it only takes a few milliseconds to prepulate all the orientations of all the vectors.

# Now apply all the orientations to each set of beacons,
# to end up with dict of {scanner:{orientation_id:[vec1, vec2...]}}
orientations_by_scanner = defaultdict(dict) # {scanner 0: {orientation 0: [vec1, vec2, ...]}}
for scanner in range(total_scanners):
    for orientation_index, orientation in enumerate(orientations):
        orientations_by_scanner[scanner][orientation_index] = 
                  [apply_orientation(orientation, vec) for vec in beacons_by_scanner[scanner]]

def apply_orientation(orientation: tuple, vector: Vector) -> Vector:
    """ Apply a reorientation of a vector, given an orientation and a vector.
    Orientation looks like ((x,y,z)(a,b,c)), where orientation[0] is x,y,z
    and orientation[1] is a,b,c, i.e. the axis inversion.
    Returns: a new vector """
    coord_list = [vector.x, vector.y, vector.z]
    x = coord_list[orientation[0][0]]
    y = coord_list[orientation[0][1]]
    z = coord_list[orientation[0][2]]
    
    x = x if orientation[1][0] == 0 else -x
    y = y if orientation[1][1] == 0 else -y
    z = z if orientation[1][2] == 0 else -z
    
    return Vector(x, y, z)

The apply_orientation() method works by taking a given x,y,z Vector, and then returning these coordinates a predefined order, with predefined axis inversions, as per the orientation that is passed in.

Finally, we:

Iterate through scanners we haven’t yet located.
- For each, iterate through each possible reorientation of the 48.
  - Apply the current to all the vectors to the probes, from the unlocated scanner. This gives us a list of adjusted (reoriented) vectors.
  - Store a Counter for any candidate vectors we identify, i.e. as the vector to get from Scanner 0 to the unknown scanner.
  - Subtract the adjusted Vector from each known probe Vector (from Scanner 0), to create candidate vectors.
  - If we find a candidate vector that appears at least 12 times, then we know we’ve found 12 probes in common. The candidate vector must be the vector to Scanner x, from Scanner 0. Mark scanner x as located.
  - Add this candidate vector to all of Scanner x’s probe vectors, to obtain new vectors to those probes, relative to Scanner 0.
  - Add these new vectors to the list of known probe vectors, relative to Scanner 0.

The code looks like this:

while scanners_not_located:     # scanners we still need to locate
    scanner_location_found = None
    for scanner in scanners_not_located:
        if scanner_location_found:
            break   # restart the loop, with one fewer unlocated scanner
        
        # We now iterate through all the possible orientations, one at a time
        for adjustment_ind in range(len(orientations)):
            assert len(orientations) == 48, "Orientations borked"
            
            # retrieve all beacon vectors for this unknown scanner, applying current adjustment
            adjusted_vecs: list[Vector] = orientations_by_scanner[scanner][adjustment_ind]
            
            candidate_vectors = Counter()
            # Iterate through all beacon vectors, relative to the unlocated scanner
            for adjusted_vec in adjusted_vecs:  
                for known_vec in all_located_beacons:
                    # Subtract adjusted vector from known vector, 
                    # in order to get a potential vector to the unknown scanner.
                    # We subtract because we want to get the vector TO the sensor, not FROM it.
                    # If we're oriented correctly and this beacon is common to more than one scanner
                    # then the candidate vector will be common to multiple beaacons.
                    candidate_vectors[known_vec - adjusted_vec] += 1
        
            candidate_scanner_vector, beacon_count = candidate_vectors.most_common(1)[0]
            if beacon_count >= MIN_OVERLAPPING_BEACONS: # we need at least this many overlapping beacons
                scanner_locations[scanner] = candidate_scanner_vector
                for vec in adjusted_vecs:
                    # add together adjusted vectors with vector of this scanner, relative to scanner 0.
                    # This gives us the new scanner's beacon vectors, relative to scanner 0.
                    all_located_beacons.add(candidate_scanner_vector + vec)
                    
                scanner_location_found = scanner    # Exit the "for scanner in" loop
                logger.debug("Found scanner %d at %s; remaining=%d", 
                              scanner, candidate_scanner_vector, len(scanners_not_located))
                break   # Don't need to try any more vector orientations
    
    assert scanner_location_found, "We must have found a scanner location"   
    scanners_not_located.remove(scanner_location_found)  # remove from list
  
# Part 1
logger.info("Part 1: Number of beacons = %d", len(all_located_beacons))

Blimey. That was trickly.

Part 2

What is the largest Manhattan distance between any two scanners?

Recall that the Manhattan distance is simply the sum of the x, y and z components of the Vector. So, we’re trying to find the two scanners that are furthest apart.

This is pretty easy to do. First, let’s update our Vector class so that it knows how to return the Manhattan distance between itself and another Vector:

    def manhattan_distance_to(self, other: Vector) -> int:
        """ Manhattan distance between this Vector and another Vector """
        diff = self-other
        return sum(abs(coord) for coord in diff)

This works by creating a new Vector called diff, by subtracting another Vector from this Vector. This gives us the Vector from one scanner to another. But we don’t care about direction; we only need magnitude. So, we go through each of the x,y and z components of this Vector, and sum up the absolute values of those components.

And finally, we go through all the combinations of two scanner locations, and get the Manhattan distance for each:

# Part 2
distances = []
for combo in combinations(scanner_locations.values(), 2):
    distances.append(combo[0].manhattan_distance_to(combo[1]))
    
logger.info("Part 2: Max Manhattan distance = %d", max(distances))

Note that itertools.combinations() is a lot like itertools.permutations(). But the former doesn’t care about order. So when using combinations(), a pair a,b is considered the same as b,a. And thus, because we only care about the absolute distance between any pair, we should be using combinations(), not permutations().

So finally, we have our output:

17:15.340:DEBUG:__main__:    Found scanner 27 at (1382,-30,-20); remaining=39
17:16.029:DEBUG:__main__:    Found scanner 19 at (1280,-1226,-40); remaining=38
17:17.066:DEBUG:__main__:    Found scanner 21 at (2477,-47,2); remaining=37
17:17.865:DEBUG:__main__:    Found scanner 13 at (2490,-5,-1182); remaining=36
17:18.203:DEBUG:__main__:    Found scanner 5 at (2480,-3,-2458); remaining=35
17:18.942:DEBUG:__main__:    Found scanner 10 at (2537,1246,-2376); remaining=34
17:19.781:DEBUG:__main__:    Found scanner 11 at (1205,1142,-1150); remaining=33
17:21.063:DEBUG:__main__:    Found scanner 15 at (3624,61,-1278); remaining=32
17:22.254:DEBUG:__main__:    Found scanner 12 at (3752,1215,-1257); remaining=31
17:23.309:DEBUG:__main__:    Found scanner 9 at (2530,2402,-1217); remaining=30
17:24.525:DEBUG:__main__:    Found scanner 14 at (3687,-1240,-1176); remaining=29
17:25.940:DEBUG:__main__:    Found scanner 17 at (2565,1122,-1218); remaining=28
17:27.634:DEBUG:__main__:    Found scanner 20 at (2566,-1130,-2367); remaining=27
17:30.304:DEBUG:__main__:    Found scanner 28 at (1267,42,1112); remaining=26
17:33.488:DEBUG:__main__:    Found scanner 30 at (4847,-15,-1282); remaining=25
17:34.513:DEBUG:__main__:    Found scanner 6 at (4832,80,-84); remaining=24
17:35.480:DEBUG:__main__:    Found scanner 7 at (3785,48,1211); remaining=23
17:36.840:DEBUG:__main__:    Found scanner 16 at (6041,14,-1191); remaining=22
17:39.643:DEBUG:__main__:    Found scanner 26 at (6132,-1177,-1173); remaining=21
17:42.454:DEBUG:__main__:    Found scanner 29 at (7324,-63,-1168); remaining=20
17:43.412:DEBUG:__main__:    Found scanner 4 at (8571,-45,-1296); remaining=19
17:46.261:DEBUG:__main__:    Found scanner 31 at (1258,-1243,1158); remaining=18
17:48.174:DEBUG:__main__:    Found scanner 22 at (1254,-1265,2471); remaining=17
17:48.442:DEBUG:__main__:    Found scanner 1 at (1212,-1236,3556); remaining=16
17:49.070:DEBUG:__main__:    Found scanner 3 at (1252,-1184,4724); remaining=15
17:50.481:DEBUG:__main__:    Found scanner 23 at (1276,54,3592); remaining=14
17:51.925:DEBUG:__main__:    Found scanner 24 at (124,-1141,2453); remaining=13
17:53.429:DEBUG:__main__:    Found scanner 25 at (1280,-2409,2479); remaining=12
17:55.400:DEBUG:__main__:    Found scanner 33 at (2450,92,1130); remaining=11
17:57.090:DEBUG:__main__:    Found scanner 34 at (1367,-2453,-57); remaining=10
17:57.914:DEBUG:__main__:    Found scanner 8 at (2468,-2482,55); remaining=9
17:58.083:DEBUG:__main__:    Found scanner 2 at (3607,-2449,-97); remaining=8
17:59.179:DEBUG:__main__:    Found scanner 35 at (1273,1108,78); remaining=7
17:59.496:DEBUG:__main__:    Found scanner 18 at (1321,2335,49); remaining=6
18:00.342:DEBUG:__main__:    Found scanner 36 at (172,2,-1300); remaining=5
18:00.351:DEBUG:__main__:    Found scanner 32 at (150,60,-2414); remaining=4
18:00.802:DEBUG:__main__:    Found scanner 37 at (2557,-1262,2305); remaining=3
18:01.028:DEBUG:__main__:    Found scanner 38 at (1370,-2400,-1165); remaining=2
18:01.520:DEBUG:__main__:    Found scanner 39 at (1253,14,2421); remaining=1
18:01.520:INFO:__main__:     Part 1: Number of beacons = 496
18:01.521:INFO:__main__:     Part 2: Max Manhattan distance = 14478
18:02.029:INFO:__main__:     Plot saved to f:\Users\Darren\localdev\Python\Advent-of-Code\src\AoC_2021\d19_scanners_and_beacons_orient_perms_combos\output\trajectory.png
18:02.032:INFO:__main__:     Execution time: 47.3569 seconds

The debug statements are to track how manner scanners are left to locate. This is useful, since it takes a minute or so to run. (Depending on whether I’m running this on my fast desktop, or my slow laptop!)

Visualisation

Lastly, let’s take a look at the visualisation code, which is using Matplotlib:

def plot(scanner_locations: dict[int, Vector], beacon_locations: set[Vector], outputfile=None):
    _ = plt.figure(111)
    axes = plt.axes(projection="3d")
    axes.set_xlabel("x")
    axes.set_ylabel("y")
    axes.set_zlabel("z")

    axes.grid(True) # grid lines on
    
    x,y,z = zip(*scanner_locations.values())    # scanner locations
    axes.scatter3D(x, y, z, marker="o", color='r', s=40, label="Sensor")
    offset=50
    for x, y, z, scanner in zip(x, y, z, scanner_locations.keys()): # add scanner numbers
        axes.text3D(x+offset, y+offset, z+offset, s=scanner, color="red", fontweight="bold")
    
    x,y,z = zip(*beacon_locations)
    axes.scatter3D(x, y, z, marker=".", c='blue', label="Probe", s=10)
    
    x_line = [min(x), max(x)]
    y_line = [0, 0]
    z_line = [0, 0]
    plt.plot(x_line, y_line, z_line, color="black", linewidth=1)
    
    x_line = [0, 0]
    y_line = [min(y), max(y)]
    z_line = [0, 0]
    plt.plot(x_line, y_line, z_line, color="black", linewidth=1)
    
    x_line = [0, 0]
    y_line = [0, 0]
    z_line = [min(z), max(z)]
    plt.plot(x_line, y_line, z_line, color="black", linewidth=1)
    
    axes.legend()
    plt.title("Scanner and Beacon Locations", fontweight="bold")

    if outputfile:
        dir_path = Path(outputfile).parent
        if not Path.exists(dir_path):
            Path.mkdir(dir_path)
        plt.savefig(outputfile)
        logger.info("Plot saved to %s", outputfile)        
    else:
        plt.show()

This works as follows:

We create a plot, and set project to 3d.
We add labels for the x, y and z axes.
We add gridlines.
We use zip() to turn the list of scanner location Vectors into three lists that represent all the x, y, and z values, respectively. (Recall tha plots need coordinates to be passed in using separate lists for each axis.) We use the splat * operator, to unpack all of the Vectors as separate values to the zip() function.
Then we render a scatter3D() plot, by passing in the x,y,z coordinates, specifying a marker type, marker colour (red), marker size, and labelling these (in a legend) as “Scanner”.
Then we use a for loop, and axes.text3D(), in order to add text annotations to each of these scanner points. The text used for each annotation is the key for the scanners dictionary, i.e. the scanner numbers themselves.
Now we do another scatter3D() but this time, for the beacon locations. We use a smaller marker type (a dot), a different colour (blue), make the markers smaller, and use a different label for the legend (“Probe”).
Then we use plt.plot() to add axis lines, for the x,y, and z axes, all passing through the origin, i.e. 0, 0, 0.
Then we add the legend, with axes.legend().
And then we add a plot title.
Finally, we either save to a file using plt.savefig(), or we display interactively, using plt.show(). This is the same as we’ve done in previous solutions.

The rendered output looks something like this:

Plot of Scanners and Beacons

‹›