# Advent of Code 2021 - Day 19

This topic is about Day 19 of the Advent of Code 2021 .

We have a private leaderboard (shared with users of Erlang Forums):

The entry code is:
`370884-a6a71927`

This took me a few hours to get right, but I did like the challenge! Run time under 1 second on my machine.

3 Likes

Needs lot of refactoringâ€¦

EDIT1: Lol just read the OPâ€™s solution. Much better than mine.

EDIT2: After reading OPâ€™s code I realized the fact that the diff can be directly used to calculate the relative locations of the scanners. Refactored my code and now itâ€™s much better. Still a lot LOC more than OPâ€™s. Originally I calculated s1 â†’ beacon â†’ s2. A lot of extra unnecessary work. Now just ignore the beacons and use the diff.

1 Like

Nice!

What I am doing is, for the next scanner `base` that was not matched against yet, for each scanner `scan` that was not matched yet, for all points `b` of `base` and for all points `p` of `scan`, for each rotation of `p`, assume that `p` is `b` and compute the offset, then transform all `scan` points with that rotation and offset, and if there are 12 equal points then `scan` is matched (and is moved in the bases queue for later use).

And obviously it is slow, my Rust version takes more than two minutes.

yeah, maybe I should have added some comments to the code. Basically what happens is this:

First, the function build_rotations() generates all 24 valid rotation matrices; Then in run() the input data is scanned and the beacons found in the first scan are put in the `beacons` Map, because scanner #0 is considered to be in reference orientation and location.
Now `work()` does this:

• it iterates over all scans in the list, and for each scan applies all the rotation matrices to all its points. For each point, it calculates the (x,y,z) distance to all known points in the `beacons` map, and goes check if more then 12 points have exactly the same distance. If this is the case, it considers the found rotation valid for this scan, adds this (x,y,z) distance to all rotated points and adds them to the `beacons` map. Finally, it removes this `scan` from the list of scans, and recurses back to itself until the `scans` list is empty.

Note that I did cheat by doing all rotations async on separate tasks

3 Likes

Thank you

yeah, so this was me trying to be clever and then I ended up with being unable to make it work and wasted way to many hours on trying to â€śfixâ€ť my initial approach.

Of course as I went to bed, I realised that I only ever needed to convert between two sets of coordinates and that this is easy, so implemented a simple body-recursive thing that does just that

That said I did like doing the â€śrotation by templateâ€ť, where when I find two sensors that are neighbours, I have the list of the â€śmatching nodesâ€ť (in normalised coordinates where [0,0,0] is the same in both nodes), and then I just look at two of these â€śmatching coordinatesâ€ť and make a â€śrotation templateâ€ť out of it which, I then can use to â€śrotateâ€ť all of the other coordinates.

1 Like

Is this guaranteed to be true? Couldnâ€™t you have at least 8 identical distances that could reflect unique points? In order to be certain you donâ€™t have a false positive donâ€™t you have to have at least 20 identical distances?
I gave up on this one because of this idea. My thought was to really get it right you have to arbitrarily choose one sensor as the MAIN sensor or base case to compare to. You then have to generate the slopes and distances for all points relative to all other points. So if you have 3 points [A, B, C] you map it to

``````[
[{slope(A,B), distance(A,B)}, {slope(A,C), distance(A,C)}],
[{slope(B,C), distance(B,C)}, {slope(B,A), distance(B,A)}],
[{slope(C,A), distance(C,A)}, {slope(C,B), distance(C,B)}]
]
``````

Then for a scanner with points D,E,F you have do the same, then do every rotation on every one and find the one that matches the minimum number in the base case. Perform the necessary rotational transformations you just found to D,E,F. Add D,E,F to the base case and now recalculate all your arbitrary references again for the base case.
You can see why I gave up on that, but I donâ€™t see logically how any other way is sound.