Discussion thread for day 19 of the Advent of Code - https://adventofcode.com/2021/day/19
It was much more involved than I first anticipated, but I oversolved part 1 which made part 2 easy
re-structure the table to scanner, x, y, and z.
Add RecordID to used in iteration later.
i found that when come to sorting by x, y, or z. we can see the match by the movement.
so I use generate row create all possible line and join with the scanners. (use generate row instead of append because can use +/- for grouping later)
join with the scanners. and use summarise to get the total of match. (11 instead of 12, because the first line is no movement to use in join)
join back to get that scanners detail. (i.e. scanner 15 with 8 and/or 18 with 😎
from here, we can guess the possible position of the scanner. (X/ Y /Z) +/- (x/ y/ z) (18 formulas)
if the count is more than 11. it is the correct answer. i reduce to 9 to solved, but i don't know why if is matches by sorting.
re-structure to this table, output it, to use in part2 to later
re-join it to the scanner 8, adjust the x, y, z to the scanner 0 position and union it with scanner 0 and use it for iteration.
This was quite involved but very satisfying:
Main Flow:
- Clean up the input then put it through the main worker section
The solver flow:
The story of this flow is:
- First create vertices / lines between all the points in each beacon section.
- Then look for overlaps based on these distance vectors. If you have a certain number of matches then you know that these beacons overlap
- If they overlap, then you need to find the rotation and offset to make these match
- Now you can take these two groups and bring them together as one beacon group and do this all again - until you only have one aligned group
Create Vertices:
This is a relatively simple process to create a vertex / edge between each pair of points
The overlap checker is a little more complex and has to check for a threshold of matching vertices
The Rotate and overlap
This looks at the overlapping group and determines how far to move it to align; and how to rotate it.
The trick is rotate first until you get an equal distance on all vertices. Then you know the offset.