commit ce94f146f587858be68c1a1d60cbca8c552412c3
parent 621e1341fae3ec25714d1719caa590af0d012a0a
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Sun, 19 Dec 2021 21:45:22 -0600
Add 2021 day 19
Diffstat:
| A | 2021/day19/input.txt | | | 942 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2021/day19/main.rs | | | 220 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 1162 insertions(+), 0 deletions(-)
diff --git a/2021/day19/input.txt b/2021/day19/input.txt
@@ -0,0 +1,942 @@
+--- scanner 0 ---
+562,-830,765
+477,603,962
+653,638,963
+519,630,969
+484,-859,699
+566,901,-526
+-556,-387,-739
+-556,-734,606
+550,725,-495
+-325,554,-668
+590,-625,-615
+-541,-810,749
+-30,-66,159
+517,-703,-550
+-597,516,531
+-652,-836,647
+-459,-333,-629
+-723,455,466
+453,-635,-512
+-525,450,418
+539,-867,749
+-368,643,-618
+479,808,-450
+128,4,70
+-328,822,-676
+-389,-445,-710
+
+--- scanner 1 ---
+882,-359,-895
+-568,-692,717
+853,785,496
+846,708,399
+-512,-419,-524
+-526,-543,-674
+372,-764,479
+-571,-621,-509
+-520,439,-794
+458,-684,545
+927,754,376
+83,-74,-82
+-34,16,42
+-335,458,283
+-546,559,-745
+-538,389,-663
+850,804,-669
+-501,-835,677
+-294,593,263
+875,812,-738
+916,-458,-747
+848,-422,-693
+820,624,-698
+-379,-734,665
+368,-806,548
+-300,658,258
+
+--- scanner 2 ---
+-598,871,923
+-725,-690,876
+439,339,640
+437,344,708
+279,578,-430
+-839,379,-410
+307,290,735
+-703,869,980
+-401,-616,-550
+781,-856,507
+17,-53,24
+297,447,-579
+816,-803,434
+-648,-694,693
+500,-784,-460
+825,-850,663
+-516,-701,-538
+-862,349,-357
+-854,339,-497
+-737,-670,672
+-570,773,967
+-495,-678,-483
+-160,47,167
+259,416,-419
+476,-871,-404
+629,-843,-413
+
+--- scanner 3 ---
+747,692,-828
+705,744,-639
+798,-590,547
+634,-482,-636
+662,466,594
+703,520,540
+-445,310,-872
+-548,-650,547
+-645,285,-907
+556,-647,-681
+-376,-636,-669
+696,636,550
+432,-497,-695
+-623,301,435
+-426,-767,-687
+592,-610,537
+-481,-628,436
+-546,-718,-661
+-24,26,-35
+721,-683,527
+848,704,-706
+-580,290,-913
+137,-123,-61
+-602,423,528
+-616,385,388
+-511,-653,633
+
+--- scanner 4 ---
+-605,534,764
+-407,-493,-557
+588,-470,-451
+-580,628,732
+895,644,417
+763,699,444
+913,653,-385
+904,424,-432
+610,-346,560
+564,-414,-364
+801,568,536
+-313,-560,-619
+-649,662,-565
+869,497,-379
+-560,683,-541
+-849,-480,489
+699,-291,570
+-637,866,-545
+-428,-548,-534
+-25,61,-27
+717,-423,-392
+-553,682,724
+-747,-519,346
+-743,-541,380
+617,-350,465
+
+--- scanner 5 ---
+-689,657,543
+650,-504,353
+-274,-731,537
+-578,-485,-920
+721,417,-745
+-266,-756,468
+-568,605,-500
+927,-725,-368
+475,775,418
+-639,639,412
+-518,478,-386
+721,-591,348
+-683,-488,-858
+527,719,483
+653,422,-747
+-513,450,-508
+-519,665,461
+626,368,-877
+438,774,421
+698,-772,-359
+-17,106,-30
+-545,-547,-899
+854,-778,-403
+-454,-701,508
+660,-444,285
+81,-16,-139
+
+--- scanner 6 ---
+550,-633,675
+-565,340,-543
+-272,-440,658
+-462,484,770
+-306,-623,-345
+746,748,735
+-229,-575,-481
+838,710,604
+-208,-429,598
+-329,-682,-421
+-339,492,602
+-459,457,721
+558,-606,621
+600,-861,-663
+-595,402,-598
+135,4,-65
+-326,-420,468
+608,-733,-633
+-522,348,-558
+492,531,-624
+539,702,-692
+518,-658,769
+91,-125,78
+694,-765,-573
+865,842,659
+541,541,-568
+
+--- scanner 7 ---
+530,361,682
+38,-173,51
+776,-905,-578
+-728,-808,-653
+581,470,-696
+-640,-519,731
+-808,-642,739
+-706,-827,-588
+-891,786,-728
+654,359,521
+520,-702,875
+-656,-763,-757
+-759,-639,766
+-771,727,-666
+388,477,-693
+-790,799,-718
+530,488,-723
+-697,685,381
+505,-745,883
+623,-972,-633
+-86,-5,112
+560,-775,821
+659,-897,-513
+-773,566,475
+-642,658,513
+586,312,692
+
+--- scanner 8 ---
+418,475,749
+670,-563,947
+451,550,938
+16,55,-3
+920,428,-411
+886,329,-263
+852,392,-465
+-516,-469,-364
+-567,591,-649
+-534,-419,-495
+-327,-595,556
+879,-842,-420
+-482,-540,548
+-524,598,480
+824,-654,-460
+611,-425,906
+-534,587,613
+608,-530,968
+-355,-590,434
+-542,-589,-413
+511,530,797
+-522,513,-484
+130,-53,118
+-508,389,-634
+854,-834,-489
+-475,513,623
+
+--- scanner 9 ---
+-808,-717,-532
+801,462,-427
+-725,-674,-509
+-404,578,473
+-400,537,482
+-677,620,-628
+-805,-722,-668
+512,-551,-714
+689,389,-392
+737,-639,448
+-553,539,430
+618,459,-517
+853,-526,493
+-731,632,-577
+-21,148,79
+458,-752,-701
+628,479,505
+597,442,601
+-660,-509,702
+-584,-719,707
+-876,668,-590
+-626,-525,747
+459,-614,-745
+796,-677,518
+588,521,668
+
+--- scanner 10 ---
+-389,811,-591
+-444,839,-381
+-419,808,-580
+-645,498,763
+-643,-474,502
+650,744,484
+-160,-15,10
+685,-640,-569
+-584,-485,-673
+654,-733,-711
+-689,-428,-758
+376,888,-343
+13,81,-49
+384,891,-611
+434,848,-522
+749,-447,913
+685,-446,771
+-688,-540,570
+-594,380,787
+682,-794,-523
+496,724,531
+-35,147,138
+777,-298,807
+-625,-499,-773
+-651,446,630
+-650,-513,512
+561,641,405
+
+--- scanner 11 ---
+-277,605,-470
+569,553,-635
+548,613,483
+-405,-574,726
+-248,697,-547
+579,668,645
+450,-944,665
+493,-867,839
+77,-78,31
+-610,506,539
+-301,-619,654
+431,-463,-525
+-256,717,-571
+438,-438,-424
+-425,-410,-625
+-470,-555,704
+-480,-477,-778
+479,-541,-377
+-680,474,573
+543,566,640
+491,-860,658
+469,539,-594
+484,610,-530
+-726,662,543
+-545,-485,-661
+
+--- scanner 12 ---
+-671,538,406
+-504,-417,579
+588,613,-492
+538,579,-465
+706,-659,-613
+-80,-112,49
+-665,-581,-479
+-623,454,433
+-512,687,-475
+-526,702,-479
+739,478,781
+-682,-583,-625
+-488,559,475
+724,557,677
+-533,-418,468
+774,-649,-673
+-671,-502,-530
+657,505,736
+520,532,-480
+337,-509,343
+389,-528,415
+-531,840,-522
+327,-408,356
+711,-588,-526
+-497,-526,479
+
+--- scanner 13 ---
+347,-554,-848
+736,679,-606
+-768,-718,-534
+593,-688,575
+603,-681,459
+-888,-665,-419
+-798,681,-796
+580,654,-689
+385,-701,-885
+-759,660,-569
+-586,-690,351
+-782,722,-614
+-860,595,805
+-775,-732,403
+488,638,794
+581,617,672
+566,686,-568
+-819,460,785
+-813,-759,-528
+-653,-833,391
+647,-647,629
+440,-574,-952
+-103,-73,-96
+441,631,710
+-854,660,810
+
+--- scanner 14 ---
+508,747,792
+-423,439,460
+632,586,790
+-334,-589,852
+628,-492,-445
+-743,-292,-685
+-431,563,-813
+-296,-582,862
+576,576,839
+-14,-19,106
+523,-541,-531
+627,-720,637
+48,87,-35
+-609,-418,-674
+-377,-596,788
+537,-816,731
+469,406,-620
+-506,374,-780
+-560,-303,-711
+-343,437,413
+-317,344,529
+-486,515,-720
+567,-492,-491
+607,365,-561
+567,-688,723
+574,344,-623
+
+--- scanner 15 ---
+624,522,626
+-539,-442,-496
+794,478,592
+740,532,633
+124,2,6
+446,-877,-721
+-431,-565,817
+837,544,-672
+959,637,-693
+827,-495,840
+-556,-466,892
+-610,-381,-335
+-403,559,-741
+-720,740,646
+576,-890,-606
+-524,545,-709
+848,-440,637
+739,-455,751
+-787,685,519
+-354,-463,829
+-538,-408,-462
+875,684,-686
+477,-942,-607
+-441,389,-734
+-683,778,499
+
+--- scanner 16 ---
+-503,-550,528
+688,-760,424
+-696,511,-657
+-65,89,-87
+-586,-702,-495
+-660,366,-644
+-407,-460,434
+-645,-778,-472
+-693,-642,-395
+585,-422,-451
+622,839,292
+-535,-490,442
+-641,373,303
+576,839,504
+333,485,-750
+593,-753,253
+661,-391,-484
+-627,454,377
+660,899,490
+567,-767,425
+505,-414,-503
+-634,411,313
+-708,565,-606
+420,390,-737
+270,428,-706
+
+--- scanner 17 ---
+588,-461,-663
+424,413,-783
+621,785,311
+819,780,359
+421,681,-775
+-475,-548,-502
+128,-55,-99
+671,-335,-598
+-381,632,855
+464,592,-725
+-582,-549,-643
+-454,510,-602
+-383,427,-557
+29,23,43
+-423,605,862
+568,-414,-509
+-461,-808,374
+-557,597,856
+-470,334,-633
+429,-588,733
+436,-528,632
+-602,-631,-531
+-532,-768,459
+405,-540,507
+-482,-786,618
+693,719,424
+
+--- scanner 18 ---
+638,749,-613
+-305,-797,-544
+703,-545,-578
+752,-571,-698
+-316,551,-501
+-498,727,360
+-493,743,475
+621,-553,-748
+-438,644,-522
+-325,-756,-679
+-506,758,408
+-300,-791,-479
+-366,-666,668
+56,-48,95
+743,-436,379
+-302,-707,833
+635,663,-576
+791,421,805
+724,481,734
+-354,-672,738
+681,-491,468
+893,516,708
+746,-435,416
+-83,101,16
+-400,504,-508
+613,552,-643
+
+--- scanner 19 ---
+-710,556,-573
+733,-670,468
+749,663,-743
+536,434,623
+-236,-921,847
+690,525,-784
+512,-947,-253
+793,-680,400
+-223,-820,837
+-545,358,812
+-456,-803,-356
+-337,-727,-262
+46,-64,92
+-663,624,-402
+481,246,583
+646,-741,463
+506,254,652
+752,558,-805
+184,-9,-27
+465,-718,-244
+-295,-801,785
+-661,500,-563
+-534,500,842
+-552,551,815
+459,-874,-288
+-364,-672,-394
+
+--- scanner 20 ---
+611,807,-820
+483,-791,469
+507,-279,-620
+-390,903,473
+879,815,-817
+573,-392,-548
+-783,-396,756
+-753,-610,-604
+90,125,-32
+-750,-547,673
+-294,821,424
+-276,768,-686
+-330,878,-589
+700,757,-777
+679,-817,484
+-746,-482,819
+39,-12,105
+512,-327,-422
+511,537,804
+563,-764,410
+-677,-467,-589
+-779,-508,-493
+699,509,865
+-252,911,442
+-388,849,-756
+653,506,711
+
+--- scanner 21 ---
+394,873,505
+748,912,-413
+-616,-568,672
+-360,781,474
+795,809,-454
+511,865,570
+-26,115,-75
+640,-520,360
+-617,433,-896
+817,-799,-375
+782,-509,390
+-446,481,-839
+-393,-410,-424
+801,-682,-413
+-513,-524,572
+-421,798,503
+-473,810,385
+-320,-402,-495
+-335,-362,-444
+-530,593,-869
+760,-800,-551
+-641,-536,667
+99,14,-155
+547,940,450
+647,887,-406
+589,-502,387
+
+--- scanner 22 ---
+504,-335,-736
+681,749,-470
+-12,141,11
+469,800,467
+-586,627,-581
+-538,-667,-700
+559,-273,-706
+-458,-715,-541
+439,928,459
+534,-474,400
+621,642,-370
+-164,45,-51
+478,-464,351
+757,690,-447
+529,832,553
+544,-281,-663
+-394,694,328
+-415,-232,661
+-521,-327,730
+-475,708,402
+410,-635,398
+-387,675,-619
+-532,639,-632
+-441,-325,777
+-455,-710,-677
+-432,701,338
+
+--- scanner 23 ---
+345,-850,775
+-401,765,426
+-395,-540,528
+-366,287,-664
+-589,719,456
+786,-612,-947
+-453,-445,-647
+-524,-430,-711
+-497,-504,523
+403,-742,835
+613,625,-450
+-450,-509,366
+436,-837,764
+410,509,360
+372,695,429
+-510,-530,-752
+-557,649,422
+422,729,394
+-52,42,-80
+564,475,-398
+112,-12,33
+814,-822,-892
+564,652,-506
+-346,295,-688
+-458,316,-587
+783,-623,-917
+
+--- scanner 24 ---
+-784,-501,379
+326,-448,397
+-147,42,69
+-665,808,709
+375,-366,493
+-854,-420,491
+294,570,379
+-687,-391,433
+-838,311,-528
+-875,-512,-597
+-616,752,736
+472,547,-346
+458,506,-446
+-866,366,-738
+-915,-454,-776
+767,-760,-596
+406,671,400
+344,-358,355
+-616,860,559
+-918,-462,-508
+314,594,371
+-835,341,-539
+706,-732,-408
+401,611,-361
+613,-763,-550
+
+--- scanner 25 ---
+778,-682,-808
+-832,-786,-674
+703,-887,484
+-587,854,-765
+800,722,449
+-542,447,561
+72,-122,-75
+-624,-536,343
+848,800,597
+841,825,496
+879,-886,427
+786,396,-767
+-518,505,471
+-586,-452,349
+-823,-755,-671
+1,27,16
+785,-782,-699
+-540,449,382
+749,-793,-807
+841,-769,443
+-645,816,-621
+788,403,-586
+-676,-430,435
+829,319,-593
+-459,828,-682
+-867,-656,-574
+
+--- scanner 26 ---
+-447,435,685
+600,605,-597
+-736,-480,773
+-830,-402,708
+507,-609,576
+593,-646,573
+613,623,606
+593,700,513
+705,-721,-378
+-809,-749,-891
+-334,500,634
+-822,-634,-761
+-427,812,-510
+603,494,533
+-874,-635,-860
+-306,510,725
+-387,723,-598
+77,-13,-11
+612,-700,-500
+752,-714,-462
+590,598,-713
+-807,-445,729
+-372,609,-489
+704,-579,551
+546,564,-543
+
+--- scanner 27 ---
+775,-780,422
+682,-896,448
+-565,-662,754
+533,-519,-527
+-782,814,-434
+-872,-646,-527
+726,544,-537
+-847,684,586
+-662,739,-398
+734,587,-552
+-660,-650,626
+-83,-35,144
+372,-517,-403
+-729,672,534
+-845,-628,-476
+672,617,-497
+-560,-694,729
+543,-470,-471
+-146,-163,-12
+-727,747,-281
+297,558,462
+680,-849,528
+292,422,465
+340,581,545
+-758,655,473
+-842,-635,-669
+
+--- scanner 28 ---
+440,-491,816
+396,587,-713
+-152,115,188
+-969,734,-609
+352,832,875
+597,-662,-622
+-880,-620,-358
+-720,701,399
+703,-570,-686
+652,-667,-664
+-658,-229,461
+443,-518,902
+-869,627,-669
+-614,-292,518
+361,-573,748
+-54,95,-4
+-758,749,598
+-913,-544,-389
+300,830,722
+393,524,-733
+343,791,871
+-861,-464,-381
+-707,737,544
+400,632,-804
+-892,686,-745
+-627,-379,423
+
+--- scanner 29 ---
+-606,518,439
+550,-555,408
+-620,935,-493
+709,563,312
+529,-409,-886
+507,761,-791
+-602,830,-472
+-38,20,-55
+-529,907,-587
+-568,454,507
+-795,-555,755
+429,783,-863
+-695,-780,-752
+693,540,275
+499,-381,-900
+591,-651,306
+-803,-806,-873
+419,615,-823
+693,-540,332
+643,485,283
+-752,-836,-902
+-685,-458,809
+611,-298,-896
+-766,-388,697
+-671,591,517
+
+--- scanner 30 ---
+798,-374,-506
+-616,426,-665
+-634,399,-614
+376,-427,576
+695,-415,-459
+292,-386,583
+681,534,622
+751,609,-743
+-820,-466,797
+-945,404,706
+773,-367,-607
+-932,394,807
+369,-429,757
+662,469,644
+-913,-336,-437
+-709,-437,798
+-809,-430,689
+617,365,572
+826,489,-707
+-796,-374,-453
+759,544,-860
+-914,-512,-494
+-86,-83,17
+-23,67,-114
+-873,456,687
+-623,429,-472
+
+--- scanner 31 ---
+-666,817,-551
+528,850,-390
+292,-387,795
+-753,-658,341
+567,608,629
+-826,707,624
+550,754,631
+37,121,-88
+315,-338,-717
+-756,-659,378
+-706,872,-363
+408,924,-421
+-821,620,553
+356,-428,630
+-762,-523,-736
+295,-297,-582
+290,-303,-517
+431,843,-467
+-889,560,563
+-40,-22,14
+344,-422,700
+-631,-541,-786
+-637,847,-371
+556,703,710
+-691,-603,430
+-713,-549,-616
+
+--- scanner 32 ---
+-704,318,-798
+-521,315,-708
+-455,724,733
+19,-67,-121
+-447,708,533
+966,543,312
+885,557,386
+774,476,-597
+828,488,-648
+973,524,-635
+-374,682,612
+147,-16,9
+-497,-857,457
+-577,-822,495
+-576,-758,400
+945,-383,645
+839,-478,714
+-362,-758,-480
+902,-866,-557
+-592,245,-833
+919,-476,761
+-361,-896,-524
+822,-818,-716
+905,-861,-693
+928,550,322
+-415,-695,-511
+
+--- scanner 33 ---
+-580,-464,-646
+-109,8,-50
+-534,-655,474
+-667,-469,-717
+546,546,330
+-519,-637,521
+430,393,-715
+-465,568,454
+403,261,-660
+522,355,-584
+-727,-401,-707
+623,-451,499
+727,-436,420
+302,-848,-466
+20,-117,-182
+451,539,334
+-393,287,-513
+361,-786,-586
+-399,243,-669
+-406,439,407
+-546,-587,555
+-446,252,-440
+-378,592,398
+556,457,275
+289,-838,-567
+682,-518,447
diff --git a/2021/day19/main.rs b/2021/day19/main.rs
@@ -0,0 +1,220 @@
+use std::collections::{HashSet, VecDeque};
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+enum Axis {
+ X,
+ Y,
+ Z,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+struct Mapping {
+ axis: [Axis; 3],
+ flip: [bool; 3],
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+struct Pos([i32; 3]);
+
+impl Pos {
+ fn new(s: &str) -> Pos {
+ let coord = s
+ .split(",")
+ .map(|c| c.parse::<i32>().unwrap())
+ .collect::<Vec<_>>();
+ Pos([coord[0], coord[1], coord[2]])
+ }
+
+ fn remap(&self, mapping: Mapping) -> Self {
+ let mut coord = [0; 3];
+ for i in 0..3 {
+ match mapping.axis[i] {
+ Axis::X => {
+ coord[i] = self.0[0] * (if mapping.flip[i] { -1 } else { 1 });
+ }
+ Axis::Y => {
+ coord[i] = self.0[1] * (if mapping.flip[i] { -1 } else { 1 });
+ }
+ Axis::Z => {
+ coord[i] = self.0[2] * (if mapping.flip[i] { -1 } else { 1 });
+ }
+ }
+ }
+ Pos(coord)
+ }
+
+ fn project(&self, mapping: Mapping, src: Pos, dest: Pos) -> Self {
+ // remaps self, then applies projection same as from mapped(src) -> dest
+ let mapped_src = src.remap(mapping);
+ let mapped_self = self.remap(mapping);
+ Pos([
+ mapped_self.0[0] + (dest.0[0] - mapped_src.0[0]),
+ mapped_self.0[1] + (dest.0[1] - mapped_src.0[1]),
+ mapped_self.0[2] + (dest.0[2] - mapped_src.0[2]),
+ ])
+ }
+
+ fn dist(&self, other: &Pos) -> (i32, i32) {
+ (
+ (self.0[0] - other.0[0]).abs()
+ + (self.0[1] - other.0[1]).abs()
+ + (self.0[2] - other.0[2]).abs(),
+ (self.0[0] - other.0[0]).pow(2)
+ + (self.0[1] - other.0[1]).pow(2)
+ + (self.0[2] - other.0[2]).pow(2),
+ )
+ }
+}
+
+fn main() {
+ let scanner_data = {
+ let mut tmp = Vec::<Vec<Pos>>::new();
+ let mut curr_scanner = Vec::<Pos>::new();
+ for l in std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ {
+ if l == "" {
+ tmp.push(curr_scanner);
+ curr_scanner = Vec::new();
+ } else if !l.starts_with("--") {
+ curr_scanner.push(Pos::new(l));
+ }
+ }
+ tmp.push(curr_scanner);
+ tmp
+ };
+ // 425
+ let (count, scanner_coord) = part_1(&scanner_data);
+ println!("Part 1: {}", count);
+ // 13354
+ println!("Part 2: {}", part_2(&scanner_coord));
+}
+
+fn part_1(scanner_data: &Vec<Vec<Pos>>) -> (usize, Vec<Pos>) {
+ let all_mapping = {
+ let mut tmp = Vec::<Mapping>::new();
+ let basic = vec![
+ Mapping {
+ axis: [Axis::X, Axis::Y, Axis::Z],
+ flip: [false, false, false],
+ },
+ Mapping {
+ axis: [Axis::X, Axis::Y, Axis::Z],
+ flip: [true, false, true],
+ },
+ Mapping {
+ axis: [Axis::Y, Axis::X, Axis::Z],
+ flip: [false, true, false],
+ },
+ Mapping {
+ axis: [Axis::Y, Axis::X, Axis::Z],
+ flip: [true, false, false],
+ },
+ Mapping {
+ axis: [Axis::Z, Axis::Y, Axis::X],
+ flip: [false, false, true],
+ },
+ Mapping {
+ axis: [Axis::Z, Axis::Y, Axis::X],
+ flip: [true, false, false],
+ },
+ ];
+ for m in basic {
+ // generate all 4 rotations
+ tmp.push(m);
+ tmp.push(Mapping {
+ axis: [m.axis[0], m.axis[2], m.axis[1]],
+ flip: [m.flip[0], m.flip[2], !m.flip[1]],
+ });
+ tmp.push(Mapping {
+ axis: [m.axis[0], m.axis[1], m.axis[2]],
+ flip: [m.flip[0], !m.flip[1], !m.flip[2]],
+ });
+ tmp.push(Mapping {
+ axis: [m.axis[0], m.axis[2], m.axis[1]],
+ flip: [m.flip[0], !m.flip[2], m.flip[1]],
+ });
+ }
+ tmp
+ };
+
+ let mut scanner_coord = vec![None; scanner_data.len()];
+ scanner_coord[0] = Some(Pos([0, 0, 0]));
+ let mut all_beacons = HashSet::<Pos>::new();
+ for x in scanner_data[0].iter() {
+ all_beacons.insert(*x);
+ }
+ // remapped and transferred to scanner 0 format
+ let mut corrected_scanner_data = vec![None; scanner_data.len()];
+ corrected_scanner_data[0] = Some(scanner_data[0].clone());
+ let mut match_queue = VecDeque::new();
+ match_queue.push_back(0);
+ while let Some(to_match) = match_queue.pop_front() {
+ let ref_data = corrected_scanner_data[to_match].clone().unwrap();
+ for matched in 0..scanner_data.len() {
+ if corrected_scanner_data[matched].is_none() {
+ // see if we have more than 12 matching points
+ let mut matching_pairs = Vec::new();
+ for a in 0..ref_data.len() {
+ for b in 0..scanner_data[matched].len() {
+ let dist_a = ref_data
+ .iter()
+ .map(|x| ref_data[a].dist(x))
+ .collect::<HashSet<_>>();
+ let dist_b = scanner_data[matched]
+ .iter()
+ .map(|x| scanner_data[matched][b].dist(x))
+ .collect::<HashSet<_>>();
+ // measuring 12 points ensures unique identification (self + 11 others)
+ if dist_a.intersection(&dist_b).count() >= 12 {
+ matching_pairs.push((a, b));
+ }
+ }
+ }
+ // find right mapping by matching calculated scanner position
+ for mapping in all_mapping.iter() {
+ let possible_scanner_pos = matching_pairs
+ .iter()
+ .map(|&(a, b)| {
+ let a = ref_data[a];
+ let b = scanner_data[matched][b].remap(*mapping);
+ Pos([a.0[0] - b.0[0], a.0[1] - b.0[1], a.0[2] - b.0[2]])
+ })
+ .collect::<HashSet<_>>();
+ if possible_scanner_pos.len() == 1 {
+ scanner_coord[matched] = Some(*possible_scanner_pos.iter().next().unwrap());
+ match_queue.push_back(matched);
+ let mut corrected_data = Vec::new();
+ for x in scanner_data[matched].iter() {
+ let x = x.project(
+ *mapping,
+ scanner_coord[0].unwrap(),
+ scanner_coord[matched].unwrap(),
+ );
+ all_beacons.insert(x);
+ corrected_data.push(x);
+ }
+ corrected_scanner_data[matched] = Some(corrected_data);
+ break;
+ }
+ }
+ }
+ }
+ }
+ (
+ all_beacons.len(),
+ scanner_coord.into_iter().map(|x| x.unwrap()).collect(),
+ )
+}
+
+fn part_2(scanner_coord: &Vec<Pos>) -> i32 {
+ let mut max_mdist = 0;
+ for a in scanner_coord.iter() {
+ for b in scanner_coord.iter() {
+ max_mdist = max_mdist.max(a.dist(b).0);
+ }
+ }
+ max_mdist
+}