Advent of Code 2021 Day 19; https://www.reddit.com/r/adventofcode/comments/rjpf7f/2021_day_19_solutions/hp5i83l/

19.cpp

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <iterator>
#include <algorithm>
using namespace std;

struct Point
{
	int x, y, z;
};

// HACK: Constant zero for explicit conversion between Point and Vec
// as writing conversion constructor will have many consequences
Point ZERO = Point{ 0, 0, 0 };

istream& operator >> (istream& in, Point& p)
{
	char dummy;
	in >> p.x >> dummy >> p.y >> dummy >> p.z;
	return in;
}

ostream& operator << (ostream& out, const Point& p)
{
	out << p.x << ',' << p.y << ',' << p.z;
	return out;
}

struct Vec
{
	int x, y, z;
	int s, t;
	// c++20 spaceship operator
	auto operator <=> (const Vec& v) const
	{
		if(x != v.x) return x <=> v.x;
		if(y != v.y) return y <=> v.y;
					  return z <=> v.z;
	}
};

Vec operator - (Point p1, Point p2)
{
	return Vec{p1.x - p2.x, p1.y - p2.y, p1.z - p2.z, -1, -1};
}

Point operator + (Point p, Vec v)
{
	return Point{p.x + v.x, p.y + v.y, p.z + v.z};
}

int abs(const Vec& v)
{
	return abs(v.x) + abs(v.y) + abs(v.z);
}

const int X = 1, Y = 2, Z = 3;
int sel(int x, int y, int z, int s)
{
	switch(s)
	{
	case X: return x;
	case Y: return y;
	case Z: return z;
	case -X: return -x;
	case -Y: return -y;
	case -Z: return -z;
	default: return 0;
	}
}

function<Vec(const Vec&)> rotate(int myX, int myY, int myZ)
{
	return [=](const Vec& v)->Vec
	{
		return Vec{
			sel(v.x, v.y, v.z, myX), 
			sel(v.x, v.y, v.z, myY), 
			sel(v.x, v.y, v.z, myZ), 
			v.s, v.t
		};
	};
}
// RF for Rotate Function
function<Vec(const Vec&)> RF[24] = {
	rotate(X, Y, Z),
	rotate(X, -Y, -Z),
	rotate(-X, Y, -Z),
	rotate(-X, -Y, Z),
	rotate(X, Z, -Y),
	rotate(X, -Z, Y),
	rotate(-X, Z, Y),
	rotate(-X, -Z, -Y),
	rotate(Y, Z, X),
	rotate(Y, -Z, -X),
	rotate(-Y, Z, -X),
	rotate(-Y, -Z, X),
	rotate(Y, X, -Z),
	rotate(Y, -X, Z),
	rotate(-Y, X, Z),
	rotate(-Y, -X, -Z),
	rotate(Z, X, Y),
	rotate(Z, -X, -Y),
	rotate(-Z, X, -Y),
	rotate(-Z, -X, Y),
	rotate(Z, Y, -X),
	rotate(Z, -Y, X),
	rotate(-Z, Y, X),
	rotate(-Z, -Y, -X),
};

vector<Vec> computeDif(const vector<Point>& p)
{
	vector<Vec> vv;
	for (int s = 0; s < p.size(); s++)
	{
		for (int t = 0; t < p.size(); t++)
		{
			if (s == t) continue;
			Vec v = p[s] - p[t];
			v.s = s;
			v.t = t;
			vv.push_back(v);
		}
	}
	return vv;
}

int main()
{
	vector<vector<Point>> scan;
	vector<Point> scannerPos;
	vector<int> merged;
	string s;
	while(getline(cin, s))
	{
		// skip --- scanner N --- line
		vector<Point> v;
		while(getline(cin, s), s != "")
		{
			stringstream ss(s);
			Point p;
			ss >> p;
			v.push_back(p);
		}
		scan.emplace_back(move(v));
	}
	int N = scan.size();
	merged.resize(N);
	scannerPos.resize(N);
	scannerPos[0] = Point{0,0,0};
	
	vector<Point> v0 = scan[0];
	for(int scanCount = 1; scanCount < N; scanCount++)
	{
		vector<Vec> d0 = computeDif(v0);
		sort(d0.begin(), d0.end());
		bool found = false;
		for(int v = 1; v < N; v++)
		{
			if (merged[v]) continue;
			vector<Vec> dv = computeDif(scan[v]);
			vector<Vec> vr;
			for(int ri = 0; ri < 24; ri++)
			{
				vr.clear();
				// convert Vecs to the specified orientation
				transform(dv.begin(), dv.end(), back_inserter(vr), RF[ri]);
				sort(vr.begin(), vr.end());
				int count = 0;
				vector<Vec> ps, qs;
				map<int, int> tallyP, tallyQ;
				// find equal element in two sorted list
				for(auto p = d0.begin(), q = vr.begin(); p != d0.end() && q != vr.end(); )
				{
					auto cmp = *p <=> *q;
					if(cmp == 0)
					{
						count++;
						ps.push_back(*p);
						qs.push_back(*q);
						tallyP[p->s]++;
						tallyP[p->t]++;
						tallyQ[q->s]++;
						tallyQ[q->t]++;
						p++;
						q++;
					}
					else if(cmp < 0)
					{
						p++;
					}
					else
					{
						q++;
					}
				}
				// find those points that has at least 22 occurances in common Vec
				// 22 comes from both endpoint count once in the 11 pair involving itself
				// These are candidate matched point
				set<int> candidateP, candidateQ;
				for (auto [i, n] : tallyP) if (n >= 22) candidateP.insert(i);
				for (auto [i, n] : tallyQ) if (n >= 22) candidateQ.insert(i);
				// There should both be at least 12 of them for a scanner considered match
				if(candidateP.size() < 12 || candidateQ.size() < 12) continue;
				// This is the actual matched point
				set<int> validQ;
				Vec offset;
				for(int w = 0; w < ps.size(); w++)
				{
					// check if the common Vec has endpoints in the candidate point list
					// BOLD assumption: no two Vecs in the set of common Vecs are the same
					if(candidateP.count(ps[w].s) && candidateP.count(ps[w].t) &&
						candidateQ.count(qs[w].s) && candidateQ.count(qs[w].t))
					{
						validQ.insert(qs[w].s);
						validQ.insert(qs[w].t);
						// 'offset' will calculate many time but should be the same each time it is calculated
						// as this is the position of the matched scanner
						Point tv = ZERO + RF[ri](scan[v][qs[w].s] - ZERO);
						offset = v0[ps[w].s] - tv;
					}
				}
				scannerPos[v] = ZERO + offset;
				cout << "Scanner " << v << " at offset " << scannerPos[v] << endl;
				// Add all points in q not in matched point list into p
				for(int i = 0; i < scan[v].size(); i++)
				{
					Point tv = (ZERO + RF[ri](scan[v][i] - ZERO) + offset);
					if (validQ.count(i) == 0) v0.push_back(tv);
				}
				merged[v] = 1;
				// we want to recalculate Vecs for the base, so reset the loop
				found = true;
				break;
			} // ri
			if(found) break;
		} // v
	} // scanCount
	cout << v0.size() << endl;
	
	// part 2
	int Mdist = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			Mdist = max(Mdist, abs(scannerPos[i] - scannerPos[j]));
		}
	}
	cout << Mdist << endl;
	return 0;
}

19b.cpp

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <iterator>
#include <algorithm>
using namespace std;

struct Point
{
	int x, y, z;
};

// HACK: Constant zero for explicit conversion between Point and Vec
// as writing conversion constructor will have many consequences
Point ZERO = Point{ 0, 0, 0 };

istream& operator >> (istream& in, Point& p)
{
	char dummy;
	in >> p.x >> dummy >> p.y >> dummy >> p.z;
	return in;
}

ostream& operator << (ostream& out, const Point& p)
{
	out << p.x << ',' << p.y << ',' << p.z;
	return out;
}

struct Vec
{
	int x, y, z;
	int s, t;
	// c++20 spaceship operator
	auto operator <=> (const Vec& v) const
	{
		if(x != v.x) return x <=> v.x;
		if(y != v.y) return y <=> v.y;
					  return z <=> v.z;
	}
};

Vec operator - (Point p1, Point p2)
{
	return Vec{p1.x - p2.x, p1.y - p2.y, p1.z - p2.z, -1, -1};
}

Point operator + (Point p, Vec v)
{
	return Point{p.x + v.x, p.y + v.y, p.z + v.z};
}

int abs(const Vec& v)
{
	return abs(v.x) + abs(v.y) + abs(v.z);
}

constexpr int X = 1, Y = 2, Z = 3;
template<int s>
int sel(int x, int y, int z)
{
	if constexpr (s == X) return x;
	else if constexpr (s == Y) return y;
	else if constexpr (s == Z) return z;
	else if constexpr (s == -X) return -x;
	else if constexpr (s == -Y) return -y;
	else if constexpr (s == -Z) return -z;
	else return 0;
}

template<int myX, int myY, int myZ>
Vec rotate(const Vec& v)
{
	return Vec{
		sel<myX>(v.x, v.y, v.z), 
		sel<myY>(v.x, v.y, v.z), 
		sel<myZ>(v.x, v.y, v.z), 
		v.s, v.t
	};
}
// RF for Rotate Function
function<Vec(const Vec&)> RF[24] = {
	rotate<X, Y, Z>,
	rotate<X, -Y, -Z>,
	rotate<-X, Y, -Z>,
	rotate<-X, -Y, Z>,
	rotate<X, Z, -Y>,
	rotate<X, -Z, Y>,
	rotate<-X, Z, Y>,
	rotate<-X, -Z, -Y>,
	rotate<Y, Z, X>,
	rotate<Y, -Z, -X>,
	rotate<-Y, Z, -X>,
	rotate<-Y, -Z, X>,
	rotate<Y, X, -Z>,
	rotate<Y, -X, Z>,
	rotate<-Y, X, Z>,
	rotate<-Y, -X, -Z>,
	rotate<Z, X, Y>,
	rotate<Z, -X, -Y>,
	rotate<-Z, X, -Y>,
	rotate<-Z, -X, Y>,
	rotate<Z, Y, -X>,
	rotate<Z, -Y, X>,
	rotate<-Z, Y, X>,
	rotate<-Z, -Y, -X>,
};

vector<Vec> computeDif(const vector<Point>& p)
{
	vector<Vec> vv;
	for (int s = 0; s < p.size(); s++)
	{
		for (int t = 0; t < p.size(); t++)
		{
			if (s == t) continue;
			Vec v = p[s] - p[t];
			v.s = s;
			v.t = t;
			vv.push_back(v);
		}
	}
	return vv;
}

int main()
{
	vector<vector<Point>> scan;
	vector<Point> scannerPos;
	vector<int> merged;
	string s;
	while(getline(cin, s))
	{
		// skip --- scanner N --- line
		vector<Point> v;
		while(getline(cin, s), s != "")
		{
			stringstream ss(s);
			Point p;
			ss >> p;
			v.push_back(p);
		}
		scan.emplace_back(move(v));
	}
	int N = scan.size();
	merged.resize(N);
	scannerPos.resize(N);
	scannerPos[0] = Point{0,0,0};
	
	vector<Point> v0 = scan[0];
	for(int scanCount = 1; scanCount < N; scanCount++)
	{
		vector<Vec> d0 = computeDif(v0);
		sort(d0.begin(), d0.end());
		bool found = false;
		for(int v = 1; v < N; v++)
		{
			if (merged[v]) continue;
			vector<Vec> dv = computeDif(scan[v]);
			vector<Vec> vr;
			for(int ri = 0; ri < 24; ri++)
			{
				vr.clear();
				// convert Vecs to the specified orientation
				transform(dv.begin(), dv.end(), back_inserter(vr), RF[ri]);
				sort(vr.begin(), vr.end());
				int count = 0;
				vector<Vec> ps, qs;
				map<int, int> tallyP, tallyQ;
				// find equal element in two sorted list
				for(auto p = d0.begin(), q = vr.begin(); p != d0.end() && q != vr.end(); )
				{
					auto cmp = *p <=> *q;
					if(cmp == 0)
					{
						count++;
						ps.push_back(*p);
						qs.push_back(*q);
						tallyP[p->s]++;
						tallyP[p->t]++;
						tallyQ[q->s]++;
						tallyQ[q->t]++;
						p++;
						q++;
					}
					else if(cmp < 0)
					{
						p++;
					}
					else
					{
						q++;
					}
				}
				// find those points that has at least 22 occurances in common Vec
				// 22 comes from both endpoint count once in the 11 pair involving itself
				// These are candidate matched point
				set<int> candidateP, candidateQ;
				for (auto [i, n] : tallyP) if (n >= 22) candidateP.insert(i);
				for (auto [i, n] : tallyQ) if (n >= 22) candidateQ.insert(i);
				// There should both be at least 12 of them for a scanner considered match
				if(candidateP.size() < 12 || candidateQ.size() < 12) continue;
				// This is the actual matched point
				set<int> validQ;
				Vec offset;
				for(int w = 0; w < ps.size(); w++)
				{
					// check if the common Vec has endpoints in the candidate point list
					// BOLD assumption: no two Vecs in the set of common Vecs are the same
					if(candidateP.count(ps[w].s) && candidateP.count(ps[w].t) &&
						candidateQ.count(qs[w].s) && candidateQ.count(qs[w].t))
					{
						validQ.insert(qs[w].s);
						validQ.insert(qs[w].t);
						// 'offset' will calculate many time but should be the same each time it is calculated
						// as this is the position of the matched scanner
						Point tv = ZERO + RF[ri](scan[v][qs[w].s] - ZERO);
						offset = v0[ps[w].s] - tv;
					}
				}
				scannerPos[v] = ZERO + offset;
				cout << "Scanner " << v << " at offset " << scannerPos[v] << endl;
				// Add all points in q not in matched point list into p
				for(int i = 0; i < scan[v].size(); i++)
				{
					Point tv = (ZERO + RF[ri](scan[v][i] - ZERO) + offset);
					if (validQ.count(i) == 0) v0.push_back(tv);
				}
				merged[v] = 1;
				// we want to recalculate Vecs for the base, so reset the loop
				found = true;
				break;
			} // ri
			if(found) break;
		} // v
	} // scanCount
	cout << v0.size() << endl;
	
	// part 2
	int Mdist = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			Mdist = max(Mdist, abs(scannerPos[i] - scannerPos[j]));
		}
	}
	cout << Mdist << endl;
	return 0;
}