Advent of Code 2021 Day 19 (BaseA Style)

[jdunkerley79]

Discussion thread for day 19 of the Advent of Code - https://adventofcode.com/2021/day/19

[patrick_digan]

It was much more involved than I first anticipated, but I oversolved part 1 which made part 2 easy

Spoiler

I looked at the relationship, for each scanner, between all of the points (ie difference in x,y,z.) Then I compared all the scanner/beacon combinations to line up each scanner with any overlapping scanners. Then I figured out how to translate the xyz values from each scanner back to 0. For example, scanner 38 overlapped with scanner 0 so only 1 translation is necessary. Scanner 39 had to take this path: 39 >12 >14>34>26>5>35>15>38>0. Once I got the path, I then figured out the translation between each scanner. The math wasn't hard, but the whole rotating scanners made it harder to think through. Once I had all the beacons in relation to scanner 0, then I just summarized. For part 2, I just added a beacon 0 for each scanner at 0,0,0 and let it run through the translation macro to get the coordinates relative to scanner 0.

Workflow:

[Pang_Hee_Choy]

Spoiler

Workflow

re-structure the table to scanner, x, y, and z. 
Add RecordID to used in iteration later.

Part1:
macro:

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)


and to take care of other dimension and positive or negative, 
I create 12 (3x2x2) lists with all 3 different criteria. (eg: sort by x, descending and positive)
1. sort by x, y and z
2. descending and ascending
3. positive and negative. 

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.

to stop the iteration, i drag a field to before in iteration output and compare with the total scanner in input2 (scanner 1 - 25) and in input1 (scanner 0 + iteration.)

after the macro, just use unique tool to get the answer.

Part2:
as output in part 1,

just simply append all possible combination, formula and sort it.

[SeanAdams]

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.