Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Scanners and Beacons

Advent of Code 2021 - Day 19

Day 19: Beacon Scanner

Useful Links

Concepts and Packages Demonstrated

DefaultDictmatplotlibpermutations

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:

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:

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:

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:

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:

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:

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

The rendered output looks something like this:

Plot of Scanners and Beacons