9
votes

# Day 19: Beacon Scanner

## Today's problem description: https://adventofcode.com/2021/day/19

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace `python`

with any of the "short names" listed in this page of supported languages):

```
<details>
<summary>Part 1</summary>
```python
Your code here.
```
</details>
```

This might be where I bow out for this year. I don't know if I'm just burned our or if it's this problem in particular, but every time I read the problem description I just wanted to do basically anything else. I probably could solve it with a few hours work, but I don't think I would enjoy it.

It's been fun so far (for the most part) and I wish the rest of you luck going forward!

I couldn’t complete yesterday’s in time. I gave up on my Rust attempt and started again in Python (after first starting again in JavaScript 😅) but I know it’ll still take me a few days. Todays seems more straightforward but agree with the sentiment that it doesn’t seem like it’ll be enjoyable. Day 20 last year was a similar idea but felt more fun.

I’m hoping that the next few days will be a little less painful as non-weekend problems—if not, it may take me the next few weeks to finish them all.

## Potential spoilers about the puzzle but a question I have

Computerphile did a video on iterative closest point a few days ago and when reading the puzzle I remembered it and wondered whether that kind of algorithm is what you should be using to solve this?

Well, I'm out.

This one was too difficult to figure out without looking for hints online. Figuring out which beacons are shared between any two scanners is trivial by comparing the relative distance to the others, but that didn't give me any leverage for determining the scanner offsets.

I drew a bunch of diagrams for triangulation, but that somehow never worked in 15+ hours of attempts, there always seemed to be a missing ingredient in the formulas I drafted.

AoC was good for one thing: I learned a lot about Rust, especially parsing with Nom. But I don't feel like wasting any more time here. You could say I'm salty, but the puzzles so far were all either trivial or trivial

andtedious. The only puzzle where the solution is not immediately obvious is Day 19, which then turned out to be straight up impossible for me.So yeah, fuck this.

Glad to know I'm not the only one who wasted an absurd amount of time on this one and ultimately came up empty-handed.

I feel stupid posting this, because the ragequit wasn't pretty.

I've cooled off a little, but this puzzle kept gnawing on me to the point that I couldn't sleep well, so I had to solve at least Part I in order to save my sanity.

I won't do Part II or the remaining puzzles -- they just don't provide enough entertainment for the time they take up.

I've always heard about how awesome they are, and admired people solving them in Haskell, but they're more tedious than interesting now that I did them myself, at least up until day 19. Maybe the cool stuff starts on day 20, who knows, but I'm now done with them for the year at least.

As for the actual solution, ironically my problem on this puzzle was that I tried to do it in Ruby because I thought Rust wasn't great for exploratory programming.

It turns out that the

`Set`

data structure is just completely and silently broken for custom classes if you don't implement both`#eql?`

and`#hash`

. I had implemented`#hash`

and`#==`

, but not`#eql?`

for my custom Coordinate class, so set intersection was broken, and that led me to believe my initial algorithm idea would not work.I redid everything in Rust, and I hope with this post, I can finally put all my thoughts of the contest to rest.

## Data structures

First, I needed a way to represent 3D coordinates.

We need a way to calculate the distance between two beacons, as well as a way to rotate a coordinate so it points 'up' (though we generally don't know where 'up' is). The puzzle description helpfully lists that there are 24 different directions -- I had to Google this, but it is obvious in retrospect -- 3 axis, times 2 for positive and negative orientation, times 4 for the possible rotations around one of the axes.

Then we have the Scanners themselves. They have an offset (their center) from Scanner 0 as well as a rotation. They keep the beacon coordinates in the local coordinate system, although the

`beacons()`

method transforms those into the global coordinate system.My initial insight (what I called trivial in the ragequit post), if you want to call it that, is that you can fingerprint the beacons by their distance to the other beacons of the same scanner. The same beacon seen by two different scanners will share 11 distance values exactly. This gives us an easy way to match beacons.

## Parsing

## Helper functions

`common_count`

counts the common elements of two sorted vectors. We never need to count above 11, so it aborts there.`match_scanners`

checks the fingerprints to see if there is a match between Scanner a and b, and returns the aligned scanner if successful.`merge`

assumes scanner`a`

is correctly oriented and brute-forces the 24 possible rotations for scanner`b`

. This should generally work for the first attempt, but it loops through all matches, just in case we have mistakenly identified a common beacon. The function will return a new`Scanner`

struct that has the correct orientation and offset. The latter is calculated by moving from Scanner A in the positive direction towards a shared beacon (+`ba`

), and then in the negative direction towards the other scanner (`ba - bb_rot`

). Try drawing a diagram of this -- in the one-dimensional case it becomes really obvious.This is where the Ruby Set data structure failed me.

## Solving

This just keeps a Queue of unsolved and a vec of solved Scanners, to iterate until done.

And then we just count how many unique beacons there are. Takes about 60ms.

## Tip

The puzzle description says the scanners keep their position, but it is helpful to move them around (conceptually, at least).

RustI finally finished both parts, though I have a bizarre issue. My solution is non-deterministic. Sometimes I run it and get the correct answer, other times I run it I get a close but wrong answer. Very strange and something I've never encountered before in AoC.

Edit: Figured out the determinism issue. I had to sort the HashMap keys on most-frequent offset matches >= 12, not just take the first value >= 12, since apparently there can be overlap.

## Rust

## Point3D

PHEW! With less than an hour before todays puzzle!

I liked day 19 a lot more than day 18; with 18 I

feltlike I understood what was supposed to be happening, but the difficulty came from a slightly awkward implementation and difficulty understanding what the puzzleactuallywanted.Today (/yesterday), I really understood

whatI was supposed to be doing, and could properly enjoy working out the mechanism to get there. Took me ages, but I did manage it!## Part 1 Ruby

This code is all still a mess, with leavings from various dead-ends still hanging around. I may come back around later and try to clean it up and describe it better, but for now I'll just dump what I've got and try to give a general overview.

Edit: Oh, I should add; the one big thing that got me going again was basically to give up on trying to figure 3D/matrix math and rotations properly, and just look at the ways that a given star at [x,y,z] might be transformed. The axes might get shuffled around (ie [y,z,x]), and the signs might get flipped eg ([-x,-y,-z]). Instead of working out proper rotations and trying those, I just generate every possible combination of axis-shuffling (which I call

`rotations`

in my code) and sign-flipping (`inversion`

). This means more things to check, but I know the right combination has to be in there somewhere, and since I'm only looking at three stars at a time, it doesn't add too many options.This puzzle is kind of like a sci-fi astronavigation problem that gets referenced fairly often; given some set of points (stars) in 3D space, how can I figure out my position relative to a known origin? I may drift back and forth between referring to the beacons as "beacons" or "stars" interchangeably because that's how I was thinking of it the whole time, so that's what's going on there.

To do this, we need to look at the relationships between the stars (beacons here) and find similarities between the unknown (results from any scanner other than 0) and the known (results from scanner 0, since we're treating that as the origin). Initially I was trying to get by with just looking at the distance to each pair of stars in a given scan, and then finding pairs with the same distances in other scans.

This sort of worked, but was giving me trouble with the rotations and I doubt it would've worked in the full input; so I ended up going with triangles instead.

The slowest part of my solution is to go through each scan, find every combination of three stars (A,B,C), compute the distance in three dimensional space between each of them (AB,BC,CA), and sort those distances into an array. Once I have this normalized triangle, I store that as the key to a hash, with the three stars as the value, something like

`{ [1,2,3] => [[x1,y1,z1], [x2,y2,z2], [x3,y3,z3]] }`

I do this for every combination of three stars in every scan, which ends up being about 2,300 triangles per scan.

Once I have this table of triangles (and the stars involved in each) for every scan, I can start looking for intersections. Any intersection will give me a set of at least three stars that I can work out a transformation for.

If I were a better mathematician, I'd probably know the matrix math to work this out more directly, but since I'm only looking at three stars at a time, I can just try everything and it works out well enough.

This is the

`relative_scanner_position`

function above, it takes a pair of triangle maps (A,B), finds the triangles that are present in both, and then tries every possible transformation on each star in each triangle from B. Each time a transformed star location lines up with one of the stars from A, we add one point to that transform.At the end, we find the highest scoring transform and return that as the relationship between scanner A and scanner B.

So now we can take any given pair of scans, find out if they overlap at all, and if so what the relationship is between the two.

We do this for all overlapping scans, and as we go we're building up two important pieces of information: 1) the graph of connected/overlapping scans, and 2) a table of transforms that let us move stars from one frame of reference to another.

Initially I tried to directly flatten all the transforms to get everything down into the coordinate space of scanner 0, but that was giving me trouble so I ended up using BFS to pathfind my way to a list of transformations to apply to each scan. Fortunately the graph is small enough that this doesn't add a meaningful amount of time.

Then it's just a matter of flattening all the stars into one coordinate space, throwing them in a set, and counting.

## Part 2 Ruby

I actually had, at one point, tracked down all the scanner locations (relative to scanner 0) during the part 1 solve, but ended up throwing them out at some point by the time I actually finished part 1. So I had to re-solve for that, but that ends up being as easy as mapping

`[0,0,0]`

down through the transform path with all the other stars.I could improve the runtime by re-using all the work from part 1, but instead I just copy-pasted everything again ¯\_(ツ)_/¯

I enjoyed this enough that I'd like to come back and clean up the code and description a bit, but I'm out of time before day 20 and I've got holiday travel coming up, so this is what we get for now!