This is a huge pattern matching puzzle. Each scanner is in one of 24 orientations. The test input has 5 scanners, the full input has 34. That's 332k combinations for the test input, and 3.5x10^45 for the full input. I don't think I'll be able to just brute-force a solution on this one so easily.
Hmm... actually, I don't need to test every combination against every other one. I just need to match each of them to a reference combination. And since I only need to figure out how many beacons there are, I don't need a 'true' orientation. Scanner 0 will be my reference, 'true' orientation, and the rest will be relative to that. So it's only 24*n combinations to test, minus the initial one. That's 96 and 792 respectively.
But that's only for the individual orientations. There's 25 beacons per scanner, on average, meaning about 25x that. Maybe. But that's still within a good range.
I think I have a good enough grasp on the problem to at least start. First things first though, getting different scanner orientations.
~
Okay, after an hour and a half of trying to figure it out, I'm looking up help....
Someone suggested using a dice as reference to figure out matricies and... ugh, no I"m not doing that. I'm going to hard-code all the different orientation transformations as one big switch statement, and I'm using the die to figure out what all of the values are going to be, using this reference (based on the die I found first):
1, 2, 3, 4, 5, 6
x, y, z,-z,-y,-x
I'm angling the dice with one corner directly facing me, so there's a top, and two bottom faces, like this
I just put each of the faces up, rotated one of four ways each. That's 24! I just map, in order from 1-6, in each orientation, the mapping above of the top, left, and right faces, it should give me all of the orientations. Then from there, I just iterate on those to match them.
It's taken me almost two hours to realize it's fastest to do it by hand. Ha. Pain.
#define IT(i, x, y, z) case i: for (auto b: ref) s.push_back(Beacon(x, y, z)); break;
vector<Beacon> getIteration(vector<Beacon> ref, int iteration) {
vector<Beacon> s;
switch (iteration) {
IT( 0, b.x, b.y, b.z) IT( 1, b.x,-b.z, b.y) IT( 2, b.x,-b.y,-b.z) IT( 3, b.x, b.z,-b.y)
IT( 4, b.y, b.z, b.x) IT( 5, b.y,-b.x,-b.z) IT( 6, b.y,-b.z,-b.x) IT( 7, b.y, b.x,-b.z)
IT( 8, b.z, b.x, b.y) IT( 9, b.z,-b.y, b.x) IT(10, b.z,-b.x,-b.y) IT(11, b.z, b.y,-b.x)
IT(12,-b.z,-b.y,-b.x) IT(13,-b.z, b.x,-b.y) IT(14,-b.z, b.y, b.x) IT(15,-b.z,-b.x, b.y)
IT(16,-b.y,-b.x,-b.z) IT(17,-b.y, b.z,-b.x) IT(18,-b.y, b.x, b.z) IT(19,-b.y,-b.z, b.x)
IT(20,-b.x,-b.z,-b.y) IT(21,-b.x, b.y,-b.z) IT(22,-b.x, b.z, b.y) IT(23,-b.x,-b.y, b.z)
}
return s;
};
And now to see how to compare the points to all of the other points.... ugh.... I don't even know. For each point in scanner S, check it against all of the references, see if there's a 'distfrom' that happens unusually often? I don't know. I'll try it. A dictionary of counts. It says if both see 12 of the same beacon... so if any of the counts are greater than 12, it's a match? I'll test that out...
The following are the matching offset distance (read: Manhattan distance) counts for each orientation.
O 0: [ 1: 502] [ 2: 52] [ 3: 5] [ 4: 1]
O 1: [ 1: 488] [ 2: 64] [ 3: 3]
O 2: [ 1: 495] [ 2: 56] [ 3: 6]
O 3: [ 1: 469] [ 2: 69] [ 3: 6]
O 4: [ 1: 494] [ 2: 58] [ 3: 5]
O 5: [ 1: 484] [ 2: 60] [ 3: 4] [ 9: 1]
O 6: [ 1: 482] [ 2: 64] [ 3: 5]
O 7: [ 1: 491] [ 2: 61] [ 3: 4]
O 8: [ 1: 509] [ 2: 47] [ 3: 6] [ 4: 1]
O 9: [ 1: 457] [ 2: 67] [ 3: 10] [ 4: 1]
O 10: [ 1: 507] [ 2: 53] [ 3: 4]
O 11: [ 1: 505] [ 2: 48] [ 3: 8]
O 12: [ 1: 448] [ 2: 66] [ 3: 11] [ 4: 3]
O 13: [ 1: 508] [ 2: 52] [ 3: 3] [ 4: 1]
O 14: [ 1: 470] [ 2: 68] [ 3: 5] [ 4: 1]
O 15: [ 1: 495] [ 2: 57] [ 3: 4] [ 4: 1]
O 16: [ 1: 504] [ 2: 50] [ 3: 7]
O 17: [ 1: 486] [ 2: 48] [ 3: 13] [ 4: 1]
O 18: [ 1: 511] [ 2: 54] [ 3: 2]
O 19: [ 1: 473] [ 2: 58] [ 3: 9] [ 4: 1] [ 5: 1]
O 20: [ 1: 498] [ 2: 54] [ 3: 5] [ 4: 1]
O 21: [ 1: 497] [ 2: 46] [ 3: 5] [ 4: 2] [13: 1]
O 22: [ 1: 481] [ 2: 61] [ 3: 3] [ 4: 2] [ 5: 1]
O 23: [ 1: 502] [ 2: 57] [ 3: 3]
Just on a first test of the idea and... there! Right there! Orientation #21 has 13 points with the same offset, and it's the only one with that many! Now I just need to identify the orientation and transformation more automatically...
Scanner orientation: [21] offset count of [13]
Scanner orientation: [ 2] offset count of [ 4]
Scanner orientation: [ 5] offset count of [ 5]
Scanner orientation: [ 0] offset count of [ 6]
Hmm... only one scanner actually matches the set. I bet I'll have to actually add the thing to the set before I try with further matches, and if there aren't enough, revisit the scanner later. I have the most frequent offset distance. So once I find that, I just reiterate with that orientation, until I find the matching pair of points again, figure out the difference, and merge them. And find a way to de-duplicate them I guess... but I don't think that will be a big deal? I hope not. Ugh, it'll be inefficient regardless, but if I DO need to optimize, this next step will be a good point.
Scanner orientation: [21] offset of [1357] seen [13] times | Offset: [ 68,-1246, -43]
Good progress, and that ran pretty instantly. Just need to merge...
[ 3 left] Scanner orientation: [21] offset of [1357] seen [13] times | Offset: [ 68,-1246, -43] | Grid size now [ 38] (12 dupes)
[ 3 left] No matching orientations found; revisiting scanner
[ 2 left] Scanner orientation: [21] offset of [2492] seen [13] times | Offset: [-1197,-1196, 99] | Grid size now [ 62] (1 dupes)
[ 1 left] Scanner orientation: [19] offset of [2214] seen [12] times | Offset: [ -20,-1133, 1061] | Grid size now [ 76] (12 dupes)
[ 0 left] Scanner orientation: [22] offset of [3539] seen [12] times | Offset: [ 1105,-1205, 1229] | Grid size now [ 90] (12 dupes)
That... runs fine I guess. But the total number doesn't match.
Comparing the full list of numbers I get vs. what they provide for the example, I see a lot of matches, but also I see a lot of extras. 11 to be exact. And in one of the orientations, only 1 dupe was found, not the expected 12+. This is pretty odd...
I added an extra case, where if there's not enough duplicates expected, I also revisit that beacon. Doing that and...
It works!
I don't even want to share my code for this in this blog. But here's a few snippets:
Main loop to find matches
for (int i = 0; i < 24; i++) {
map<int, int> offsets, counts;
vector<Beacon> iteration = getIteration(s, i);
for (auto ref: grid)
for (auto b: iteration)
offsets[ref.offset(b)]++;
for (auto dist: offsets)
counts[dist.second]++;
for (auto c: counts)
if (c.first >= 12 && c.first > maxPair.second) {
maxPair = pair(i, c.first-1);
for (auto n: offsets)
if (n.second == c.first)
maxOffset = n.first;
}
}
Duplication check (it expects there to be around 12, or more)
int dupeCount = 0;
vector<Beacon> candidates;
for (auto m: matching) {
Beacon candidate = Beacon(m.x+t.x, m.y+t.y, m.z+t.z);
bool dupe = false;
for (auto g: grid)
if (candidate == g) {
dupe = true;
dupeCount++;
break;
}
if (!dupe) candidates.push_back(candidate);
}
if (dupeCount < maxPair.second) {
scanners.push(s);
printf("[%2.1d left] False match found, [%2.1d] duplicates found, expected [%2.1d]; revisiting scanner\n", scanners.size(), dupeCount, maxPair.second);
continue;
}
It mostly works.... but on the full input, it's looping endlessly. Hmm.
If I get through all the scanners and can't match them, then I can cycle to a different one. I don't need to keep one the exact one each time. If I notice that I've done a full loop, I'll do that. I'll keep a counter of every time I don't match with a scanner, and if that gets bigger than the queue, I'll cycle the grid out.
~
That's not quite it. It went much farther this time, but it still didn't quite make it. It looks like there's five disconnected ones.
~
I am an idiot. I found the issue. The REAL issue.
I would have never noticed if I didn't format everything as nice as I did. Ugh.
It's still not working by the way.
~
Okay, it's 2am and I started at 9pm. I'm tired, and I'm stressed. Maybe if I check EVERY combination that has greater than 12 matches, then merge the ones where the duplicates match.
~
2:30am, and I have a revelation. The distances could be a fluke, or a red herring. I'm just doing raw manhattan distances. I need to find the SPECIFIC distance, in the form of basically a vector. I can stringify it to make sure that it hashes better. Let's do it.
Holy shit, that was it. That was it! Aaaa! I was getting goofed by poor offset assumptions. By doing the FULL offset in each direction (using it as a hash), it just worked the first time. I needed to do the full 3d the entire time.
I really f#$%ed myself over by trying to do the Manhattan distance the first time. Ugh. And I was so proud of that the whole time.
I've never been so happy that it's been correct.
Anyway here's my Beacon class. I am as proud as I am ashamed.
class Beacon {
public:
int x, y, z;
Beacon(){};
Beacon(int _x, int _y, int _z) { x = _x; y = _y; z = _z; }
int offset(Beacon b) { return (b.x-x) + (b.y-y) + (b.z-z); }
string offsetHash(Beacon b) { stringstream s; s << "[" << b.x-x << "," << b.y-y << "," << b.z-z << "]"; return s.str(); }
bool operator==(const Beacon & b) { return (x == b.x) && (y == b.y) && (z == b.z); }
bool operator< (const Beacon & b) { return x < b.x; }
};
AHAHAHAHAHAHAHAHAHA You're kidding me.
I now NEED Manhattan distances. Ugh. FML. It's just mocking me.
~
Okay granted I don't actually need it in the same way, and it's just for the individual scanners. I just need to combine all of the transforms I have saved up, then calculate the ones with the largest relative manhattan distances. I don't even need to change my initial code all too much.
// Calculate final distances
int farApart = -1;
for (auto l: scannerPositions)
for (auto r: scannerPositions)
if (l.offset(r) > farApart)
farApart = l.offset(r);
Felt almost trivial after that hell I put myself through...
I need to re-check my assumptions more when I get stuck like this.