commit c0f55021a0fe9386bd827813a9181935c2293e63
parent 3dbffcd9e45cb9f629131725bf5ad2e3b2b8fb47
Author: Louis Burda <quent.burda@gmail.com>
Date: Sat, 15 Apr 2023 21:45:50 -0400
Add day 19 solution
Diffstat:
| A | src/19/Cargo.toml | | | 7 | +++++++ |
| A | src/19/input | | | 1057 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/19/part1 | | | 397 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/19/part2 | | | 11 | +++++++++++ |
| A | src/19/src/main.rs | | | 246 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/19/test1 | | | 10 | ++++++++++ |
| A | src/19/test2 | | | 41 | +++++++++++++++++++++++++++++++++++++++++ |
| A | src/19/test3 | | | 136 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
8 files changed, 1905 insertions(+), 0 deletions(-)
diff --git a/src/19/Cargo.toml b/src/19/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "day19"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../common/aoc" }
diff --git a/src/19/input b/src/19/input
@@ -0,0 +1,1057 @@
+--- scanner 0 ---
+-676,-433,-499
+496,-527,-542
+560,-496,-544
+-130,59,-171
+777,740,449
+-595,482,-515
+-462,376,-485
+446,-541,-444
+816,578,360
+693,-355,497
+-547,886,246
+783,-339,523
+-580,717,270
+537,724,-439
+585,738,-546
+693,-360,344
+780,596,356
+519,766,-677
+-758,-658,596
+-633,-661,463
+-604,-681,687
+-485,838,297
+-20,94,11
+-680,-565,-520
+-609,-430,-454
+-446,478,-577
+
+--- scanner 1 ---
+377,828,-479
+10,-83,131
+-61,70,6
+753,-464,827
+-692,-838,-494
+-486,726,689
+585,-439,837
+-696,-786,-313
+356,764,-472
+-763,-560,688
+579,376,423
+-854,-467,690
+-702,-868,-263
+756,-775,-429
+377,410,461
+-700,519,-495
+626,-747,-534
+-829,-450,771
+331,756,-377
+665,-746,-373
+584,335,465
+-527,570,-526
+479,-473,821
+-675,727,755
+-639,388,-521
+-627,838,722
+
+--- scanner 2 ---
+642,-368,607
+-472,-381,667
+-888,337,858
+-784,-648,-513
+602,854,701
+48,-36,-26
+-822,335,834
+-42,106,111
+685,-341,677
+455,689,-605
+-918,484,-528
+821,-485,-443
+479,717,-505
+-876,-543,-474
+-804,426,-472
+-662,482,-542
+780,-538,-394
+503,-313,632
+-544,-569,675
+-476,-530,793
+604,785,584
+508,769,724
+-921,-682,-568
+-854,463,785
+381,727,-551
+667,-545,-409
+
+--- scanner 3 ---
+614,-405,619
+-306,-511,766
+460,-384,665
+518,720,-558
+833,-619,-478
+529,734,632
+-418,758,621
+616,-599,-481
+-478,-837,-281
+-320,-428,683
+555,693,439
+736,-688,-402
+-630,562,-613
+3,77,84
+-305,773,614
+642,-350,722
+-445,-822,-317
+510,742,-525
+-292,-623,672
+-606,662,-641
+520,606,610
+-264,724,561
+-704,616,-651
+572,703,-676
+-542,-821,-341
+
+--- scanner 4 ---
+505,-678,285
+-469,-711,-721
+765,-709,-746
+-475,520,225
+15,-36,-79
+-569,659,270
+-500,-713,-657
+793,-578,-680
+-583,758,-756
+-403,-801,448
+-595,775,-514
+847,852,-493
+-530,554,362
+-538,-735,519
+-514,-811,-607
+179,106,-149
+-406,-756,515
+745,492,390
+751,-816,-698
+403,-770,301
+639,476,356
+471,486,381
+-612,766,-781
+640,848,-418
+645,890,-459
+509,-740,434
+
+--- scanner 5 ---
+668,735,724
+-867,783,567
+-906,-544,816
+563,806,825
+409,-872,677
+370,-539,-533
+-405,-561,-311
+592,766,618
+-509,778,-739
+-383,682,-816
+-470,-436,-372
+362,-776,567
+607,618,-692
+-909,779,533
+597,729,-812
+-888,794,719
+-917,-605,613
+-912,-733,757
+-552,-553,-290
+-86,-72,41
+642,556,-745
+487,-663,-485
+-559,717,-730
+501,-788,569
+370,-695,-476
+
+--- scanner 6 ---
+-782,-545,375
+-34,191,-34
+562,-760,577
+679,-768,412
+541,845,-631
+-926,533,603
+650,-736,478
+317,-756,-621
+-105,18,-135
+-835,992,-471
+-908,503,560
+-702,-559,544
+447,491,471
+-849,490,601
+-786,864,-439
+471,901,-489
+-859,990,-405
+280,-675,-697
+-519,-366,-802
+-495,-225,-744
+527,843,-375
+446,482,595
+-505,-228,-802
+563,438,498
+-749,-488,391
+477,-661,-657
+
+--- scanner 7 ---
+-366,-597,586
+-409,-721,560
+609,-623,-569
+851,613,-765
+743,-654,717
+-356,537,-649
+744,-484,645
+569,-539,-504
+1,-128,77
+-321,755,292
+95,-2,-28
+-411,-889,-670
+650,-545,760
+461,732,754
+760,459,-742
+410,670,802
+-413,771,394
+-486,-840,-542
+608,-466,-595
+-351,622,398
+627,584,-745
+-290,608,-514
+434,637,633
+-458,-694,565
+-335,541,-517
+-318,-893,-552
+
+--- scanner 8 ---
+567,-628,-719
+687,755,-587
+-524,741,318
+512,-349,572
+606,-434,549
+851,554,626
+-519,-699,-774
+-524,-813,-600
+730,573,596
+808,673,-560
+-465,475,-710
+-402,422,-687
+439,-565,-793
+-658,795,390
+-770,-619,512
+-821,-540,441
+-525,-834,-825
+510,-418,689
+-729,-696,483
+737,518,736
+30,112,-34
+-102,-56,36
+-712,797,354
+806,650,-644
+382,-628,-672
+-617,439,-655
+
+--- scanner 9 ---
+-304,561,846
+720,938,762
+631,-649,-565
+623,-492,724
+602,934,669
+-296,566,732
+-638,-455,383
+-643,-457,438
+0,49,-22
+592,-741,-670
+-675,-341,-683
+730,885,594
+-549,-337,-832
+527,802,-668
+-669,-653,369
+755,-496,745
+758,-563,790
+-514,638,-900
+561,956,-728
+686,-786,-531
+-489,777,-845
+-557,-409,-644
+-312,484,757
+512,915,-675
+-559,820,-872
+
+--- scanner 10 ---
+739,-755,-453
+101,-126,158
+821,497,-816
+863,502,-775
+-596,-592,819
+793,-765,485
+693,401,655
+-506,-614,914
+-838,-657,-627
+736,482,575
+627,420,457
+-745,413,933
+884,-687,509
+748,-738,-720
+-738,-612,-513
+-736,622,-488
+731,-726,-478
+714,-615,525
+-843,608,-536
+-605,650,-554
+-730,319,944
+-807,261,920
+825,704,-741
+-740,-643,-577
+16,-44,21
+-464,-457,823
+
+--- scanner 11 ---
+-588,507,-880
+-423,-345,577
+-600,309,552
+526,-515,-421
+474,672,264
+580,711,304
+-435,531,-812
+-66,-110,-161
+647,404,-543
+480,330,-506
+-765,-596,-817
+513,-679,-486
+594,-865,485
+-589,-344,671
+-742,-644,-870
+-543,567,-791
+-675,-538,-786
+574,-834,461
+-518,430,525
+656,-602,-423
+45,-55,-18
+617,690,360
+-623,311,468
+-582,-359,497
+580,-628,530
+542,402,-515
+
+--- scanner 12 ---
+-550,-616,376
+457,-816,717
+594,-638,-771
+-557,-642,301
+-558,514,384
+649,-611,-764
+695,-771,-745
+-622,545,386
+653,-790,648
+-2,-95,-168
+-755,681,-502
+655,-785,703
+542,360,-845
+-508,500,286
+-421,-607,412
+-643,-562,-717
+-702,-589,-727
+99,-133,4
+-630,-718,-821
+-845,702,-681
+-755,686,-655
+618,476,362
+696,383,-754
+614,608,341
+547,611,296
+571,380,-621
+
+--- scanner 13 ---
+542,-821,-720
+857,-452,668
+-508,603,651
+-271,812,-483
+434,-751,-706
+626,-768,-768
+-377,872,-453
+-275,797,-538
+867,857,-654
+-276,-790,-658
+820,845,-517
+555,701,726
+-7,-86,10
+-325,-303,307
+-258,-760,-701
+941,-518,560
+927,-376,571
+-335,-803,-699
+828,884,-544
+-398,-429,341
+672,745,655
+-516,415,723
+-349,-301,373
+181,96,-72
+-390,564,719
+755,647,734
+
+--- scanner 14 ---
+968,-689,515
+470,615,372
+636,521,371
+-603,-581,503
+971,-699,573
+-533,662,655
+747,-516,-360
+139,-18,17
+-527,731,861
+830,-675,515
+629,695,386
+69,165,149
+565,667,-403
+-533,888,-684
+670,724,-284
+802,-656,-353
+-547,707,892
+-427,928,-645
+-780,-492,-422
+766,-546,-239
+-798,-528,486
+-776,-612,-251
+-570,832,-663
+-795,-585,-497
+647,640,-282
+-611,-488,447
+
+--- scanner 15 ---
+583,713,-552
+458,547,852
+655,-492,680
+368,573,868
+656,-409,-476
+705,-394,666
+-383,-790,-509
+-560,346,-311
+570,609,-396
+591,-494,711
+792,-520,-441
+663,-484,-450
+-417,460,580
+-384,415,749
+-390,-667,-540
+-61,-112,54
+511,619,-423
+-692,383,-315
+-298,367,661
+458,394,847
+-548,270,-278
+-741,-636,731
+-836,-726,709
+46,61,104
+-425,-619,-517
+-745,-768,866
+
+--- scanner 16 ---
+-582,-327,-846
+905,876,813
+-483,-630,605
+574,810,-769
+797,-760,688
+612,840,-757
+609,-433,-734
+720,-765,748
+-723,624,-933
+-735,-332,-846
+-833,914,394
+-809,745,427
+792,-762,584
+-616,-633,480
+-630,768,-930
+-719,606,-969
+548,-556,-638
+-556,-311,-936
+-392,-653,451
+667,-508,-621
+833,911,802
+-782,866,332
+899,791,751
+69,129,-154
+437,751,-791
+
+--- scanner 17 ---
+843,599,405
+-809,-488,331
+-854,650,-358
+-808,623,-434
+748,644,496
+607,-468,-847
+534,-221,443
+-440,-717,-526
+-683,584,-400
+584,-642,-902
+515,789,-735
+-864,-278,324
+-129,4,-41
+-806,-289,267
+-732,597,390
+568,-291,509
+-457,-620,-638
+604,-414,-919
+-715,500,498
+773,612,394
+593,924,-781
+13,97,37
+592,-219,308
+622,808,-782
+-744,588,578
+-374,-728,-714
+
+--- scanner 18 ---
+758,-562,-685
+-531,-794,741
+127,9,-157
+-394,339,-708
+-352,306,-715
+-690,713,531
+-539,-941,720
+667,602,472
+-51,-48,-1
+704,-963,215
+830,258,-876
+746,405,-863
+-801,636,474
+-414,-876,659
+-537,-922,-485
+628,-536,-584
+739,-787,301
+674,-431,-657
+636,551,645
+876,443,-864
+641,733,533
+-735,-849,-497
+-820,682,627
+24,-189,-93
+-547,-849,-398
+800,-837,292
+-281,318,-677
+
+--- scanner 19 ---
+-564,-230,433
+555,837,-898
+401,705,759
+891,-476,341
+561,669,664
+588,-446,-607
+-618,-569,-470
+-501,-571,-539
+49,126,-174
+823,-548,353
+-641,-475,-555
+-24,-23,-90
+-454,-344,397
+611,951,-840
+634,-348,-597
+-775,921,-987
+-702,887,-861
+733,-402,391
+-435,524,369
+-594,-351,452
+-421,524,231
+625,695,-842
+688,-422,-635
+-751,855,-989
+364,629,678
+-411,582,228
+
+--- scanner 20 ---
+693,516,-782
+659,450,-852
+-321,-542,711
+-249,-707,-345
+-312,-541,587
+906,-745,704
+732,-840,-605
+-363,831,579
+-315,-519,-356
+729,-912,-659
+-332,-631,-453
+27,-37,79
+717,315,-854
+162,-117,-23
+658,654,791
+-681,274,-784
+-268,-658,684
+-739,331,-795
+-320,754,581
+729,607,638
+-684,338,-585
+-333,813,622
+709,-895,-431
+930,-657,605
+715,687,807
+938,-774,770
+
+--- scanner 21 ---
+-791,-706,-625
+552,-348,697
+436,438,-576
+-49,86,132
+484,716,550
+658,-377,-702
+411,446,-671
+518,583,461
+-877,-882,-590
+-372,-860,653
+-433,-795,528
+-351,-713,645
+113,-28,35
+475,731,403
+755,-359,636
+-618,717,915
+506,-398,-691
+-559,814,-527
+-447,632,-522
+457,374,-569
+-561,794,804
+-620,683,-553
+472,-356,-687
+696,-353,825
+-465,763,934
+-800,-756,-686
+
+--- scanner 22 ---
+485,-687,713
+-601,613,888
+847,-748,-334
+-509,-449,-668
+-828,645,-417
+-742,-526,814
+-649,580,777
+779,508,-414
+-803,564,-400
+505,514,-423
+611,498,-389
+499,-794,665
+-462,-378,-682
+610,870,385
+-737,647,-510
+-33,148,157
+-51,-18,1
+605,912,426
+-731,-716,724
+745,-656,-318
+-834,-606,774
+403,874,460
+457,-556,647
+-460,646,776
+741,-718,-467
+-434,-434,-772
+
+--- scanner 23 ---
+452,-737,702
+-410,-410,-834
+638,-813,694
+760,826,-627
+-399,-316,-819
+345,440,471
+-834,690,795
+-524,595,-685
+753,616,-684
+527,-713,714
+401,-344,-824
+323,521,316
+358,-348,-867
+693,717,-611
+-818,618,625
+-858,768,704
+-520,460,-553
+474,-385,-885
+-688,-398,604
+-886,-417,538
+3,-42,-9
+-423,-258,-896
+-429,617,-595
+-95,67,-127
+456,472,432
+-768,-479,647
+
+--- scanner 24 ---
+780,697,-379
+936,663,567
+497,-664,-506
+-464,-736,630
+-765,519,741
+-778,577,-655
+-764,671,-543
+799,629,622
+12,-75,97
+133,15,-41
+819,-445,663
+-806,466,692
+-366,-746,584
+498,-503,-467
+-592,-376,-869
+805,707,-547
+677,-501,593
+771,691,-653
+933,-503,607
+-750,588,-460
+-625,-412,-854
+-652,526,726
+469,-559,-376
+-440,-708,530
+-528,-436,-853
+891,524,661
+
+--- scanner 25 ---
+804,592,-664
+822,-814,411
+-789,574,563
+914,-678,-907
+904,-751,-936
+798,-905,489
+-492,-542,707
+-422,-442,-890
+-359,-426,658
+393,485,562
+-381,-581,739
+-376,-428,-831
+484,443,719
+82,46,-146
+-507,484,-631
+900,-700,-781
+839,544,-687
+782,-735,561
+-579,445,-481
+-445,-331,-852
+488,575,584
+-476,372,-496
+-729,501,462
+846,421,-656
+24,-44,11
+-796,517,353
+
+--- scanner 26 ---
+-634,-479,591
+-674,-465,394
+-51,-67,55
+435,-372,793
+398,-595,-668
+690,666,621
+-598,-384,431
+501,-404,764
+-721,-915,-381
+803,722,496
+414,-652,-635
+-597,576,487
+588,624,-406
+609,602,-366
+567,-581,-588
+-791,659,-499
+-847,667,-592
+600,-380,676
+734,630,526
+-779,-774,-405
+-808,854,-552
+-555,457,529
+-779,-912,-391
+-578,608,616
+610,664,-256
+
+--- scanner 27 ---
+819,557,797
+748,-478,-469
+-454,-688,-549
+747,-648,-397
+-616,427,534
+654,-539,-354
+846,-866,615
+-687,413,487
+-317,761,-822
+-456,-826,816
+156,-21,133
+831,632,950
+-405,-715,-554
+-610,-822,839
+-362,-591,-528
+-409,777,-720
+-631,323,459
+101,-136,-28
+-601,-885,888
+465,738,-360
+438,643,-481
+923,-763,658
+-347,628,-716
+827,-779,589
+414,676,-312
+870,636,721
+
+--- scanner 28 ---
+-678,642,-686
+-127,-37,-154
+-830,712,557
+375,-599,421
+-947,-520,-719
+722,788,-846
+504,-353,-854
+-441,656,-731
+-962,-527,-545
+-886,720,464
+-961,-361,-639
+711,864,-765
+-472,636,-755
+-847,907,504
+359,-542,388
+-21,41,-7
+-818,-859,665
+527,-571,-898
+637,888,-813
+531,-444,-927
+570,655,690
+528,-528,468
+-760,-862,675
+549,677,650
+571,717,800
+-818,-721,651
+
+--- scanner 29 ---
+-603,-822,-896
+-601,-865,-819
+-385,750,-883
+821,353,-638
+471,-363,-805
+405,-365,-829
+-595,-873,476
+-498,-917,593
+-560,-852,-878
+375,-512,557
+-609,416,489
+509,620,542
+631,-510,571
+-440,735,-879
+372,654,597
+489,-454,501
+-367,399,477
+417,515,503
+-355,810,-777
+439,-491,-756
+-471,-864,477
+817,502,-764
+-634,408,460
+-24,-33,-23
+749,541,-646
+
+--- scanner 30 ---
+-299,646,541
+668,-881,662
+419,314,-781
+-464,674,-679
+-436,612,596
+-766,-576,-402
+385,276,-579
+76,-162,-38
+544,-872,661
+344,318,-574
+440,391,661
+-737,-520,-493
+837,-626,-781
+773,-619,-802
+682,408,649
+-430,690,-573
+-455,680,-405
+-14,6,-88
+-344,507,635
+571,-925,545
+765,-524,-827
+-738,-681,-532
+-416,-462,637
+-558,-518,567
+-302,-520,581
+707,400,678
+
+--- scanner 31 ---
+402,-411,-885
+571,-444,-861
+525,-768,847
+710,952,-771
+565,774,385
+-427,561,-864
+-431,-739,521
+-707,-530,-480
+-519,-692,601
+476,740,560
+405,-819,781
+450,-349,-834
+506,752,522
+-355,840,543
+-421,-807,621
+692,916,-775
+-860,-455,-468
+-378,680,-740
+-379,948,646
+-444,918,608
+-631,-451,-429
+-9,131,71
+-475,672,-896
+440,-830,853
+548,913,-682
+
+--- scanner 32 ---
+628,746,783
+-588,884,-667
+694,-818,344
+792,815,-799
+-549,-686,614
+-631,-324,-895
+-654,-387,-842
+622,-679,300
+652,808,-744
+446,-580,-522
+-531,765,-562
+410,-634,-520
+5,6,-88
+721,671,798
+374,-446,-576
+-574,-656,447
+-680,-693,481
+-792,523,430
+748,917,779
+-696,505,573
+-504,886,-644
+-599,-539,-878
+-752,484,536
+736,-657,263
+682,929,-763
+
+--- scanner 33 ---
+-714,-643,-399
+701,-594,474
+403,722,-579
+-723,-658,-252
+17,40,109
+586,-488,-777
+-692,471,842
+-762,-365,727
+-502,426,-674
+331,776,-576
+72,173,-14
+-443,432,-485
+-646,421,-546
+702,-470,465
+724,473,468
+498,-587,-753
+-787,-373,822
+585,-567,421
+-540,450,853
+-680,-510,-310
+612,570,485
+-726,429,838
+348,548,-556
+469,-653,-785
+-741,-301,720
+536,462,402
+
+--- scanner 34 ---
+-506,776,673
+-395,600,-245
+-790,-450,589
+-564,-590,-510
+-433,825,733
+-770,-659,-516
+561,-654,583
+462,431,537
+588,657,-248
+-753,-421,694
+-801,-635,-496
+513,564,-263
+342,684,-267
+503,399,494
+-356,560,-432
+-412,653,-440
+35,-10,-12
+517,-575,507
+-802,-305,706
+736,-856,-616
+-44,82,161
+460,381,594
+754,-760,-473
+488,-699,544
+775,-816,-510
+-372,837,735
+
+--- scanner 35 ---
+515,-353,714
+573,333,-663
+480,389,-655
+362,459,919
+372,401,916
+-548,625,-453
+-870,-726,-557
+476,-611,-847
+-857,-757,-810
+-940,-599,806
+-872,-671,794
+-128,37,-25
+449,-365,-828
+-3,-119,58
+-635,602,-604
+-610,546,483
+569,-536,-832
+386,401,778
+-824,-790,-682
+545,-474,695
+-450,582,388
+-782,-525,756
+-506,583,-572
+405,-467,750
+533,372,-850
+-413,506,469
+
+--- scanner 36 ---
+-613,-749,-610
+690,735,796
+716,-829,-557
+690,659,864
+-417,485,-398
+576,-845,-461
+-32,-38,111
+599,308,-423
+-451,425,-244
+-482,303,575
+824,-723,870
+-472,-812,592
+-402,478,-285
+-513,-777,-586
+77,-184,194
+-433,-661,530
+693,-914,-463
+640,698,925
+782,-567,778
+669,281,-380
+753,-644,819
+624,253,-562
+-441,496,549
+-455,-694,538
+-559,-787,-684
+-569,474,540
+
+--- scanner 37 ---
+920,-438,557
+749,-774,-709
+917,-749,-699
+-665,-763,-643
+54,-105,21
+-690,-746,-562
+-528,-375,622
+-673,413,702
+790,-466,662
+836,781,-590
+-714,401,755
+-599,-653,-560
+-765,450,706
+13,64,113
+-243,718,-539
+-372,646,-473
+643,-740,-693
+641,809,-579
+-532,-427,441
+443,559,434
+753,795,-673
+-425,801,-511
+427,623,374
+442,656,410
+-538,-345,391
+829,-467,501
+
diff --git a/src/19/part1 b/src/19/part1
@@ -0,0 +1,397 @@
+--- Day 19: Beacon Scanner ---
+
+As your probe drifted down through this area, it released an assortment of [1m[97mbeacons[0m and
+[1m[97mscanners[0m into the water. It's difficult to navigate in the pitch black open waters of the ocean
+trench, but if you can build a map of the trench using data from the scanners, you should be able to
+safely reach the bottom.
+
+The beacons and scanners float motionless in the water; they're designed to maintain the same
+position for long periods of time. Each scanner is capable of detecting all beacons in a large cube
+centered on the scanner; beacons that are at most 1000 units away from the scanner in each of the
+three axes (x, y, and z) have their precise position determined relative to the scanner. However,
+scanners cannot detect other scanners. The submarine has automatically summarized the relative
+positions of beacons detected by each scanner (your puzzle input).
+
+For example, if a scanner is at x,y,z coordinates 500,0,-500 and there are beacons at
+-500,1000,-1500 and 1501,0,-500, the scanner could report that the first beacon is at
+-1000,1000,-1000 (relative to the scanner) but would not detect the second beacon at all.
+
+Unfortunately, while each scanner can report the positions of all detected beacons relative to
+itself, [1m[97mthe scanners do not know their own position[0m. You'll need to determine the positions of the
+beacons and scanners yourself.
+
+The scanners and beacons map a single contiguous 3d region. This region can be reconstructed by
+finding pairs of scanners that have overlapping detection regions such that there are [1m[97mat least 12
+beacons[0m that both scanners detect within the overlap. By establishing 12 common beacons, you can
+precisely determine where the scanners are relative to each other, allowing you to reconstruct the
+beacon map one scanner at a time.
+
+For a moment, consider only two dimensions. Suppose you have the following scanner reports:
+
+--- scanner 0 ---
+0,2
+4,1
+3,3
+
+--- scanner 1 ---
+-1,-1
+-5,0
+-2,1
+
+Drawing x increasing rightward, y increasing upward, scanners as S, and beacons as B, scanner 0
+detects this:
+
+...B.
+B....
+....B
+S....
+
+Scanner 1 detects this:
+
+...B..
+B....S
+....B.
+
+For this example, assume scanners only need 3 overlapping beacons. Then, the beacons visible to both
+scanners overlap to produce the following complete map:
+
+...B..
+B....S
+....B.
+S.....
+
+Unfortunately, there's a second problem: the scanners also don't know their [1m[97mrotation or facing
+direction[0m. Due to magnetic alignment, each scanner is rotated some integer number of 90-degree turns
+around all of the x, y, and z axes. That is, one scanner might call a direction positive x, while
+another scanner might call that direction negative y. Or, two scanners might agree on which
+direction is positive x, but one scanner might be upside-down from the perspective of the other
+scanner. In total, each scanner could be in any of 24 different orientations: facing positive or
+negative x, y, or z, and considering any of four directions "up" from that facing.
+
+For example, here is an arrangement of beacons as seen from a scanner in the same position but in
+different orientations:
+
+--- scanner 0 ---
+-1,-1,1
+-2,-2,2
+-3,-3,3
+-2,-3,1
+5,6,-4
+8,0,7
+
+--- scanner 0 ---
+1,-1,1
+2,-2,2
+3,-3,3
+2,-1,3
+-5,4,-6
+-8,-7,0
+
+--- scanner 0 ---
+-1,-1,-1
+-2,-2,-2
+-3,-3,-3
+-1,-3,-2
+4,6,5
+-7,0,8
+
+--- scanner 0 ---
+1,1,-1
+2,2,-2
+3,3,-3
+1,3,-2
+-4,-6,5
+7,0,8
+
+--- scanner 0 ---
+1,1,1
+2,2,2
+3,3,3
+3,1,2
+-6,-4,-5
+0,7,-8
+
+By finding pairs of scanners that both see at least 12 of the same beacons, you can assemble the
+entire map. For example, consider the following report:
+
+--- 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
+
+Because all coordinates are relative, in this example, all "absolute" positions will be expressed
+relative to scanner 0 (using the orientation of scanner 0 and as if scanner 0 is at coordinates
+0,0,0).
+
+Scanners 0 and 1 have overlapping detection cubes; the 12 beacons they both detect (relative to
+scanner 0) are at the following coordinates:
+
+-618,-824,-621
+-537,-823,-458
+-447,-329,318
+404,-588,-901
+544,-627,-890
+528,-643,409
+-661,-816,-575
+390,-675,-793
+423,-701,434
+-345,-311,381
+459,-707,401
+-485,-357,347
+
+These same 12 beacons (in the same order) but from the perspective of scanner 1 are:
+
+686,422,578
+605,423,415
+515,917,-361
+-336,658,858
+-476,619,847
+-460,603,-452
+729,430,532
+-322,571,750
+-355,545,-477
+413,935,-424
+-391,539,-444
+553,889,-390
+
+Because of this, scanner 1 must be at 68,-1246,-43 (relative to scanner 0).
+
+Scanner 4 overlaps with scanner 1; the 12 beacons they both detect (relative to scanner 0) are:
+
+459,-707,401
+-739,-1745,668
+-485,-357,347
+432,-2009,850
+528,-643,409
+423,-701,434
+-345,-311,381
+408,-1815,803
+534,-1912,768
+-687,-1600,576
+-447,-329,318
+-635,-1737,486
+
+So, scanner 4 is at -20,-1133,1061 (relative to scanner 0).
+
+Following this process, scanner 2 must be at 1105,-1205,1229 (relative to scanner 0) and scanner 3
+must be at -92,-2380,-20 (relative to scanner 0).
+
+The full list of beacons (relative to scanner 0) is:
+
+-892,524,684
+-876,649,763
+-838,591,734
+-789,900,-551
+-739,-1745,668
+-706,-3180,-659
+-697,-3072,-689
+-689,845,-530
+-687,-1600,576
+-661,-816,-575
+-654,-3158,-753
+-635,-1737,486
+-631,-672,1502
+-624,-1620,1868
+-620,-3212,371
+-618,-824,-621
+-612,-1695,1788
+-601,-1648,-643
+-584,868,-557
+-537,-823,-458
+-532,-1715,1894
+-518,-1681,-600
+-499,-1607,-770
+-485,-357,347
+-470,-3283,303
+-456,-621,1527
+-447,-329,318
+-430,-3130,366
+-413,-627,1469
+-345,-311,381
+-36,-1284,1171
+-27,-1108,-65
+7,-33,-71
+12,-2351,-103
+26,-1119,1091
+346,-2985,342
+366,-3059,397
+377,-2827,367
+390,-675,-793
+396,-1931,-563
+404,-588,-901
+408,-1815,803
+423,-701,434
+432,-2009,850
+443,580,662
+455,729,728
+456,-540,1869
+459,-707,401
+465,-695,1988
+474,580,667
+496,-1584,1900
+497,-1838,-617
+527,-524,1933
+528,-643,409
+534,-1912,768
+544,-627,-890
+553,345,-567
+564,392,-477
+568,-2007,-577
+605,-1665,1952
+612,-1593,1893
+630,319,-379
+686,-3108,-505
+776,-3184,-501
+846,-3110,-434
+1135,-1161,1235
+1243,-1093,1063
+1660,-552,429
+1693,-557,386
+1735,-437,1738
+1749,-1800,1813
+1772,-405,1572
+1776,-675,371
+1779,-442,1789
+1780,-1548,337
+1786,-1538,337
+1847,-1591,415
+1889,-1729,1762
+1994,-1805,1792
+
+In total, there are [1m[97m79[0m beacons.
+
+Assemble the full map of beacons. [1m[97mHow many beacons are there?[0m
+
+
diff --git a/src/19/part2 b/src/19/part2
@@ -0,0 +1,11 @@
+--- Part Two ---
+
+Sometimes, it's a good idea to appreciate just how big the ocean is. Using the Manhattan distance,
+how far apart do the scanners get?
+
+In the above example, scanners 2 (1105,-1205,1229) and 3 (-92,-2380,-20) are the largest Manhattan
+distance apart. In total, they are 1197 + 1175 + 1249 = [1m[97m3621[0m units apart.
+
+[1m[97mWhat is the largest Manhattan distance between any two scanners?[0m
+
+
diff --git a/src/19/src/main.rs b/src/19/src/main.rs
@@ -0,0 +1,246 @@
+use std::collections::{HashSet,HashMap};
+
+#[derive(PartialEq,Eq,Hash,Clone)]
+struct Pos {
+ x: isize,
+ y: isize,
+ z: isize
+}
+
+impl Pos {
+ fn add(&self, other: &Pos) -> Pos {
+ Pos { x: self.x + other.x, y: self.y + other.y, z: self.z + other.z }
+ }
+
+ fn sub(&self, other: &Pos) -> Pos {
+ Pos { x: self.x - other.x, y: self.y - other.y, z: self.z - other.z }
+ }
+
+ fn face_z(&self, i: usize) -> Pos {
+ match i {
+ 0 => Pos { x: self.x, y: self.y, z: self.z },
+ 1 => Pos { x: self.x, y: -self.z, z: self.y },
+ 2 => Pos { x: self.x, y: -self.y, z: -self.z },
+ 3 => Pos { x: self.x, y: self.z, z: -self.y },
+ 4 => Pos { x: -self.z, y: self.y, z: self.x },
+ 5 => Pos { x: self.z, y: self.y, z: -self.x },
+ _ => unreachable!()
+ }
+ }
+
+ fn rot_z(&self, i: usize) -> Pos {
+ match i {
+ 0 => Pos { x: self.x, y: self.y, z: self.z },
+ 1 => Pos { x: self.y, y: -self.x, z: self.z },
+ 2 => Pos { x: -self.x, y: -self.y, z: self.z },
+ 3 => Pos { x: -self.y, y: self.x, z: self.z },
+ _ => unreachable!()
+ }
+ }
+
+ fn rot(&self, r: usize) -> Pos {
+ return self.face_z(r % 6).rot_z(r / 6);
+ }
+
+ fn abs(&self) -> usize {
+ return (self.x.abs() + self.y.abs() + self.z.abs()) as usize;
+ }
+}
+
+impl std::fmt::Display for Pos {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "V({}, {}, {})", self.x, self.y, self.z)
+ }
+}
+
+fn parse_scanners(input: &str) -> Vec<Vec<Pos>> {
+ let mut scanners: Vec<Vec<Pos>> = Vec::new();
+
+ for l in input.lines() {
+ if l.contains("scanner") {
+ scanners.push(Vec::new());
+ } else {
+ if l.is_empty() { continue; }
+ let last = scanners.last_mut().unwrap();
+ let vals: Vec<isize> = l.split(",").map(|v| v.parse().unwrap()).collect();
+ last.push(Pos { x: vals[0], y: vals[1], z: vals[2] });
+ }
+ }
+
+ return scanners;
+}
+
+fn gen_edges(pos: &Vec<Pos>) -> HashMap<Pos,Vec<(usize,usize)>> {
+ let mut edges: HashMap<Pos,Vec<(usize,usize)>> = HashMap::new();
+
+ for (i1,p1) in pos.iter().enumerate() {
+ for (i2,p2) in pos.iter().enumerate() {
+ if i1 == i2 { continue; }
+ let diff = p1.sub(p2);
+ let res = edges.get_mut(&diff);
+ if res.is_some() {
+ res.unwrap().push((i1, i2));
+ } else {
+ edges.insert(diff, vec![(i1, i2)]);
+ }
+ }
+ }
+
+ return edges;
+}
+
+fn calc_remote_offset(remote_nodes: &Vec<Pos>, local_nodes: &Vec<Pos>,
+ remote_clique: &Vec<usize>, local_edges: &HashMap<Pos,Vec<(usize,usize)>>) -> Pos {
+ /* find an edge in the clique that has exactly one candidate on the
+ * local side (should exist if the whole clique is not available twice)
+ * and use that to correlate two points and calculate the offset of
+ * the remote scanner from the local one in local reference frame */
+ for &i1 in remote_clique {
+ for &i2 in remote_clique {
+ if i1 == i2 { continue; }
+ let diff = remote_nodes[i1].sub(&remote_nodes[i2]);
+ let res = local_edges.get(&diff);
+ if res.is_none() { continue; }
+ let cands = res.unwrap();
+ if cands.len() == 1 {
+ let (o1,_) = cands[0];
+ let remote_node = &remote_nodes[i1];
+ let local_node = &local_nodes[o1];
+ return local_node.sub(remote_node);
+ }
+ }
+ }
+ unreachable!();
+}
+
+fn get_overlap_nodes(id: usize, remote_nodes: &Vec<Pos>, local_nodes: &Vec<Pos>,
+ local_edges: &HashMap<Pos,Vec<(usize,usize)>>) -> Option<(Vec<Pos>,Pos)> {
+ aoc::debugln!("== scanner {} == ", id);
+
+ let minclique = 12; /* 3 for test1, 6 for test2 */
+ for r in 0..24 {
+ let remote_rot = remote_nodes.iter().map(|p| p.rot(r)).collect();
+ let remote_edges = gen_edges(&remote_rot);
+
+ aoc::debugln!("> ROT {}", r);
+
+ let mut adjs: Vec<HashSet<usize>> = Vec::new();
+ for _ in remote_nodes { adjs.push(HashSet::new()); }
+ for (diff,edges) in &remote_edges {
+ if local_edges.get(diff).is_none() { continue; }
+ aoc::debug!("EDGE {}", diff);
+ for &(u1,u2) in edges {
+ aoc::debug!(" {},{}", u1, u2);
+ adjs[u1].insert(u2);
+ adjs[u2].insert(u1);
+ }
+ aoc::debugln!("");
+ }
+
+ let mut clique: Vec<usize> = Vec::new();
+ for (u1,adj) in adjs.iter().enumerate() {
+ clique.clear();
+ clique.append(&mut adj.iter().map(|&x| x).collect());
+ clique.push(u1);
+ for &u2 in adj {
+ if clique.len() < minclique { break; }
+ clique = clique.iter().filter(|u| adjs[u2].contains(u))
+ .map(|u| *u).collect();
+ clique.push(u2);
+ }
+ if clique.len() >= minclique { break; }
+ }
+
+ aoc::debugln!("clique len {}", clique.len());
+ for &node in &clique {
+ aoc::debugln!("{}", remote_nodes[node]);
+ }
+
+ if clique.len() >= minclique {
+ let remote_offset = calc_remote_offset(&remote_rot,
+ &local_nodes, &clique, &local_edges);
+ aoc::debugln!("offset {}", remote_offset);
+ let remote_nodes_corrected: Vec<Pos>
+ = remote_rot.iter().map(|p| p.add(&remote_offset))
+ .filter(|p| !local_nodes.contains(p)).collect();
+ aoc::debugln!("\nbeacons {}\n", local_nodes.len());
+ return Some((remote_nodes_corrected, remote_offset));
+ }
+ }
+
+ return None;
+}
+
+fn part1(aoc: &mut aoc::Info) {
+ let mut scanners = parse_scanners(&aoc.input);
+
+ let mut beacon_nodes: Vec<Pos> = Vec::new();
+ beacon_nodes.append(&mut scanners.remove(0));
+
+ while !scanners.is_empty() {
+ aoc::debugln!("\n== ADDING NEW == \n");
+
+ let beacon_edges = gen_edges(&beacon_nodes);
+
+ let mut overlapping: Option<usize> = None;
+ for (i,scanner_nodes) in scanners.iter().enumerate() {
+ let res = get_overlap_nodes(i + 1,
+ &scanner_nodes, &beacon_nodes, &beacon_edges);
+ if res.is_some() {
+ overlapping = Some(i);
+ let (mut new_nodes,_) = res.unwrap();
+ beacon_nodes.append(&mut new_nodes);
+ break;
+ }
+ }
+ assert!(overlapping.is_some());
+
+ scanners.remove(overlapping.unwrap());
+ }
+
+ aoc.answer = Some(format!("{}", beacon_nodes.len()));
+ aoc.solution = Some("462");
+}
+
+fn part2(aoc: &mut aoc::Info) {
+ let mut scanners = parse_scanners(&aoc.input);
+
+ let mut beacon_nodes: Vec<Pos> = Vec::new();
+ beacon_nodes.append(&mut scanners.remove(0));
+
+ let mut scanner_positions: Vec<Pos> = Vec::new();
+ while !scanners.is_empty() {
+ aoc::debugln!("\n== ADDING NEW == \n");
+
+ let beacon_edges = gen_edges(&beacon_nodes);
+
+ let mut overlapping: Option<usize> = None;
+ for (i,scanner_nodes) in scanners.iter().enumerate() {
+ let res = get_overlap_nodes(i + 1,
+ &scanner_nodes, &beacon_nodes, &beacon_edges);
+ if res.is_some() {
+ overlapping = Some(i);
+ let (mut new_nodes, scanner_pos) = res.unwrap();
+ scanner_positions.push(scanner_pos);
+ beacon_nodes.append(&mut new_nodes);
+ break;
+ }
+ }
+ assert!(overlapping.is_some());
+
+ scanners.remove(overlapping.unwrap());
+ }
+
+ let mut answer: usize = 0;
+ for p1 in &scanner_positions {
+ for p2 in &scanner_positions {
+ answer = usize::max(answer, p1.sub(p2).abs());
+ }
+ }
+ aoc.answer = Some(format!("{}", answer));
+}
+
+fn main() {
+ aoc::run(part1, part2);
+}
+
diff --git a/src/19/test1 b/src/19/test1
@@ -0,0 +1,10 @@
+--- scanner 0 ---
+0,2,0
+4,1,0
+3,3,0
+
+--- scanner 1 ---
+-1,-1,0
+-5,0,0
+-2,1,0
+
diff --git a/src/19/test2 b/src/19/test2
@@ -0,0 +1,41 @@
+--- scanner 0 ---
+-1,-1,1
+-2,-2,2
+-3,-3,3
+-2,-3,1
+5,6,-4
+8,0,7
+
+--- scanner 0 ---
+1,-1,1
+2,-2,2
+3,-3,3
+2,-1,3
+-5,4,-6
+-8,-7,0
+
+--- scanner 0 ---
+-1,-1,-1
+-2,-2,-2
+-3,-3,-3
+-1,-3,-2
+4,6,5
+-7,0,8
+
+--- scanner 0 ---
+1,1,-1
+2,2,-2
+3,3,-3
+1,3,-2
+-4,-6,5
+7,0,8
+
+--- scanner 0 ---
+1,1,1
+2,2,2
+3,3,3
+3,1,2
+-6,-4,-5
+0,7,-8
+
+
diff --git a/src/19/test3 b/src/19/test3
@@ -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
