day19

8 files changed, 1531 insertions, 0 deletions

diff --git a/2021/day19/day19 b/2021/day19/day19
new file mode 100755
index 0000000..c00434d
--- /dev/null
+++ b/2021/day19/day19
diff --git a/2021/day19/day19.cpp b/2021/day19/day19.cpp
new file mode 100644
index 0000000..f45d7ca
--- /dev/null
+++ b/2021/day19/day19.cpp
@@ -0,0 +1,272 @@
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <vector>
+
+
+class Beacon {
+	public:
+	Beacon() { x=y=z=0; }
+	Beacon(int x, int y, int z): x(x), y(y), z(z) { }
+	Beacon(const Beacon &b) { x=b.x; y=b.y; z=b.z; }
+
+	int x,y,z;
+
+	bool operator==(const Beacon& r) { 
+		return x==r.x && y==r.y && z==r.z;
+	}
+	friend bool operator==(const Beacon& l, const Beacon& r) { 
+		return l.x==r.x && l.y==r.y && l.z==r.z;
+	}
+
+	std::string show () {
+		std::string rep = 
+			std::to_string(x) + "," +
+			std::to_string(y) + "," +
+			std::to_string(z) + "\n";
+		return rep;
+	}
+};
+
+class Scanner {
+	public:
+	Scanner() { }
+	Scanner(const Scanner &s) { 
+		for (Beacon b : s.beacons) beacons.emplace_back(b);
+	}
+
+	int x,y,z;
+	std::vector<Beacon> beacons;
+	bool fixed = false;
+
+	bool operator==(const Scanner& r) { 
+		return x==r.x && y==r.y && z==r.z && beacons == r.beacons;
+	}
+
+	std::string show () {
+		std::string rep = "scanner\n";
+		for (Beacon b : beacons) {
+			rep += "  beacon at " + b.show();
+		}
+		return rep;
+	}
+
+	Scanner scale (int x, int y, int z) {
+		Scanner s;
+		for (Beacon& b : beacons) {
+			s.beacons.emplace_back(b.x*x, b.y*y, b.z*z);
+		}
+		return s;
+	}
+
+	Scanner rotate (int axis, int pi_halves) {
+		Scanner s;
+		int sin = pi_halves < 2 ? pi_halves : -pi_halves+2;
+		pi_halves = (pi_halves+1) % 4;
+		int cos = pi_halves < 2 ? pi_halves : -pi_halves+2;
+		for (Beacon& b : beacons) {
+			if (axis == 2)
+				s.beacons.emplace_back(
+					b.x*cos - b.y*sin, 
+					b.x*sin + b.y*cos,
+					b.z);
+			if (axis == 1)
+				s.beacons.emplace_back(
+					b.x*cos + b.z*sin, 
+					b.y,
+					-b.x*sin + b.z*cos);
+			if (axis == 0)
+				s.beacons.emplace_back(
+					b.x, 
+					b.y*cos - b.z*sin,
+					b.y*sin + b.z*cos);
+		}
+		return s;
+	}
+
+	Scanner rebase (bool swapxy, bool swapyz, bool swapxz) {
+		Scanner s;
+		int tmp;
+		for (Beacon& b : beacons) {
+			Beacon a { b };
+			if (swapxy) { tmp = a.x; a.x = a.y; a.y = tmp; }
+			if (swapyz) { tmp = a.y; a.y = a.z; a.z = tmp; }
+			if (swapxz) { tmp = a.x; a.x = a.z; a.z = tmp; }
+			s.beacons.push_back(a);
+		}
+		return s;
+	}
+
+	Scanner translate (int x, int y, int z) {
+		Scanner s;
+		for (Beacon& b : beacons) {
+			s.beacons.emplace_back(b.x+x, b.y+y, b.z+z);
+		}
+		return s;
+	}
+
+	int overlap (Scanner oth) {
+		int sum = 0;
+		for (Beacon &b : beacons) {
+			if (std::find(std::begin(oth.beacons), std::end(oth.beacons), b)
+					!= std::end(oth.beacons)) {
+				sum++;
+			}
+		}
+		//std::cout << sum << " ";
+		return sum;
+	}
+};
+
+
+std::vector<Scanner> orientations (Scanner source) {
+	std::vector<Scanner> orientations;
+	for (int i=0; i<4; i++) {
+		Scanner rotated = source.rotate(0, i);
+		for (int j=0; j<6; j++) {
+			Scanner based { rotated };
+			if (j==1) {
+				based = rotated.rotate(1, 1);
+			}
+			if (j==2) {
+				based = rotated.rotate(1, 2);
+			}
+			if (j==3) {
+				based = rotated.rotate(1, 3);
+			}
+			if (j==4) {
+				based = rotated.rotate(2, 1);
+			}
+			if (j==5) {
+				based = rotated.rotate(2, 3);
+			}
+			orientations.push_back(based);
+		}
+	}
+	return orientations;
+}
+
+Beacon parse_beacon (std::string raw) {
+	Beacon b;
+
+	auto comma = raw.find(",");
+	b.x = std::stoi(raw.substr(0, comma));
+	raw = raw.substr(comma+1);
+
+	comma = raw.find(",");
+	b.y = std::stoi(raw.substr(0, comma));
+	raw = raw.substr(comma+1);
+
+	b.z = std::stoi(raw);
+	
+	return b;
+}
+
+std::vector<Scanner> parse_scanners (std::string raw) {
+	std::vector<Scanner> scanners;
+	while (raw.size() > 0) {
+		auto newline = raw.find('\n');
+		if (newline != std::string::npos) {
+			std::string line = raw.substr(0, newline);
+			raw = raw.substr(newline+1);
+			if (line.find("---") != std::string::npos) {
+				scanners.push_back(Scanner());
+			} else if (line.size() > 1) {
+				Beacon b = parse_beacon(line);
+				scanners[scanners.size()-1].beacons.push_back(b);
+			}
+		} else {
+			Beacon b = parse_beacon(raw);
+			scanners[scanners.size()-1].beacons.push_back(b);
+		}
+	}
+	return scanners;
+}
+
+int main (int argc, char *argv[]) {
+	std::string raw; std::getline(std::ifstream(argv[1]), raw, '\0');
+	
+	std::vector<Scanner> scanners = parse_scanners(raw);
+
+	std::vector<Beacon> cloud;
+	for (Beacon b : scanners[0].beacons) {
+		if (std::find(std::begin(cloud), std::end(cloud), b) 
+				== std::end(cloud))
+			cloud.push_back(b);
+	}
+	scanners[0].fixed = true;
+	scanners[0].x = 0;
+	scanners[0].y = 0;
+	scanners[0].z = 0;
+
+	while (true) {
+		int fixed_count = 0;
+		bool overlap = false;
+		for (int i=0; i<scanners.size(); i++) {
+			if (scanners[i].fixed) { 
+				fixed_count ++;
+				continue; 
+			}
+			for (int j=0; j<scanners.size(); j++) {
+				if (i == j) continue;
+				if (!scanners[j].fixed) continue;
+				Scanner base = scanners[j];
+				std::cout << "compare " << i << " against " << j << std::endl;
+				auto rebaseds = orientations(scanners[i]);
+				for (Scanner rebased : rebaseds) {
+					for (Beacon as : base.beacons) {
+						for (Beacon bas : rebased.beacons) {
+							int dx = as.x - bas.x;
+							int dy = as.y - bas.y;
+							int dz = as.z - bas.z;
+							int dist = std::abs(scanners[j].x-dx) 
+								+ std::abs(scanners[j].y-dy)
+							   	+ std::abs(scanners[j].z-dz);
+							if (dist > 2000) continue;
+							Scanner translated = rebased.translate(dx, dy, dz);
+							if (base.overlap(translated) >= 12) {
+								std::cout << "overlaps: " << base.overlap(translated) << std::endl;
+								scanners[i].x = dx;
+								scanners[i].y = dy;
+								scanners[i].z = dz;
+								std::cout << "  at: " <<dx<<" "<<dy<<" "<<dz << std::endl;
+								std::cout << "  dist: " <<dist<< std::endl;
+								scanners[i].beacons.clear();
+								for (Beacon b : translated.beacons) {
+									scanners[i].beacons.emplace_back(b);
+									if (std::find(std::begin(cloud), std::end(cloud), b) 
+											== std::end(cloud))
+										cloud.push_back(b);
+								}
+								scanners[i].fixed = true;
+								overlap = true;
+								break;
+							}
+						}
+						if (overlap) break;
+					}
+					if (overlap) break;
+				}
+				if (overlap) break;
+			}
+			if (overlap) break;
+		}
+		if (fixed_count == scanners.size()) break;
+	}
+	std::cout << "beacons: " << cloud.size() << std::endl;
+	int maxdist = 0;
+	for (int i=0; i<scanners.size(); i++) {
+		for (int j=0; j<scanners.size(); j++) {
+			if (i==j) continue;
+			int dist = std::abs(scanners[i].x-scanners[j].x) + 
+				std::abs(scanners[i].y-scanners[j].y) + 
+				std::abs(scanners[i].z-scanners[j].z);
+			maxdist = std::max(dist, maxdist);
+		}
+	}
+	std::cout << "max dist: " << maxdist << std::endl;
+	Scanner s;
+	for (Beacon b : cloud) { s.beacons.push_back(b); }
+	//std::cout << s.show() << std::endl;
+	return 0;
+}
diff --git a/2021/day19/day19_input.txt b/2021/day19/day19_input.txt
new file mode 100644
index 0000000..c4d50d3
--- /dev/null
+++ b/2021/day19/day19_input.txt
@@ -0,0 +1,1057 @@
+--- scanner 0 ---
+653,279,-501
+679,389,-558
+450,-411,508
+-695,711,321
+-488,-362,828
+617,622,535
+-596,-479,787
+728,-588,-541
+616,666,636
+-519,-440,-646
+469,-429,698
+-635,554,281
+640,303,-449
+-770,512,-877
+-529,-488,839
+-786,405,-744
+767,-717,-435
+548,579,606
+790,-625,-462
+-720,477,-784
+377,-427,714
+-568,-589,-703
+-84,-26,-131
+-732,508,283
+-563,-492,-674
+
+--- scanner 1 ---
+-425,386,591
+-449,587,580
+-737,898,-600
+39,0,43
+-645,-653,-656
+-402,-614,731
+830,-641,327
+-266,-604,717
+-370,522,564
+866,-710,-689
+680,-782,-665
+151,98,-78
+601,691,573
+609,646,603
+-558,-794,-706
+-587,-690,-787
+-325,-593,829
+840,789,-549
+660,730,605
+964,-667,426
+916,775,-606
+-641,913,-518
+854,-689,-684
+-779,967,-499
+981,-556,328
+880,619,-599
+
+--- scanner 2 ---
+-433,-534,544
+-435,-569,466
+-705,516,451
+-434,544,-451
+369,755,357
+461,-845,-641
+822,-764,631
+417,688,299
+-442,538,-730
+536,-887,-638
+-400,455,-614
+692,-911,609
+-59,-121,-99
+806,-924,631
+-496,-441,444
+294,507,-497
+599,-720,-655
+-740,520,635
+37,37,-30
+-890,-444,-800
+-863,-447,-834
+-879,480,518
+290,513,-492
+-749,-402,-893
+352,664,336
+340,609,-603
+
+--- scanner 3 ---
+-348,-472,472
+-558,-639,-485
+-336,520,435
+-481,573,504
+424,769,720
+-585,-735,-357
+694,558,-469
+-471,-546,556
+-568,-597,-374
+-565,602,-500
+-382,-571,618
+759,-499,667
+578,-411,-282
+676,-398,-459
+-776,616,-534
+897,559,-455
+-650,523,-483
+120,-117,136
+680,528,-464
+13,46,71
+571,-431,-514
+-414,483,404
+716,-571,807
+477,704,692
+750,-562,669
+439,778,664
+
+--- scanner 4 ---
+363,290,737
+-335,752,-760
+497,-574,-841
+377,258,745
+-597,-673,530
+804,592,-647
+-419,429,408
+-531,-559,-697
+720,-491,332
+-579,-691,493
+-434,757,-708
+648,-473,470
+30,-145,-62
+-456,371,539
+-421,713,-633
+-651,-465,-741
+-568,-502,-705
+847,627,-734
+-315,458,489
+464,-500,-766
+871,763,-642
+476,-762,-754
+630,-631,371
+-636,-879,528
+524,342,789
+
+--- scanner 5 ---
+690,-755,-689
+-611,537,489
+-343,-379,-410
+-723,456,581
+-501,-305,537
+711,-689,-650
+649,-691,749
+610,-554,699
+440,509,-934
+528,-744,-704
+379,722,524
+-443,606,-793
+-384,389,-775
+629,493,-909
+-451,-365,555
+553,686,591
+-425,-382,657
+-395,-509,-393
+-557,452,-767
+-318,-512,-543
+-680,463,347
+594,-809,704
+498,476,-829
+518,682,407
+93,14,-140
+-10,126,-47
+
+--- scanner 6 ---
+-747,-534,-657
+492,747,-778
+-486,-843,608
+-856,692,-388
+609,291,458
+-560,411,812
+819,-770,-561
+809,268,474
+-934,706,-423
+-103,-16,-39
+-795,684,-401
+-678,476,744
+826,-857,-547
+279,-953,525
+804,350,472
+517,756,-667
+360,817,-689
+342,-811,502
+287,-779,445
+3,-147,34
+-653,-801,609
+-810,-525,-659
+-692,-892,627
+-569,471,678
+-738,-568,-519
+790,-667,-546
+
+--- scanner 7 ---
+-859,543,-643
+-688,703,750
+474,-589,-775
+-653,724,701
+56,-84,105
+-801,601,-786
+572,-617,718
+285,271,-813
+790,356,960
+-828,-626,785
+-781,-713,752
+741,399,853
+-721,731,586
+-428,-510,-698
+368,-691,-821
+-465,-534,-763
+-135,30,139
+773,477,824
+-486,-443,-746
+-801,-545,856
+409,326,-775
+449,-515,775
+363,-685,-825
+-69,-137,-19
+-869,495,-810
+286,249,-743
+472,-538,601
+
+--- scanner 8 ---
+-396,-737,680
+483,-575,509
+333,-689,-363
+484,698,621
+765,457,-321
+-757,718,-734
+503,709,526
+-633,-800,-470
+-859,810,-752
+-461,775,657
+-430,714,667
+346,726,628
+-438,-812,677
+706,521,-362
+401,-631,370
+-464,633,563
+-563,-674,663
+-58,-117,99
+-657,-678,-500
+75,-151,-41
+-749,-683,-483
+401,-730,-277
+554,498,-360
+-774,779,-584
+367,-636,-447
+377,-596,416
+
+--- scanner 9 ---
+484,-612,591
+775,361,557
+705,529,-688
+-731,-684,738
+78,-171,67
+-811,-550,-451
+833,426,477
+541,-620,628
+-319,571,-741
+758,-717,-722
+-353,477,-911
+-637,479,348
+-285,518,-825
+447,-576,508
+822,-730,-593
+-637,417,352
+-661,373,419
+-770,-557,824
+-661,-592,-479
+-775,-609,725
+681,407,-718
+-11,-32,-55
+740,461,438
+797,524,-705
+920,-726,-706
+-746,-734,-439
+
+--- scanner 10 ---
+582,-825,-367
+777,282,-340
+585,-505,910
+814,270,652
+-83,-178,5
+-138,5,134
+-530,780,-769
+442,-782,-439
+845,348,615
+580,-816,-430
+557,-543,836
+-849,669,725
+-861,666,644
+-686,-549,-524
+-685,-507,-691
+693,405,-414
+-808,659,829
+-571,-681,677
+-440,-753,700
+-448,744,-690
+-586,786,-585
+631,316,-439
+-704,-458,-485
+745,415,705
+529,-490,901
+-445,-604,758
+
+--- scanner 11 ---
+-812,-468,444
+42,154,104
+814,-318,-477
+340,-662,520
+-421,596,-609
+625,733,649
+561,731,418
+-525,-733,-430
+405,521,-706
+-580,815,637
+-805,-702,487
+376,543,-827
+-514,-786,-476
+358,-630,477
+-58,40,-16
+760,-222,-539
+-656,568,-600
+-612,780,713
+-570,681,-544
+377,509,-606
+575,717,470
+-731,-560,556
+811,-351,-473
+-616,-729,-412
+-393,791,711
+355,-620,435
+
+--- scanner 12 ---
+-718,-584,-698
+835,-490,226
+-519,748,-479
+-402,696,215
+-397,690,211
+-508,594,261
+-320,-244,293
+-635,665,-521
+730,683,-819
+546,687,-784
+438,-553,-727
+-319,-266,223
+431,539,273
+613,723,-958
+394,515,338
+-443,-321,261
+-607,-542,-708
+-735,-446,-681
+-356,659,-513
+-74,-31,6
+388,-690,-688
+825,-538,393
+767,-596,250
+433,-808,-743
+14,159,-94
+452,448,290
+
+--- scanner 13 ---
+348,-635,532
+-795,574,275
+363,401,507
+350,-600,454
+488,493,-760
+-83,185,-28
+-777,-258,597
+612,400,474
+-762,491,-914
+-839,465,334
+664,-767,-905
+-891,-245,619
+-910,432,316
+-116,-3,-136
+438,406,-652
+-684,-449,-667
+-907,-405,619
+805,-725,-812
+516,412,527
+-621,-282,-650
+431,504,-736
+778,-722,-846
+411,-728,432
+-783,597,-821
+-546,-324,-653
+-727,515,-960
+
+--- scanner 14 ---
+-638,-690,564
+791,913,-314
+646,-771,-483
+685,-674,-615
+645,-656,-614
+-468,606,426
+426,665,832
+688,879,-425
+761,763,-350
+356,-472,523
+-534,473,338
+-587,621,-738
+399,640,788
+463,-488,390
+-489,-739,621
+-504,-548,-411
+-460,664,-613
+-700,681,-651
+-80,4,29
+-542,-632,-530
+-541,-695,593
+-542,-763,-448
+-470,455,464
+339,658,887
+428,-538,483
+
+--- scanner 15 ---
+58,76,63
+-435,-686,-512
+506,-397,-727
+-397,-611,-526
+581,704,763
+450,705,851
+-597,462,309
+309,565,-904
+-691,465,451
+-587,431,370
+-633,-483,386
+303,-568,301
+-694,798,-728
+-712,851,-712
+-626,-345,358
+-535,-660,-629
+-119,20,-59
+412,-374,-715
+-794,810,-820
+317,-582,547
+351,-305,-725
+484,729,852
+-728,-502,375
+279,636,-888
+339,-506,456
+72,-64,-129
+410,575,-868
+
+--- scanner 16 ---
+617,736,277
+688,-661,-586
+-66,162,-156
+663,-599,-497
+-901,-438,312
+-865,-437,502
+411,717,326
+578,718,368
+672,-548,635
+663,-410,601
+-417,611,358
+-642,725,-553
+-742,675,-565
+762,-745,-463
+333,562,-961
+-894,-452,399
+-462,-353,-657
+-354,634,216
+-808,741,-608
+-10,7,-48
+-362,554,390
+412,480,-925
+735,-550,644
+517,618,-967
+-352,-307,-603
+-381,-499,-613
+
+--- scanner 17 ---
+523,737,-476
+696,-575,-567
+649,-639,670
+-704,-853,400
+639,695,-559
+731,-651,-535
+709,247,423
+-726,397,-541
+633,-818,620
+-542,432,-537
+-635,704,513
+-786,-801,-760
+647,-870,606
+-64,-95,-3
+-535,641,420
+802,388,381
+-714,-811,403
+-746,-768,385
+-552,-844,-767
+707,-577,-348
+-609,258,-501
+743,274,426
+360,703,-565
+-557,702,548
+-644,-732,-686
+
+--- scanner 18 ---
+-863,443,-642
+29,48,-152
+-589,924,395
+571,597,-692
+-832,382,-652
+322,-563,611
+-729,-831,254
+263,-790,614
+643,459,681
+-565,925,429
+343,-710,-639
+-590,836,526
+-719,-795,355
+320,-665,682
+-829,524,-746
+372,-727,-648
+-443,-639,-767
+673,540,-569
+475,563,661
+-658,-815,224
+-496,-655,-749
+562,530,708
+-484,-747,-849
+-118,140,-78
+650,714,-592
+245,-740,-693
+
+--- scanner 19 ---
+485,-544,652
+518,316,730
+605,736,-430
+747,776,-345
+-598,-389,-762
+602,-651,-847
+9,-73,17
+-563,-343,-738
+132,82,56
+-505,390,-806
+563,764,-280
+399,-418,582
+-590,600,615
+-632,675,632
+-317,-508,563
+-619,-482,-656
+-326,-658,462
+541,358,605
+395,-446,541
+-431,-624,555
+652,-543,-760
+-464,304,-738
+-558,474,-772
+-491,553,622
+449,395,626
+595,-567,-749
+
+--- scanner 20 ---
+-691,605,537
+-435,-661,772
+-906,-749,-307
+-44,-155,-21
+741,649,513
+-879,-657,-284
+538,-712,454
+723,-524,-791
+339,241,-503
+288,370,-437
+759,681,556
+722,-490,-570
+-693,560,586
+-134,32,24
+-783,357,-395
+-659,641,515
+-892,271,-434
+-483,-683,609
+-800,-620,-346
+-403,-641,565
+-840,247,-421
+744,639,471
+694,-502,-670
+285,337,-441
+524,-698,506
+474,-714,685
+
+--- scanner 21 ---
+-478,748,-570
+390,-346,-615
+532,852,538
+-636,870,587
+-633,957,666
+878,-328,544
+973,-486,575
+979,-252,627
+-514,-497,-496
+520,874,444
+-469,965,-539
+-548,-708,-482
+-313,-390,551
+-483,762,-540
+490,-413,-525
+421,-268,-578
+-497,-582,-575
+155,43,-21
+678,545,-394
+-327,-258,417
+706,492,-329
+503,887,660
+5,127,107
+-296,-275,462
+650,507,-320
+-553,812,682
+
+--- scanner 22 ---
+4,-96,-37
+-702,394,-681
+-732,543,758
+687,-874,814
+544,613,-840
+-544,-638,690
+526,629,477
+-725,311,778
+-553,-640,627
+-876,-750,-946
+479,528,-691
+535,641,-605
+665,-896,675
+-686,-751,-910
+409,622,366
+673,-909,736
+-776,418,-868
+-789,-736,-939
+728,-519,-612
+798,-608,-480
+-587,-778,618
+737,-630,-637
+435,581,451
+-627,488,791
+-778,429,-649
+-154,-13,-112
+
+--- scanner 23 ---
+-530,-655,411
+-480,-637,471
+-752,-611,-350
+600,552,649
+620,-443,797
+-634,578,890
+-27,-4,71
+627,680,553
+489,-785,-576
+581,-493,660
+795,301,-552
+829,464,-641
+-640,-703,-431
+-529,523,857
+-559,672,-582
+524,-601,-580
+-709,-845,-357
+-536,755,877
+565,-488,915
+-454,-535,488
+-485,648,-769
+787,580,-558
+-483,637,-550
+350,-668,-616
+610,663,691
+
+--- scanner 24 ---
+-439,889,-868
+-595,879,-749
+-883,-470,742
+-28,-13,-112
+374,769,462
+-899,-512,625
+525,-432,509
+-639,-753,-397
+502,-491,-549
+-563,739,357
+679,822,-904
+777,711,-921
+514,-231,485
+276,748,385
+-882,-632,684
+-93,70,45
+778,796,-770
+-673,883,-919
+541,-367,430
+-417,596,359
+532,-536,-541
+500,-575,-600
+-550,-787,-375
+388,759,326
+-623,-740,-446
+-466,680,489
+
+--- scanner 25 ---
+708,668,622
+-806,-657,-776
+723,-509,572
+752,655,697
+424,670,-419
+-564,558,686
+-147,-12,91
+-6,-113,10
+-943,-776,580
+-781,-792,589
+366,633,-550
+-678,492,-541
+232,-987,-707
+-884,453,-539
+788,-521,756
+-845,-663,576
+370,-933,-688
+-865,-695,-736
+-690,-594,-723
+-470,438,730
+274,-918,-606
+747,754,749
+638,-549,714
+453,774,-500
+-696,510,-504
+-507,521,694
+
+--- scanner 26 ---
+-546,380,-686
+488,-437,-579
+-684,505,-672
+-94,-79,24
+778,778,-493
+431,-448,-603
+566,652,457
+-680,599,491
+-675,691,474
+-783,-541,-518
+-628,-459,268
+-621,338,-689
+-727,-459,-379
+583,-852,740
+579,716,586
+-762,-435,-425
+441,-767,700
+575,814,473
+438,-350,-687
+399,-917,728
+-558,575,461
+805,781,-527
+-722,-425,438
+664,823,-434
+-669,-391,354
+
+--- scanner 27 ---
+-31,106,163
+-652,-639,456
+-11,-63,-23
+-563,-802,490
+-338,652,745
+542,-423,658
+-600,-756,-238
+-569,-523,498
+445,618,-272
+-694,796,-750
+659,612,-258
+-592,926,-716
+362,-839,-246
+805,406,895
+706,552,861
+638,-551,685
+680,-440,675
+-683,904,-764
+476,688,-240
+731,490,772
+-594,-761,-234
+-419,798,701
+340,-838,-316
+-498,-650,-284
+121,63,22
+-309,844,755
+417,-715,-284
+
+--- scanner 28 ---
+-802,564,645
+-667,-713,670
+-23,-19,155
+548,-772,-755
+461,-480,585
+-666,-755,837
+-91,118,35
+-460,697,-758
+599,-446,576
+-685,-804,631
+330,780,467
+601,-437,513
+-416,579,-764
+-629,615,-772
+-426,-658,-612
+365,794,389
+-552,-581,-531
+576,-719,-690
+-870,499,763
+780,653,-620
+343,772,528
+722,611,-638
+857,595,-734
+-736,559,754
+604,-757,-764
+-421,-509,-554
+
+--- scanner 29 ---
+525,-354,-804
+-738,428,492
+-744,-454,511
+817,588,-679
+-351,650,-317
+401,-316,-859
+-757,377,424
+-745,-397,620
+716,-702,343
+165,88,82
+800,605,-541
+640,397,672
+-782,-307,588
+-685,-343,-529
+-624,402,396
+-356,634,-572
+-306,595,-435
+-3,-46,35
+402,-386,-881
+-753,-319,-635
+-743,-486,-587
+674,608,658
+689,615,-583
+765,-767,429
+527,-748,406
+691,523,579
+
+--- scanner 30 ---
+-655,-669,507
+-579,676,264
+708,704,345
+698,-730,-690
+647,-412,283
+114,52,-89
+-484,781,-876
+600,754,258
+-695,-628,-911
+794,414,-870
+669,-575,331
+700,-499,-626
+684,-678,-676
+-574,-598,541
+627,-619,251
+853,528,-915
+-32,136,35
+760,387,-873
+-584,844,-783
+-526,580,252
+-663,-671,-893
+-653,-713,-896
+684,761,356
+-559,829,253
+-506,842,-748
+-619,-647,539
+
+--- scanner 31 ---
+-390,-774,-465
+614,-606,-647
+797,279,539
+0,-170,153
+-766,649,-232
+-818,636,-256
+362,633,-355
+-483,-724,-430
+768,400,517
+-87,9,112
+-621,-523,487
+-593,-567,539
+411,-714,502
+413,567,-226
+448,-499,540
+-726,724,635
+796,500,505
+530,-630,540
+615,-588,-687
+359,629,-322
+-805,786,672
+-832,763,764
+-523,-790,-358
+-709,675,-342
+-564,-572,636
+483,-491,-648
+
+--- scanner 32 ---
+612,-679,-331
+553,-622,596
+662,312,-391
+182,36,67
+545,636,573
+88,-125,-99
+-518,623,-679
+-623,-818,766
+-237,-663,-807
+732,-606,546
+-529,824,-703
+-299,-700,-728
+-473,544,494
+561,243,-349
+580,297,-487
+-502,688,-758
+-744,-796,795
+492,573,689
+-538,551,695
+-523,-830,794
+501,-608,610
+819,-659,-363
+532,535,748
+-260,-571,-834
+-502,522,582
+656,-637,-411
+
+--- scanner 33 ---
+-70,76,-69
+711,-630,515
+-824,-531,-531
+-869,484,433
+528,787,-600
+-644,-427,547
+654,-622,552
+-385,438,-616
+437,-525,-798
+-478,-482,563
+-421,628,-615
+540,605,486
+334,603,447
+522,568,504
+412,840,-663
+275,-516,-782
+-905,-487,-677
+373,-512,-669
+-544,-439,497
+353,800,-701
+-924,516,376
+-932,342,456
+-934,-477,-485
+748,-666,432
+-392,525,-630
+
+--- scanner 34 ---
+-10,9,-42
+-525,781,-643
+426,609,-794
+717,-756,724
+-412,-440,-659
+-635,458,930
+-474,-351,-634
+544,556,633
+-523,790,-706
+601,-714,641
+-621,545,923
+629,-527,-566
+603,707,-807
+501,-554,-470
+-636,648,894
+-766,-457,381
+92,136,91
+-574,-467,410
+518,-537,-608
+-720,-511,491
+-328,-317,-733
+658,602,-774
+509,632,665
+-663,747,-634
+533,558,852
+880,-722,635
+
+--- scanner 35 ---
+-880,894,-337
+-669,-532,-317
+-599,761,353
+-862,823,-370
+-577,875,340
+-577,891,500
+424,456,-655
+-921,779,-479
+-764,-427,823
+262,-649,761
+431,422,582
+372,547,-673
+355,-645,-528
+-664,-364,730
+326,-725,-405
+-742,-366,695
+425,459,501
+405,-688,867
+353,586,-657
+-97,91,-21
+-722,-628,-305
+-689,-379,-306
+338,-762,738
+232,-658,-426
+407,502,627
+
+--- scanner 36 ---
+723,406,-525
+611,-867,-526
+-717,282,477
+555,643,396
+706,-878,-545
+-506,-401,686
+-414,279,-360
+-432,350,-393
+669,-802,422
+-717,298,317
+862,462,-443
+-472,-402,662
+575,-944,419
+18,-45,4
+-339,-706,-625
+604,-895,-388
+-325,-952,-611
+-373,394,-502
+-603,-490,661
+552,568,354
+565,-883,388
+816,427,-419
+-361,-797,-549
+-695,412,330
+569,505,521
+
+--- scanner 37 ---
+-770,-521,-464
+-612,-645,914
+-812,732,-690
+-590,-482,866
+-653,473,549
+-830,751,-500
+468,-437,-691
+-632,-438,946
+-814,824,-706
+77,90,53
+-740,-435,-306
+638,-487,-731
+482,-494,-767
+290,-387,928
+566,685,-452
+670,692,598
+-524,434,443
+735,676,519
+-616,411,470
+871,703,574
+-110,-1,30
+611,715,-460
+527,717,-511
+344,-406,790
+-884,-460,-410
+359,-488,886
diff --git a/2021/day19/makefile b/2021/day19/makefile
new file mode 100644
index 0000000..a0b09fe
--- /dev/null
+++ b/2021/day19/makefile
@@ -0,0 +1,2 @@
+all day19.cpp:
+	g++ -std=c++20 day19.cpp -o day19
diff --git a/2021/day19/test0.txt b/2021/day19/test0.txt
new file mode 100644
index 0000000..4e496e9
--- /dev/null
+++ b/2021/day19/test0.txt
@@ -0,0 +1,136 @@
+--- scanner 0 ---
+404,-588,-901
+528,-643,409
+-838,591,734
+390,-675,-793
+-537,-823,-458
+-485,-357,347
+-345,-311,381
+-661,-816,-575
+-876,649,763
+-618,-824,-621
+553,345,-567
+474,580,667
+-447,-329,318
+-584,868,-557
+544,-627,-890
+564,392,-477
+455,729,728
+-892,524,684
+-689,845,-530
+423,-701,434
+7,-33,-71
+630,319,-379
+443,580,662
+-789,900,-551
+459,-707,401
+
+--- scanner 1 ---
+686,422,578
+605,423,415
+515,917,-361
+-336,658,858
+95,138,22
+-476,619,847
+-340,-569,-846
+567,-361,727
+-460,603,-452
+669,-402,600
+729,430,532
+-500,-761,534
+-322,571,750
+-466,-666,-811
+-429,-592,574
+-355,545,-477
+703,-491,-529
+-328,-685,520
+413,935,-424
+-391,539,-444
+586,-435,557
+-364,-763,-893
+807,-499,-711
+755,-354,-619
+553,889,-390
+
+--- scanner 2 ---
+649,640,665
+682,-795,504
+-784,533,-524
+-644,584,-595
+-588,-843,648
+-30,6,44
+-674,560,763
+500,723,-460
+609,671,-379
+-555,-800,653
+-675,-892,-343
+697,-426,-610
+578,704,681
+493,664,-388
+-671,-858,530
+-667,343,800
+571,-461,-707
+-138,-166,112
+-889,563,-600
+646,-828,498
+640,759,510
+-630,509,768
+-681,-892,-333
+673,-379,-804
+-742,-814,-386
+577,-820,562
+
+--- scanner 3 ---
+-589,542,597
+605,-692,669
+-500,565,-823
+-660,373,557
+-458,-679,-417
+-488,449,543
+-626,468,-788
+338,-750,-386
+528,-832,-391
+562,-778,733
+-938,-730,414
+543,643,-506
+-524,371,-870
+407,773,750
+-104,29,83
+378,-903,-323
+-778,-728,485
+426,699,580
+-438,-605,-362
+-469,-447,-387
+509,732,623
+647,635,-688
+-868,-804,481
+614,-800,639
+595,780,-596
+
+--- scanner 4 ---
+727,592,562
+-293,-554,779
+441,611,-461
+-714,465,-776
+-743,427,-804
+-660,-479,-426
+832,-632,460
+927,-485,-438
+408,393,-506
+466,436,-512
+110,16,151
+-258,-428,682
+-393,719,612
+-211,-452,876
+808,-476,-593
+-575,615,604
+-485,667,467
+-680,325,-822
+-627,-443,-432
+872,-547,-609
+833,512,582
+807,604,487
+839,-516,451
+891,-625,532
+-652,-548,-490
+30,-46,-14
diff --git a/2021/day19/test1.txt b/2021/day19/test1.txt
new file mode 100644
index 0000000..3254360
--- /dev/null
+++ b/2021/day19/test1.txt
@@ -0,0 +1,7 @@
+--- scanner 0 ---
+-1,-1,1
+-2,-2,2
+-3,-3,3
+-2,-3,1
+5,6,-4
+8,0,7
diff --git a/2021/day19/test2.txt b/2021/day19/test2.txt
new file mode 100644
index 0000000..28284f8
--- /dev/null
+++ b/2021/day19/test2.txt
@@ -0,0 +1,53 @@
+--- scanner 0 ---
+404,-588,-901
+528,-643,409
+-838,591,734
+390,-675,-793
+-537,-823,-458
+-485,-357,347
+-345,-311,381
+-661,-816,-575
+-876,649,763
+-618,-824,-621
+553,345,-567
+474,580,667
+-447,-329,318
+-584,868,-557
+544,-627,-890
+564,392,-477
+455,729,728
+-892,524,684
+-689,845,-530
+423,-701,434
+7,-33,-71
+630,319,-379
+443,580,662
+-789,900,-551
+459,-707,401
+
+--- scanner 1 ---
+686,422,578
+605,423,415
+515,917,-361
+-336,658,858
+95,138,22
+-476,619,847
+-340,-569,-846
+567,-361,727
+-460,603,-452
+669,-402,600
+729,430,532
+-500,-761,534
+-322,571,750
+-466,-666,-811
+-429,-592,574
+-355,545,-477
+703,-491,-529
+-328,-685,520
+413,935,-424
+-391,539,-444
+586,-435,557
+-364,-763,-893
+807,-499,-711
+755,-354,-619
+553,889,-390
diff --git a/2021/day19/test3.txt b/2021/day19/test3.txt
new file mode 100644
index 0000000..52bea1e
--- /dev/null
+++ b/2021/day19/test3.txt
@@ -0,0 +1,4 @@
+--- scanner 0 ---
+1,0,0
+0,1,0
+0,0,1