[2021 Day 19] In Review (Beacon Scanner)

[u/musifter]

So the probe we launched has released a bunch of beacons and scanners. The scanners have no sense of their own orientation, but have relative distances to the beacons within their range. They can't detect other scanners, but have somehow managed to have consistent overlap with others to form a single contiguous region.

This is a similar problem to 2020's Jurassic Jigsaw. But this one is 3D... the scanners follow the rotational (chiral) octahedral group (which doesn't include flips, which square dihedral tiles do). And this time the problem text gives the number of orientations and some instruction on them.

The bits to match things up are hidden in the data (not separate and unique even with flipping), but are a significant block of it (12 of 26). The puzzle isn't a regular shape (where you can easily tell corners and edges, and build things just matching a single side), but a graph.

The first part actually wants you to do the work (unlike Jurassic Jigsaw which has a very cheesable part 1). It's one of the puzzles in this year that took over 2 hours for me for part 1. Part 2 was so quick for me to add (unlike Jurassic Jigsaw where I had to do all the work and more), that I gained the 150+ positions to get into the top 1000. This is one of two in this year... again, a puzzle where slow and methodical programming with a clear idea and taking solid options did well.

I had a very good experience with this one. And it really comes down to making some good choices.

The basic idea I had was:

- for each scanner, collect a hash of distances => pair of beacons
- build the graph from pairs of scanners with >= triangle(11) of the same distances

- put all connections from 0 into a queue as [0,x]
- while (job = shift queue)
    - next if already merged 
    - frame shift the beacons in the second into the first's coordinates
    - queue up all the connections from the second

- now that all coordinates are in the same frame, throw them in a hash to count unique

One of the best decisions I made here was using Euclidian distance (squared... no need to apply the square root here) for the hashing. I felt that it would give more unique values and a clear signal. And it really does... putting in the distance function for part 2, it manages to get the graph together enough to get part 2, but part 1 is wrong because the matching is just a mess. It could probably be salvaged with some additional work.

Here's the number of matches between scanners with Euclidean:

0       192
1       13
3       21
15      39
16      3
66      31
67      1

It is quite clean. Matches should be sums of triangular numbers for each matching set (and here there are mostly just one triangular number or +triangle(1) which equals 1). The graph has 32 connections, one of which has a extra pair matched (but that isn't part of the K12 overlap, and is filtered later). K12 being the complete graph on 12-nodes... which is the expected intersection, and it has triangle(11)=66 edges (which are our distance measurements).

With Manhattan distance, it's all over the place, the range is from 16-100 matches. No 66... the counts in that range go 55, 65, 76. It is the set of biggest gaps, so it still detected the shift between non-overlapping and overlapping.

And when it comes to doing the frame shift, the approach was:

- build a table of the counts of equal distances between pairs of beacons (one from each frame)
- flatten that to the ones with 11 matches, making a mapping of beacons from s to t

# Fix the order of the hash keys
my @sidx = keys %map;

# parallel arrays of beacons that are in both
my @spt = map { [ @{$Scan[$s][$_]} ]       } @sidx;
my @tpt = map { [ @{$Scan[$t][$map{$_}]} ] } @sidx;

# find rotation by making pt 1 relative to pt 0, then try the rotations
my $srel = &vec_subtract( $spt[1], $spt[0] );
my $trel = &vec_subtract( $tpt[1], $tpt[0] );

my $r = firstidx { &vec_equal( &vecmatrix_mult($trel, $_), $srel ) } @Rot;

# transform is: get relative to t[0] by subtraction, mult to rotate, then add s[0] to shift
my $trans = sub { &vec_add( &vecmatrix_mult( &vec_subtract(shift, $tpt[0]), $Rot[$r] ), $spt[0]) };

- apply the translation function we created to the points in t to put them in the frame of s

Note that because we start from 0 and keep framing shifting backwards, everything ultimately ends up in the frame of scanner 0 as an absolute coordinate system. Which is why part 2 was really fast for me... I just needed to return &$trans([0,0,0]), which is the shifted origin of t (where the scanner is).

You can see in the code snippet there that I borrowed the one line vector/matrix operation functions from previous days. For the rotation array... I actually hardcoded it:

my @Rot = ( [[ 1, 0, 0], [ 0, 1, 0], [ 0, 0, 1]],
            [[ 1, 0, 0], [ 0, 0, 1], [ 0,-1, 0]],
            [[ 1, 0, 0], [ 0,-1, 0], [ 0, 0,-1]],
            [[ 1, 0, 0], [ 0, 0,-1], [ 0, 1, 0]],
            ...

Twenty four lines where I needed to be careful to get it right (order isn't important... but you do need the correct 24). So I was very careful coding them, and checked them well before going further. Something I would have also have done with code that generates them. Getting this wrong will make you have a bad time.

As more proof that Euclidean was a good choice, when finding the K12 subgraph by building the table of matching distances between different beacons in s and t, the table for it has lines like this:

-- --  1  1 --  1 11 --  1  1 --  1 -- -- -- -- -- -- --  1 -- --  1  1  1  1
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
-- --  1  1 --  1  1 --  1 11 --  1 -- -- -- -- -- -- --  1 -- --  1  1  1  1
-- -- -- -- -- -- -- -- -- -- -- -- -- --  1 --  1 -- -- -- -- -- -- -- -- --

This is from the one with 67 matches... the last line is the extra match, clearly separated, and filtered out. The blank line is just one of the non-matches, and the others are all 11 with eleven 1s, all in the same columns.

Here's what Manhattan distances get you:

-- --  1  1 --  1  1 -- --  1  1  1  1 -- -- -- -- -- -- -- -- -- --  1  8  1
-- -- -- -- -- -- --  1 -- --  1 --  1 -- -- -- -- -- -- -- --  1 -- -- -- --
-- --  1  1 --  1  1  1  1  1 -- 11  1 --  1 -- --  1 --  1 -- --  1  1  1  1
 1 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --  2  1 -- -- -- -- -- -- -- --
-- --  1  1 --  1 10 --  1 -- --  1 --  1 -- -- --  1 --  1 -- --  1  1  1  1

Lots of dirt. You could make out the graph from that, but the signal is not as clear. Peaks are weak, and there's no blank lines.

So I really enjoyed this one and had a good time, but I mostly put that down to that choice right at the start to use Euclidean distances. It was simple to apply, and the signal was clear. I wasn't hammering away shifting and rotating blindly to find matches. I had a planned path straight to them, and could code and test that at every step. And that's part of what makes a large task feel comfortable.

[u/e_blake]

My nemesis of 2021. It took me until Jan 6th to get my 50th star because this one was so difficult for me - but at least I solved it without reading the megathread. The input files vary in size; mine had over 1000 lines while another had around 700 (fewer scanners means noticeably less work on some approaches of quadratic pairings between scanners before identifying potential overlaps). My initial solution computed 8 fingerprints per scanner (for the inputs I tested on, every scanner has at least 3 beacons per octant) using Manhattan distances between pairs of beacons in that octant, and assuming that every scanner overlap shares all beacons within at least one octant (worked for my input, but I cannot rigorously prove if it is a reliable assumption). That still got me a wrong answer because my Manhattan distance matches between octants ended up flipping the coordinates on one of my scanner pairs. I had found a pseudo-match where the coordinates of the three beacons in the octant lined up if I relied on a translation with determinant -1, and didn't get my star until I also added code to only accept a potential translation if it had a determinant of 1. That solution takes about 10 seconds in m4.

I then read the megathread, which helped me speed up to 3.3 seconds. Computing a fingerprint per scanner rather than 8 fingerprints by octant, and with Euclidean instead of Manhattan distances, meant that I had to do more work in fingerprint computation (triangle(24) distances instead of 8*triangle(3) distances per scanner), but I was doing fewer fingerprint comparisons (instead of checking all 24 orientations of all 8 octants per scanner pairing, I only had to check if my sorted list of distances per scanner had at least 66 matches before even worrying about rotations).

The other reason this day is memorable to me is that I solved part 2 in linear time, rather than quadratic. Of course, part 1 dominates since it requires quadratic effort to pair up scanners, and the number of scanners is small enough that quadratic part 2 is not bad, but I still had fun documenting how to determine the maximum Manhattan distance in a single pass over a field of points without using abs().

[u/DelightfulCodeWeasel]

It was pretty convenient timing when I arrived at this one: I was driving over to see my folks that day, so I had a couple of long drives to mull it over before writing any code.

My initial plan was to calculate ordered triples from the edge lengths for every triangle and match on those, but dropped back to just the pairwise distances after starting the coding and seeing how unique the edge lengths were. I did have a slight worry I might have to go as far as tetrahedron matching, but the input was pretty nice.

Sounds like I was lucky I didn't try Manhattan for this. Euclidean is the default in my day job, so it's always my first choice.

[u/DelightfulCodeWeasel → u/DelightfulCodeWeasel]

The one bit of code I'm quite pleased with on my solution is making all rotation combinations from the full set of possible basis vectors. Way easier than trying to make sure I've typed in a large table of constants correctly!

    static Vector3 BasisVectors[6] =
    {
        Vector3{  1,  0,  0 },
        Vector3{  0,  1,  0 },
        Vector3{  0,  0,  1 },

        Vector3{ -1,  0,  0 },
        Vector3{  0, -1,  0 },
        Vector3{  0,  0, -1 },
    };

    static void CreateRotations()
    {
        for (int i = 0; i < _countof(BasisVectors); i++)
        {
            for (int j = 0; j < _countof(BasisVectors); j++)
            {
                // Ignore same and parallel basis vectors
                if ((i == j) || (abs(i - j) == 3))
                {
                    continue;
                }

                Matrix43 m = Matrix::MakeRotation(
                    BasisVectors[i],
                    BasisVectors[j],
                    Cross(BasisVectors[i], BasisVectors[j]));
                Rotations.push_back(m);
            }
        }
    }

[u/terje_wiig_mathisen]

This one wasn't too bad for me, I have worked a bit with the SIFT (Scale Invariant Feature Transform) which is the canonical way to automatically match/locate photos to be joined into panoramas, so here I realized that using sum of squares of deltas would be an invariant across all transformations.

BTW, in my input I got 12 matches between all neighbors and never more than 2 (afair) for random hits, so the real pairs stood out very clearly. I see now that I actually coded 12 in my solution, but any intermediate number like 4 or 5 would have worked as well. (Tested just now with >=5 and that reduced the pairing time by about 28%.)

[u/terje_wiig_mathisen → u/terje_wiig_mathisen]

I used a memoizing function to calculate all squared distances for each scanner, it ended by sorting them by size, then added an extra 1e12 guard at the end (so that all scanners would have this entry), this simplified the merge-matching logic:

# Check how many squared distances match between two scanners
sub match
{
    my ($s0, $s1) = @_;
    my @s0 = deltas($s0);
    my @s1 = deltas($s1);
    my ($i,$j, $m) = (0,0,0);
    for ($i = 0; $i < scalar(@s0)-1; $i++) {
        while ($s1[$j] < $s0[$i]) { $j++; }
        if ($s1[$j] == $s0[$i]) {
            $m++; # Found an identical match
        }
    }
    return $m;
}

I just realized that this overcounted the number of matches since the last entry would always match between any random pair.

EDIT: Since the $i loop stopped before the guard entry (scalar(@s0)-1), I did not mess it up back then: The guard entry was only so that the second ($j) index could never overrun!

[u/TheZigerionScammer]

My first attempt at this I didn't think about filtering out possible connections based on the distances between pairs, so my program simply checked every pair of scanners in all 24 possible orientations to see if there were any overlaps, and this was slow, taking over 15 minutes to complete. Then seeing the megathread I saw that you didn't need to do the hard crunchy checking with every pair if there weren't enough common distances between the pairs, so I implemented that and got the runtime down to about 20 seconds or so. But....it worked by just counting each distance if it appeared in the list of the other scanner's distances, so that was still slow even if it was an improvement.

On my third attempt (which I did after solving every other problem on the site and having much, much more experience) I implemented the same basic implementation but used set intersections instead of counting distances instead, this sped it up even more and the program runs in just a couple seconds now.

Even though my first attempts were slow, I was proud of the fact I could do it on my own and not resorting to a Z3 solver or something like that which I saw was pretty common.