day19notes.txt

# Part 1

Ah, 3D volumes. I'm getting bad memories of a particularly difficult problem in
a past AoC that involved 3D octahedrons…

The input has 28 scanner blocks, each with 26 beacons. The coordinates are
all in the -1000..1000 range.

The text is very long. I jumped to the question: how many beacons are there?

OK, how's this for a plan to match scanners?

  - for each scanner A in the input:
    - for each possible orientation R (represented as a 3x3 rotation matrix):
      - transform A's beacons according to R;
      - for each other scanner B coming after A in the input:
        - for each rotated beacon a in A's set:
          - for each beacon b in B's set:
            - compute a translation vector v that brings a to b (that is, v=b-a);
            - set match counter to 0;
            - for each beacon b2 in B's set:
              - for each beacon a2 in A's set:
                - if a2+v == a2, increase match counter;
                - if match counter equals 12:
                  - record that A matches B with orientation R and translation v;
                  - go pick the next B.

Wow that's some deep nested loops. Calling Ns the number of scanners and Nb the number
of beacons per scanner, let's annotate this with counts:

 Ns           |  - for each scanner A in the input:
 * 24         |    - for each possible orientation R (represented as a 3x3 rotation matrix):
              |      - transform A's beacons according to R;
 * (Ns-1)/2   |      - for each other scanner B coming after A in the input:
 * Nb         |        - for each rotated beacon a in A's set:
 * Nb         |          - for each beacon b in B's set:
              |            - compute a translation vector v that brings a to b (that is, v=b-a);
              |            - set match counter to 0;
 * Nb         |            - for each beacon b2 in B's set:
 * Nb         |              - for each beacon a2 in A's set:
              |                - if a2+v == a2, increase match counter;
              |                - if match counter equals 12:
              |                  - record that A matches B with orientation R and translation v;
              |                  - go pick the next B.

That's roughly Ns^2 * Nb^4 * 12 vector comparisons we'd be doing, in the worst case
where all beacon sets are disjoint (which can't happen in the given input
according to the problem statement).

With Ns=28 and Nb=26, that comes out at 4,299,230,208 comparisons. Of course, we'll never reach
that count, but it still feels high.

Is there any way to reduce that number?

We could stop trying to find the right translation to match beacons between two scanners
as soon as it's clear that we won't find 12 common beacons, i.e. if we tried aligning
one beacon in A with (Nb-11) of B's beacons so far and no match has been found, it's
impossible to find a match that will work. That could bring down the count by about
half? Likewise, when matching we can stop as soon as (Nb-11) comparisons have failed,
that'd be about another half down.

We'd be at Ns^2 * Nb^4 * 3, which is still about a billion.

What if we focused on beacons instead? There are clearly less than 728 of them.
In fact, I think the maximum count would be reached if each scanner overlapped
a single other scanner by 12 beacons, which would make the beacon count
(Ns-1)*(Nb-12)+Nb. That would be 624 beacons in the input.

Anyway, can we take a beacon as seen by one scanner and look for matches in the other
scanners? To be a match, it would have to see at least 11 of its friends in the same
relative positions after any rotation. Hmm, that looks like my original loop but
switched around, I'm not hopeful that it would improve things.

Ideally, we could compute some sort of rotation- and translation-invariant
signature for each scanner, so that we could then pair them up.

But we only require 12 beacons to match between a pair of scanners… we'd have
to compute c(n,k) signatures for each scanner and match those up, and
c(26,12) is 9,657,700… not going to work.

Taking a peek at the leaderboard, it starts at 00:15:57 for this first star,
which almost certainly means that the problem does not have a "trivial" solution.

The relevant Wikipedia page is https://en.wikipedia.org/wiki/Point_set_registration . I'm
not hopeful, but let's keep an open mind.

Thinking of beacons again, but using the constraint that each scanner sees all beacons
within a cube… if we look at a beacon, and take its closest neighbor in each of the
6 axis-parallel directions (+X,-X,+Y,-Y,+Z,-Z); I believe we can say that any scanner
that sees this beacon has to also see some of these. Ah, but no, this doesn't work.

Wikipedia mentions graph matching; indeed, if we see each scanner as a complete graph
of distances between the beacons it sees (that's 26*25+2=325 edges), solving an
inexact graph matching problem would help in finding matched scanners. Ah, but it
appears that just the "Subgraph isomorphism problem" is NP-complete…

Oh well, let's get on with parsing anyway, maybe some idea will come up.

Parsing done. That was the easy part, unfortunately…

Would sorting the beacons of a scanner help with the matching? Probably, but
does it significantly reduce the complexity?

Given two lists of ordered values:

    -----A------A----A--A-----------A----------A------
    ---B----B---B-B---------B----B----------B---------

Once we have picked a pair of beacons to align (here, the first of each list):

    ---A------A----A--A-----------A----------A------
    ---B----B---B-B---------B----B----------B---------

We can advance through both lists in parallel:

  - while i<len(A) and j<len(B) and match count<12:
    - if A[i] == B[j], increase match count, increase i, increase j;
    - otherwise if A[i] < B[j], increase i;
    - otherwise, increase j.

If the match count did not reach the target (12), we have to try aligning the
next pair. Is there an optimal order for testing the Nb*Nb alignment pairs?
Not that I can think of. However, it would be better not to test the same
alignment twice (which would happen if some beacons are aligned but less than
12). But checking for that would not improve the worst case where no beacons
are aligned at all.

So, with sorted beacon lists, the matching step goes from Nb*Nb steps to just
around 2*Nb (in the worst case in the loop above, i and j increase alternately,
which gets us to the end of the list in 2*Nb steps).

This brings the total cost to Ns^2 * Nb^3 * 6, I think. I'm not counting the
cost of the sort, because even if I use a naive O(n^2) approach, sorting 26
items 28*24 times shouldn't be significant in the grand scheme of things.

              |  - for each scanner A in the input:
              |    - insertion-sort its beacon list (can be done while parsing).
 Ns           |  - for each scanner A in the input:
 * 24         |    - for each possible orientation R (represented as a 3x3 rotation matrix):
              |      - transform A's beacons according to R, insertion-sorting them into a list;
 * (Ns-1)/2   |      - for each other scanner B coming after A in the input:
 * (Nb-11)    |        - for each rotated beacon a in A's first (Nb-11) beacons:
 * (Nb-11)    |          - for each beacon b in B's first (Nb-11) beacons:
              |            - compute a translation vector v that brings a to b (that is, v=b-a);
              |            - set match counter to 0;
              |            - set i to 0, j to 0;
 * Nb*2       |            - while i<len(A) and j<len(B) and match count<12:
              |              - if A[i]+v == B[j], increase match count, increase i, increase j;
              |              - otherwise if A[i]+v < B[j], increase i;
              |              - otherwise, increase j.
              |            - if match counter equals 12:
              |              - record that A matches B with orientation R and translation v;
              |              - go pick the next B.

Tightening the counts as planned, we get Ns*24*(Ns-1)/2*(Nb-11)*(Nb-11)*Nb*2 (whee).
This is barely 106,142,400 vector comparisons! Almost easy now.

There's a small further optimization to be made to sorted list matching: once we've picked
a beacon in A and a beacon in B to align, there's no point in testing any beacon
to the left of the aligned ones — we must have already tested this alignment! Alternatively,
start matching at the start of the lists but if any match is found to the left, abort
this alignment because it must have been tested already.

I believe either formulation would reduce the Nb*2 factor above, but maybe not enough
to justify the added risk of a mistake.

Well, time to implement some stuff I guess. Should I make a list, or will this give
me suicidal thoughts? I need:

  - a vector3-list type with a sorted-insert operation;
  - a matrix3 type with a matrix*vector operation;
  - a function that fills a new vector3-list by applying a matrix3 to each
    element of an existing list;
  - a list of 24 matrix3 values, one for each possible orientation;
  - a function that fills a new vector3-list by adding a vector3 to each
    element of an existing list;
  - a function that counts common elements between two vector3-lists;
  - a function that tests whether two vector3-lists have 12 alignable elements by
    testing every possible translation and returning the right translation if found;

Well that doesn't look so bad in fact. With all these basic bricks, writing the master
algorithm shouldn't be too hard:

  - for each scanner in the input, parse its beacons into a sorted vector3-list;
  - for each scanner A:
    - for each possible orientation R (represented as a 3x3 rotation matrix):
      - transform A's beacons according to R, insertion-sorting them into a list;
      - for each other scanner B coming after A:
        - if A's rotated beacons can align with B's beacons with translation v:
          - record that A matches B with orientation R and translation v;
          - go pick the next B.

Of course then I will have to answer the real question, which looks like filling
a graph:

  - mark scanner 0;
  - repeat until all scanners are marked:
    - for each scanner other than 0:
      - if there is a record of a match (R,v) with a marked scanner:
        - apply R then v to its beacons;
        - insert them into scanner 0's beacon list (skipping duplicates);
        - mark this scanner.
  - return the length of scanner 0's beacon list.

Let's get on with it.

That vector3-list type is my scanner type in fact.

Well, it's been 6 hours and I have:
  - a vector3-list type with a sorted-insert operation.

Yay.

On to rotation matrices. Do I really need full-blown 3x3 matrices? Not really.
Every useful rotation can be expressed as e.g. +Y+Z+X :

  1 0 0   0 0 1   0 1 0
  0 1 0   1 0 0   0 0 1
  0 0 1   0 1 0   1 0 0
  +X+Y+Z  +Y+Z+X  +Z+X+Y

I should actually be able to encode these into functions, e.g.

  ( *vout *vin -- )
  @+y+z+x
     STH2 ( vout* : vin* )
     STH2rk #0002 ADD2 LDA2 OVR2 STA2 2++
     STH2rk #0004 ADD2 LDA2 OVR2 STA2 2++
     STH2r  #0000 ADD2 LDA2 SWP2 STA2
     RTN

Some orientations need to flip some axes though:

  1  0  0 
  0 -1  0  
  0  0 -1  
  +X-Y-Z 

So the general form of the function would be:

  ( *vout *vin -- )
  @+x-y-z
     STH2 ( vout* : vin* )
     STH2rk #0000 ADD2 LDA2 #0001 MUL2 OVR2 STA2 2++
     STH2rk #0002 ADD2 LDA2 #ffff MUL2 OVR2 STA2 2++
     STH2r  #0004 ADD2 LDA2 #ffff MUL2 SWP2 STA2
     RTN

All that's left is to generate those. Not every permutation of XYZ combined
with a +/- vector is valid though. For example, +X+Z+Y is not a rotation.

One way of checking is to do the cross product between the first two: the
result must be the third vector.

OK, I've written an ugly bit of JavaScript to generate all the (hopefully
correct) 24 functions, plus a selector that returns a function pointer
given a rotation id between 0 and 23. I want to revisit this later to
actually generate the code in memory from UXN code, but that will have
to do for now.

I can now check off those two additional items:
  - a matrix3 type with a matrix*vector operation;
  - a list of 24 matrix3 values, one for each possible orientation;

Next up are:
  - a function that fills a new vector3-list by applying a matrix3 to each
    element of an existing list;
  - a function that fills a new vector3-list by adding a vector3 to each
    element of an existing list;

Clearly those two call for a `map` implementation on vector lists, I mean
scanners.

OK, that was easy.

What's next on my list?
  - a function that counts common elements between two vector3-lists;

I have planned this out, but there could be surprises.

Well that went satisfyingly smoothly.

Next up is the core logic:
  - a function that tests whether two vector3-lists have 12 alignable elements by
    testing every possible translation and returning the right translation if found;

I have a non-optimized version (tests too many pairs) working, let's move on.

I've thought of a way to avoid having yet another data structure to record
matches between scanners. Here's how it could look:

  - copy scanner 0 to a new "master" scanner;
  - mark scanner 0 as source;
  - repeat:
    - for each scanner A marked as source:
      - for each unmarked scanner B:
        - for each rotation R:
          - count matches between A and R(B);
          - if the target match count is reached:
            - overwrite B with R(B)+v;
            - merge B into the master scanner;
            - mark B as source.
      - mark A as done.
    - if no scanner remains as source, we are done.
  - count the beacons in the master scanner.

This should first find all scanners that share beacons with scanner 0, then
expand the set to scanners that share beacons with those, and so on until
we have everything aligned.

Let's write a function that starts with one scanner and tries
to align it with every other one.

I'm starting to have something that I can run on the large sample… but it doesn't
find any match between scanner 0 and any other scanner, even though the text says
scanners 0 and 1 overlap (also, it is taking around two seconds for each scanner
pair which is more than I expected, but I'll worry about that later).

Let's see, [-618,-824,-621] (from scanner 0) is supposed to be the same beacon
as [686,422,578] (from scanner 1).  And we're told the offset of scanner 1
relative to scanner 0 is [68,-1246,-43].

There has to be a rotation that aligns those points, which is it?

Ah, printing every possibility with that offset, I have found that indeed,
with rotation number 4 (-X+Y-Z) scanner 1's beacons do look a lot like
scanner 0's. Why doesn't my find-alignment function work?

This [68,-1246,-43] offset must be the difference between a beacon in scanner
0's list and one in scanner 1's rotated right? Let's print all the vectors
find-alignment tries.

Ah, it doesn't appear. Hmm, but the first offset we're trying is
[11398 500 10032] which doesn't make any sense, all the coordinates
are between -3000 and 3000 at this point.

Aaand I forgot to dereference one pointer, of course.

Aaaaah I got the correct result for the sample! On the first complete run,
too. But I faked the selection of sources, one last bit to work out.

The run is a bit long on the full input, but it does get to an answer of
323 beacons… which is correct, yay!

Let's hope part 2 will be quick.

# Part 2

OK, now we have to find the positions of the scanners. I think we've already
done the hard work, I just need to compute the positions… relative to scanner 0,
for example, since this is what I've been doing.

I just had to save the offset vectors which were already available, and then
find the maximum of all Manhattan distances. I didn't try to be smart, and
just computed every pair of distances. The answer is correct for the sample
input, will it work on the real one? The answer in a few seconds, because
that thing does run slowly… and the answer is correct.

Wow, that was a long one. And I'm not proud of my solution which is still
basically brute force, I wonder what better alternatives existed…