2021-12-19 - Beacon Scanner
(original .ipynb)
Day 19 puzzle input is a collection of scanners and the relative 3D positions of scanners they can see (mine is here). Part 1 involves translating and rotating these to find how the scanners all fit together and finding the number of beacons overall. Part 2 involves finding the maximum manhattan distance between any two scanners.
A warning to anyone who wants to look at or enjoy the code contained within:
This place is not a place of honor... no highly esteemed deed is commemorated here... nothing valued is here. What is here was dangerous and repulsive to us. This message is a warning about danger.
tiny_test_str = """--- scanner 0 ---
0,2,0
4,1,0
3,3,0
--- scanner 1 ---
-1,-1,0
-5,0,0
-2,1,0"""
test_input_str = """--- 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"""
puzzle_input_str = open("puzzle_input/day19.txt").read()
def scan_beacon(line):
return tuple(int(s) for s in line.split(","))
def parse_scanner(scanner_str):
lines = scanner_str.split("\n")
identifier = lines[0].removeprefix("--- scanner ").removesuffix(" ---")
beacons = [scan_beacon(line) for line in lines[1:]]
return int(identifier), beacons
def parse_input(input_str):
scanners = list(parse_scanner(scanner) for scanner in input_str.split("\n\n"))
return {i:beacons for i,beacons in scanners}
def rot_x(x, y, z):
return (x, -z, y)
def rot_y(x, y, z):
return (z, y, -x)
def rot_z(x, y, z):
return (y, -x, z)
def flip(x, y, z):
return (-x, -y, -z)
def rotations(point, r):
for _ in range(4):
yield point
point = r(*point)
from itertools import permutations, product
from collections import defaultdict
def orientations2(point):
for f in [point, flip(*point)]:
for rx in rotations(f, rot_x):
for ry in rotations(rx, rot_y):
for p in rotations(ry, rot_z):
yield p
def orientations(point):
for perm in permutations(range(3)):
for muls in product([-1, 1], [-1, 1], [-1, 1]):
yield (
point[perm[0]] * muls[0],
point[perm[1]] * muls[1],
point[perm[2]] * muls[2]
)
def orient_funcs():
for perm in permutations(range(3)):
for muls in product([-1, 1], [-1, 1], [-1, 1]):
yield lambda point:(
point[perm[0]] * muls[0],
point[perm[1]] * muls[1],
point[perm[2]] * muls[2]
)
def vec_add(ax, ay, az, bx, by, bz):
return (ax+bx, ay+by, az+bz)
def vec_sub(ax, ay, az, bx, by, bz):
return (ax-bx, ay-by, az-bz)
def test_orientation(known_beacons, beacons, orient, required_beacons_aligned):
differences = defaultdict(lambda:0)
assert len(known_beacons) == len(beacons)
for (known_beacon, beacon) in zip(known_beacons, beacons):
diff = vec_sub(*known_beacon, *orient(beacon))
differences[diff] += 1
for diff, count in differences.items():
if count >= required_beacons_aligned:
return diff
return None
def try_orient_scanner_old(all_beacons, scanner_positions, known_scanner, scanner, required_beacons_aligned):
known_scanner_pos = scanner_positions[known_scanner]
known_beacons = all_beacons[known_scanner]
for beacons in permutations(all_beacons[scanner]):
for orient in orient_funcs():
scanner_position = test_orientation(known_beacons, beacons, orient, required_beacons_aligned)
if scanner_position is not None:
scanner_positions[scanner] = scanner_position
all_beacons[scanner] = [vec_add(*scanner_position, *orient(beacon)) for beacon in beacons]
return True
return False
# areSetsAligned (set1: point[], set2: point[] )
# for i=0 to set1.length-1
# for j=0 to set2.length-1
# let offset = set2[j] - set1[i] // these 2 points will be aligned
# let matches = 0;
# // or we can have 2 loops
# allPoints1 = Set of set1 //hashtable or whatever
# // for each point from set2, move it and check if it exists in set1
# for k=0 to set2.length-1
# let moved = set2[k] - offset
# if allPoints.has moved then
# matches += 1
# if matches>=12 then yahoo & break // sets1 and sets2 match, use offset
def are_sets_aligned(set1, set2, required_beacons_aligned):
for i in set1:
for j in set2:
offset = vec_sub(*j, *i)
matches = 0
for k in set2:
moved = vec_sub(*k, *offset)
if moved in set1:
matches += 1
if matches >= required_beacons_aligned:
return offset
return None
def try_orient_scanner(all_beacons, scanner_positions, known_scanner, scanner, required_beacons_aligned):
known_scanner_pos = scanner_positions[known_scanner]
known_beacons = all_beacons[known_scanner]
for orient in orient_funcs():
unknown = [tuple(orient(p)) for p in all_beacons[scanner]]
if offset := are_sets_aligned(known_beacons, unknown, required_beacons_aligned):
all_beacons[scanner] = [vec_sub(*beacon, *offset) for beacon in unknown]
scanner_positions[scanner] = offset
# for beacons in permutations(all_beacons[scanner]):
# scanner_position = test_orientation(known_beacons, beacons, orient, required_beacons_aligned)
# if scanner_position is not None:
# scanner_positions[scanner] = scanner_position
# all_beacons[scanner] = [vec_add(*scanner_position, *orient(beacon)) for beacon in beacons]
return True
return False
def part_one(input_str, required_beacons_aligned=12):
all_beacons = parse_input(input_str)
scanner_positions = {0:(0,0,0)}
done_scanners = [0]
todo_scanners = [i for i in all_beacons if i != 0]
while len(todo_scanners) > 0:
ts = todo_scanners.pop(0)
for ds in done_scanners:
success = try_orient_scanner(all_beacons, scanner_positions, ds, ts, required_beacons_aligned)
if success:
done_scanners.append(ts)
break
if ts not in done_scanners:
todo_scanners.append(ts)
# naive dumb way to do this
unique_beacons = set()
for i, beacons in all_beacons.items():
for beacon in beacons:
unique_beacons.add(serialize(*beacon))
from pprint import pprint
pprint(scanner_positions)
return len(unique_beacons)
def serialize(x,y,z):
return f"{x},{y},{z}"
assert 3 == part_one(tiny_test_str, 3)
assert 79 == part_one(test_input_str)
print("part one:", part_one(puzzle_input_str))
ok part one: 362
from itertools import combinations
# i'm not rewriting this today - after the above took forever in my jupyter
# notebook I realised I didn't save the scanner positions, so ran it (slightly)
# quicker on my local machine and dumped the positions using `pprint()`
# whether I come back to this to fix remains to be seen ...
positions = {0: (0, 0, 0),
1: (2464, 3573, 1227),
2: (3722, 6019, 87),
3: (2540, 2433, 1155),
4: (1219, 3654, -1060),
5: (-22, 3572, 1159),
6: (1224, 4801, 1291),
7: (2544, 4815, 1258),
8: (94, 2376, 1345),
9: (4867, 3702, 2531),
10: (1333, 3618, 24),
11: (2434, 7343, -40),
12: (106, 3706, 2449),
13: (3620, 6069, 1317),
14: (2506, 3612, 2528),
15: (1221, 3606, 1168),
16: (2543, 4769, 88),
17: (3607, 3589, 2467),
18: (1233, 3560, 3625),
19: (3728, 7224, 1252),
20: (2476, 3556, 4761),
21: (2437, 7347, 1231),
22: (63, 1315, 111),
23: (2521, 3593, 3700),
24: (143, 2477, 86),
25: (2350, 5964, 1282),
26: (26, 1217, -1093),
27: (2418, 3746, -37)}
def part_two():
return max(manhattan_distance(*pair) for pair in combinations(positions.values(), 2))
print("part two:", part_two())
part two: 12204