commit40ae9ac2d3f794b51685a439516e4b220b8b703eparent4a8670dc62efc98f30b853c6c4c3753bd83e3e1bAuthor:Eamon Caddigan <eamon.caddigan@gmail.com>Date:Sun, 19 Dec 2021 14:38:13 -0500 Solution to day 19, part 1Diffstat:

A | day19_part1.py | | | 332 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |

1 file changed, 332 insertions(+), 0 deletions(-)diff --git a/day19_part1.py b/day19_part1.py@@ -0,0 +1,332 @@ +#!/usr/bin/env python +"""Advent of Code 2021, day 19 (part 1): Beacon Scanner +Given positions (but not consistent frame of reference), find the overlap +between a set of beacons detected by several scanners""" + +# Looking at the leaderboard, this one has been hard for folks. My first +# impression is that its pretty doable if I can get away with brute forcing a +# few parts of it, but if I need to be sophisticated (i.e., if a bunch of +# polynomial time approaches dont scale), then this could be a huge slog. +# +# Numpy and SciPy are helping out here, but neither are doing any algorithmic +# heavy lifting (as was the case when using optimization or graph search from +# SciPy in previous puzzles). +# +# Note: I'm using _augmented matrices_ to represent the beacon locations and +# transformations. 3D data is represented by 4D vectors padded with a 1, +# allowing translations to be implemented with matrix multiplication. + +from typing import List, Union, Tuple +from itertools import product +import numpy as np +from scipy.spatial.transform import Rotation as R +from scipy.spatial.distance import cdist +from utils import get_puzzle_input + +EXAMPLE_INPUT = \ +"""--- scanner 0 --- +404,-588,-901 +528,-643,409 +-838,591,734 +390,-675,-793 +-537,-823,-458 +-485,-357,347 +-345,-311,381 +-661,-816,-575 +-876,649,763 +-618,-824,-621 +553,345,-567 +474,580,667 +-447,-329,318 +-584,868,-557 +544,-627,-890 +564,392,-477 +455,729,728 +-892,524,684 +-689,845,-530 +423,-701,434 +7,-33,-71 +630,319,-379 +443,580,662 +-789,900,-551 +459,-707,401 + +--- scanner 1 --- +686,422,578 +605,423,415 +515,917,-361 +-336,658,858 +95,138,22 +-476,619,847 +-340,-569,-846 +567,-361,727 +-460,603,-452 +669,-402,600 +729,430,532 +-500,-761,534 +-322,571,750 +-466,-666,-811 +-429,-592,574 +-355,545,-477 +703,-491,-529 +-328,-685,520 +413,935,-424 +-391,539,-444 +586,-435,557 +-364,-763,-893 +807,-499,-711 +755,-354,-619 +553,889,-390 + +--- scanner 2 --- +649,640,665 +682,-795,504 +-784,533,-524 +-644,584,-595 +-588,-843,648 +-30,6,44 +-674,560,763 +500,723,-460 +609,671,-379 +-555,-800,653 +-675,-892,-343 +697,-426,-610 +578,704,681 +493,664,-388 +-671,-858,530 +-667,343,800 +571,-461,-707 +-138,-166,112 +-889,563,-600 +646,-828,498 +640,759,510 +-630,509,768 +-681,-892,-333 +673,-379,-804 +-742,-814,-386 +577,-820,562 + +--- scanner 3 --- +-589,542,597 +605,-692,669 +-500,565,-823 +-660,373,557 +-458,-679,-417 +-488,449,543 +-626,468,-788 +338,-750,-386 +528,-832,-391 +562,-778,733 +-938,-730,414 +543,643,-506 +-524,371,-870 +407,773,750 +-104,29,83 +378,-903,-323 +-778,-728,485 +426,699,580 +-438,-605,-362 +-469,-447,-387 +509,732,623 +647,635,-688 +-868,-804,481 +614,-800,639 +595,780,-596 + +--- scanner 4 --- +727,592,562 +-293,-554,779 +441,611,-461 +-714,465,-776 +-743,427,-804 +-660,-479,-426 +832,-632,460 +927,-485,-438 +408,393,-506 +466,436,-512 +110,16,151 +-258,-428,682 +-393,719,612 +-211,-452,876 +808,-476,-593 +-575,615,604 +-485,667,467 +-680,325,-822 +-627,-443,-432 +872,-547,-609 +833,512,582 +807,604,487 +839,-516,451 +891,-625,532 +-652,-548,-490 +30,-46,-14 +""" + +def parse_input(input_string: str) -> List[np.ndarray]: + """Given the puzzle input, return a list comprising all the + beacons detected by each scanner""" + # I do not love how hacky this is + scanner_beacons = [] + beacon_start = 0 + # Depends on the trailing newline in the puzzle input. Hacky! + input_lines = input_string.split('\n') + for idx, line in enumerate(input_lines): + if line.startswith('---'): + beacon_start = idx + 1 + elif line == '': + # End of a probe's beacons + scanner_beacons.append( + np.array([l.split(',') + ['1'] for l in input_lines[beacon_start:idx]]) + .astype(float) + ) + return scanner_beacons + +def augment_matrix(rotation_matrix: np.ndarray) -> np.ndarray: + """Given a 3x3 transformation matrix, return a 4x4 augmented matrix + representing the same transformation""" + return np.vstack(( + np.hstack((rotation_matrix, np.zeros((3, 1)))), + np.array([0, 0, 0, 1]) + )) + +def create_rotations() -> List[np.ndarray]: + """Create the 24 distinct rotation matrices for a probe that can be + oriented to point along any direction of the x, y, and z axis, with its top + aligned along one of the other two axes""" + # This function is inefficient; it considers all possible 90 degree + # rotations along each of the three axes (i.e., 4^3 = 64 combinations), and + # then only returns the 24 unique ones. One could probably reason out how + # to more directly generate the 24 that matter, but this works! + # This first step creates a Rotation instance that stacks all 64 rotations + rotations = R.from_euler( + 'zyx', + np.array(list(product(*(((0, 90, 180, 270),) * 3)))), + degrees=True + ) + # This next step creates a list of non-duplicate rotation matricies + final_rotations = [augment_matrix( + rotations[0].as_matrix().round() + )] + for rot_obj in rotations[1:]: + # In our case, all of the elements of the rotation matrix should be -1, + # 0, or 1, so we'll round everything to the nearest value to make + # equality checking easier + rot_mat = augment_matrix(rot_obj.as_matrix().round()) + for prev_rot_mat in final_rotations: + if (rot_mat == prev_rot_mat).all(): + break + else: + # We get here if the for loop completed without breaking, which + # means we have a unique rotation matrix + final_rotations.append(rot_mat) + return final_rotations + +def translation_matrix(offset: np.ndarray) -> np.ndarray: + """Given a length-three array representing the x, y, and z offset, return a + 4x4 translation matrix (if the offset array is longer than three elements, + only the first three are used, so it's safe to lazily pass length-four + arrays too)""" + return np.vstack(( + np.identity(4)[0:3, :], + np.append(offset[0:3], 1) + )) + +def count_overlapping_beacons(scanner_1: np.ndarray, + scanner_2: np.ndarray) -> int: + """Given a pair of (appropriately rotated and translated) beacon positions, + count how many from each scanner are at approximately the same location""" + return (cdist(scanner_1, scanner_2) < 1e-8).sum() + +def find_best_overlap(scanner_1: np.ndarray, + scanner_2: np.ndarray) -> Union[np.ndarray, None]: + """Find the combined rotation/translation matrix for scanner 2 that results + in (magic number) 12 overlapping beacons, or return None if no such + transformation exists""" + # The algorithm: for each possible rotation, calculate the distance matrix + # (using Euclidean distance) between the two sets of beacons. If (magic + # number) 12 or more beacon pairs have the same distance, translate + # scanner_2's beacons so that the first such pair has a distance of zero. + # If the remainder of the same-distance pairs don't also go to zero, + # continue to the next pair, until there are fewer than twelve remaining + # pairs to check. + for rot_mat in create_rotations(): + scanner_2_rot = scanner_2.dot(rot_mat) + dist_mat = cdist(scanner_1, scanner_2_rot) + # We'll round the distance matrix to get a sense of the mode + beacon_dist_count = np.bincount( + np.reshape(dist_mat.round(), dist_mat.size) + .astype(int) + ) + if beacon_dist_count.max() >= 12: + # There are at least 12 beacon pairs with similar distances. + # Iterate through the pairs to see if translating one to the other + # provides a match. + potential_beacon_matches = np.nonzero( + dist_mat.round() == np.argmax(beacon_dist_count) + ) + # Technically we can stop iterating when there are fewer than 12 + # possible matches but I don't feel like programming that in unless + # I have to. + for scanner_1_beacon_idx, scanner_2_beacon_idx in \ + zip(*potential_beacon_matches): + scanner_1_beacon = scanner_1[scanner_1_beacon_idx, :] + scanner_2_beacon = scanner_2_rot[scanner_2_beacon_idx, :] + trans_mat = translation_matrix( + scanner_1_beacon - scanner_2_beacon + ) + num_overlapping = count_overlapping_beacons( + scanner_1, + scanner_2_rot.dot(trans_mat) + ) + if num_overlapping >= 12: + return rot_mat.dot(trans_mat) + return None + +def create_beacon_network(scanner_beacons: List[np.ndarray]) -> \ + Tuple[np.ndarray, List[np.ndarray]]: + """Given a list of scanner beacons, find all of the unique beacons across + all scanners by rotating and translating the scanner coordinates (relative + to the first beacon in the list). Returns the final beacon locations and a + list of translation matrices.""" + scanner_beacon_list: Union[None, np.ndarray] = scanner_beacons.copy() + translation_list: Union[None, np.ndarray] = [None] * len(scanner_beacon_list) + + final_beacons = scanner_beacon_list[0] + scanner_beacon_list[0] = None + translation_list[0] = np.identity(4) + + # The way the problem is written suggests that not every pair of scanners + # has an overlapping set of beacons. This algorithm loops through all + # scanners sequentially. When it finds overlap with the network, its + # beacons are added to the network and it's removed from further + # consideration. Eventually, all of the beacons should get added! + while sum([x is not None for x in scanner_beacon_list]) > 0: + for scanner_id, beacons in enumerate(scanner_beacon_list): + if beacons is not None: + trans_mat = find_best_overlap(final_beacons, beacons) + if trans_mat is not None: + final_beacons = np.unique( + np.vstack(( + final_beacons, + beacons.dot(trans_mat) + )), + axis=0 + ) + + scanner_beacon_list[scanner_id] = None + translation_list[scanner_id] = trans_mat + + return final_beacons, translation_list + +def solve_puzzle(input_string: str) -> int: + """Return the numeric solution to the puzzle""" + return create_beacon_network(parse_input(input_string))[0].shape[0] + +def main() -> None: + """Run when the file is called as a script""" + assert solve_puzzle(EXAMPLE_INPUT) == 79 + print("Total number of beacons:", + solve_puzzle(get_puzzle_input(19))) + +if __name__ == "__main__": + main()