- commit
- 8e8e79228da54b61f1b9356a51bc8c22ec65311f
- parent
- 10b4a7d7d1b166a1767a7d0b1d4d0b4634f35124
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2021-12-19 08:59
day 19
Diffstat
| A | 2021/19/input.txt | 723 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2021/19/part1.rs | 174 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2021/19/test.txt | 136 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
3 files changed, 1033 insertions, 0 deletions
diff --git a/2021/19/input.txt b/2021/19/input.txt
@@ -0,0 +1,723 @@ -1 1 --- scanner 0 --- -1 2 579,799,416 -1 3 48,82,-27 -1 4 474,-502,534 -1 5 652,-594,511 -1 6 -609,574,-469 -1 7 352,-544,-666 -1 8 -780,740,353 -1 9 -33,-102,-83 -1 10 384,-640,-624 -1 11 470,-559,544 -1 12 468,864,533 -1 13 670,759,-677 -1 14 -700,873,335 -1 15 -747,-486,-412 -1 16 349,-584,-782 -1 17 -382,-890,249 -1 18 -567,658,-522 -1 19 -689,659,-426 -1 20 531,820,-584 -1 21 -738,-569,-457 -1 22 -369,-772,414 -1 23 -816,800,310 -1 24 601,763,-473 -1 25 355,790,421 -1 26 -629,-538,-431 -1 27 -387,-903,381 -1 28 -1 29 --- scanner 1 --- -1 30 961,715,-541 -1 31 -390,653,-337 -1 32 475,-505,-519 -1 33 -398,393,554 -1 34 -543,-651,892 -1 35 917,-691,745 -1 36 -333,512,638 -1 37 -447,-609,924 -1 38 949,600,-504 -1 39 -487,-493,927 -1 40 959,652,536 -1 41 860,-802,675 -1 42 425,-583,-486 -1 43 31,89,-38 -1 44 856,-598,606 -1 45 -729,-629,-505 -1 46 -381,635,-466 -1 47 -728,-658,-697 -1 48 940,447,580 -1 49 423,-556,-430 -1 50 921,566,529 -1 51 -385,763,-451 -1 52 82,-46,86 -1 53 863,628,-559 -1 54 -792,-638,-728 -1 55 -441,535,654 -1 56 -1 57 --- scanner 2 --- -1 58 -619,-740,-444 -1 59 284,732,-285 -1 60 349,769,-397 -1 61 -800,371,856 -1 62 -154,-142,35 -1 63 -588,-753,-593 -1 64 433,-771,646 -1 65 426,648,604 -1 66 -469,-701,964 -1 67 -436,-703,873 -1 68 -831,445,878 -1 69 -68,-35,148 -1 70 433,-910,547 -1 71 321,677,-474 -1 72 658,-831,-735 -1 73 -708,471,-612 -1 74 532,743,654 -1 75 -599,-758,926 -1 76 543,-753,-648 -1 77 445,-815,-781 -1 78 -682,-685,-597 -1 79 491,-773,545 -1 80 -814,389,-621 -1 81 -712,458,817 -1 82 -726,309,-547 -1 83 422,838,592 -1 84 -1 85 --- scanner 3 --- -1 86 -742,640,493 -1 87 468,610,-347 -1 88 -656,680,388 -1 89 533,814,631 -1 90 -501,744,-596 -1 91 472,-555,-383 -1 92 -55,12,40 -1 93 603,-399,668 -1 94 -422,891,-618 -1 95 -505,-699,597 -1 96 -520,646,478 -1 97 -523,-607,-421 -1 98 -487,-491,600 -1 99 479,-501,677 -1 100 475,661,-559 -1 101 428,770,510 -1 102 -526,-596,-325 -1 103 443,-605,-422 -1 104 374,-553,-286 -1 105 548,-425,783 -1 106 -570,841,-566 -1 107 -401,-666,575 -1 108 605,756,519 -1 109 469,566,-488 -1 110 -494,-573,-565 -1 111 -1 112 --- scanner 4 --- -1 113 -24,-9,-13 -1 114 693,825,-612 -1 115 -659,674,730 -1 116 726,696,493 -1 117 -602,-470,716 -1 118 -548,804,-616 -1 119 -273,-440,-429 -1 120 755,920,-722 -1 121 591,-810,463 -1 122 104,132,31 -1 123 -798,656,824 -1 124 701,-689,-711 -1 125 -566,-637,674 -1 126 800,-828,-711 -1 127 901,636,510 -1 128 -548,-422,677 -1 129 592,-714,585 -1 130 -775,678,794 -1 131 -336,-418,-360 -1 132 906,716,416 -1 133 -738,825,-594 -1 134 -360,-472,-355 -1 135 -647,851,-605 -1 136 802,-691,-653 -1 137 743,730,-718 -1 138 676,-767,543 -1 139 -1 140 --- scanner 5 --- -1 141 295,-829,-370 -1 142 -646,-497,-795 -1 143 785,-566,682 -1 144 331,-823,-362 -1 145 396,624,-653 -1 146 -345,390,-837 -1 147 -854,-521,625 -1 148 -776,-569,671 -1 149 -719,302,694 -1 150 775,-608,710 -1 151 618,434,807 -1 152 613,-547,645 -1 153 -691,-468,-758 -1 154 -857,329,748 -1 155 366,768,-662 -1 156 -46,-127,-7 -1 157 -368,546,-822 -1 158 -855,-613,723 -1 159 477,-938,-370 -1 160 727,347,755 -1 161 803,431,840 -1 162 -390,421,-837 -1 163 -915,322,743 -1 164 -713,-449,-683 -1 165 322,664,-548 -1 166 -1 167 --- scanner 6 --- -1 168 -478,-795,-399 -1 169 636,601,800 -1 170 475,790,-480 -1 171 399,-509,961 -1 172 48,51,76 -1 173 -372,687,518 -1 174 429,-773,-421 -1 175 -854,749,-409 -1 176 -751,809,-318 -1 177 379,-786,-305 -1 178 -764,-417,427 -1 179 -712,-535,446 -1 180 552,-546,960 -1 181 -809,832,-531 -1 182 653,710,892 -1 183 483,781,-545 -1 184 -104,95,187 -1 185 378,-509,931 -1 186 -505,589,580 -1 187 -681,-426,472 -1 188 499,783,-725 -1 189 -347,-777,-366 -1 190 452,-886,-397 -1 191 -360,-782,-234 -1 192 720,662,828 -1 193 -418,474,502 -1 194 -1 195 --- scanner 7 --- -1 196 -747,-527,-295 -1 197 -383,523,528 -1 198 722,-666,942 -1 199 622,-640,-526 -1 200 -722,-449,-374 -1 201 822,-614,982 -1 202 531,486,601 -1 203 -473,-615,807 -1 204 658,-592,-519 -1 205 546,512,-555 -1 206 801,-857,967 -1 207 -487,406,-646 -1 208 -20,-36,160 -1 209 -491,411,-601 -1 210 596,468,439 -1 211 550,606,-623 -1 212 -705,-445,-317 -1 213 636,-516,-380 -1 214 699,575,-610 -1 215 -472,-687,821 -1 216 522,380,519 -1 217 -563,527,518 -1 218 -336,449,-620 -1 219 -74,-172,0 -1 220 -502,-611,738 -1 221 -473,453,641 -1 222 -1 223 --- scanner 8 --- -1 224 -325,277,621 -1 225 -346,432,631 -1 226 648,-738,463 -1 227 -284,-886,-509 -1 228 610,-583,-878 -1 229 429,537,390 -1 230 -366,-908,-467 -1 231 661,-654,541 -1 232 567,-557,-727 -1 233 605,-763,488 -1 234 -379,-707,832 -1 235 583,609,339 -1 236 823,713,-542 -1 237 888,705,-461 -1 238 -262,393,-504 -1 239 458,674,373 -1 240 -329,-650,646 -1 241 572,-602,-723 -1 242 -237,503,-467 -1 243 -288,-829,-492 -1 244 -5,6,-132 -1 245 -386,307,509 -1 246 -383,-599,733 -1 247 99,-170,-55 -1 248 -249,384,-440 -1 249 830,694,-667 -1 250 -1 251 --- scanner 9 --- -1 252 597,-475,-339 -1 253 821,675,845 -1 254 -364,-312,543 -1 255 414,576,-313 -1 256 743,721,797 -1 257 -328,-320,537 -1 258 -749,800,-693 -1 259 386,653,-405 -1 260 -661,726,-773 -1 261 -95,72,62 -1 262 -643,791,-611 -1 263 -647,-638,-624 -1 264 822,773,753 -1 265 -735,-677,-711 -1 266 613,-745,869 -1 267 658,-708,898 -1 268 487,-413,-244 -1 269 491,-425,-434 -1 270 -646,695,819 -1 271 349,464,-350 -1 272 -510,-320,428 -1 273 -818,732,800 -1 274 680,-633,917 -1 275 -766,-699,-637 -1 276 74,149,-8 -1 277 -808,760,758 -1 278 -1 279 --- scanner 10 --- -1 280 671,-555,-655 -1 281 672,548,433 -1 282 -684,363,-477 -1 283 628,600,354 -1 284 720,502,355 -1 285 792,-806,496 -1 286 397,393,-396 -1 287 -438,403,762 -1 288 -573,-435,-449 -1 289 -475,291,827 -1 290 397,400,-473 -1 291 434,477,-433 -1 292 -559,-598,685 -1 293 -464,-648,579 -1 294 -625,390,-456 -1 295 657,-513,-539 -1 296 773,-881,518 -1 297 -653,-440,-543 -1 298 744,-918,563 -1 299 -672,386,-603 -1 300 -147,-172,17 -1 301 647,-507,-645 -1 302 -369,-586,689 -1 303 -530,480,790 -1 304 -593,-615,-526 -1 305 -35,-50,-86 -1 306 -1 307 --- scanner 11 --- -1 308 -708,-978,-663 -1 309 715,-781,-742 -1 310 680,759,-622 -1 311 -262,303,742 -1 312 819,750,-718 -1 313 -406,333,733 -1 314 881,-642,685 -1 315 -701,-920,-668 -1 316 654,-831,-823 -1 317 557,760,713 -1 318 565,725,753 -1 319 940,-709,735 -1 320 -683,664,-675 -1 321 933,-652,865 -1 322 162,-1,80 -1 323 -484,-431,902 -1 324 -599,740,-760 -1 325 -596,555,-727 -1 326 763,-827,-746 -1 327 -366,259,628 -1 328 -609,-453,917 -1 329 -728,-782,-614 -1 330 -640,-408,917 -1 331 463,792,860 -1 332 30,-171,-39 -1 333 742,714,-656 -1 334 -1 335 --- scanner 12 --- -1 336 -557,-594,-751 -1 337 535,-288,-328 -1 338 522,-780,851 -1 339 577,462,-599 -1 340 -378,644,873 -1 341 506,-435,-371 -1 342 562,-830,712 -1 343 490,514,-708 -1 344 -404,624,-594 -1 345 620,-862,805 -1 346 30,-32,-49 -1 347 -485,-641,-711 -1 348 -470,546,874 -1 349 445,575,738 -1 350 442,-439,-322 -1 351 -423,587,-766 -1 352 -722,-561,777 -1 353 -794,-556,932 -1 354 472,521,876 -1 355 -426,598,795 -1 356 -666,-473,931 -1 357 465,526,934 -1 358 -41,29,133 -1 359 -673,-676,-778 -1 360 -465,559,-756 -1 361 574,429,-784 -1 362 -1 363 --- scanner 13 --- -1 364 -512,-780,-383 -1 365 -634,-328,271 -1 366 850,517,723 -1 367 409,-606,298 -1 368 -639,-724,-396 -1 369 380,-651,335 -1 370 100,-55,35 -1 371 -752,362,545 -1 372 735,371,731 -1 373 739,589,-529 -1 374 -411,665,-757 -1 375 656,-371,-623 -1 376 827,524,-467 -1 377 708,-458,-468 -1 378 833,537,-431 -1 379 -488,714,-796 -1 380 -610,-752,-415 -1 381 749,-364,-620 -1 382 -509,-350,256 -1 383 -478,-305,256 -1 384 -856,406,431 -1 385 361,-673,410 -1 386 741,335,723 -1 387 -436,839,-789 -1 388 22,58,-107 -1 389 -712,436,440 -1 390 -1 391 --- scanner 14 --- -1 392 -460,675,-680 -1 393 431,-518,-720 -1 394 410,-453,-630 -1 395 546,395,-372 -1 396 -809,-922,-637 -1 397 -476,-447,567 -1 398 -385,609,-563 -1 399 -679,-919,-628 -1 400 496,378,-277 -1 401 481,-504,704 -1 402 -668,-866,-537 -1 403 401,-490,-849 -1 404 -432,672,-630 -1 405 606,-464,582 -1 406 711,311,823 -1 407 -589,487,725 -1 408 848,340,840 -1 409 2,45,75 -1 410 -564,530,750 -1 411 559,334,-368 -1 412 783,465,874 -1 413 -533,-497,381 -1 414 -480,543,672 -1 415 -425,-501,480 -1 416 451,-443,592 -1 417 95,-118,129 -1 418 -1 419 --- scanner 15 --- -1 420 901,-715,774 -1 421 -447,800,-713 -1 422 -499,-598,656 -1 423 -530,755,-704 -1 424 613,743,-575 -1 425 -57,-132,9 -1 426 863,-629,781 -1 427 859,628,565 -1 428 383,-740,-702 -1 429 563,-720,-625 -1 430 698,786,-655 -1 431 388,-660,-608 -1 432 802,739,635 -1 433 -499,781,-595 -1 434 -391,-575,672 -1 435 -415,-629,-674 -1 436 -438,-641,-548 -1 437 697,690,-533 -1 438 -545,430,383 -1 439 -442,-688,-695 -1 440 882,-510,730 -1 441 -505,546,386 -1 442 -456,-456,756 -1 443 798,535,704 -1 444 100,-5,81 -1 445 -601,588,418 -1 446 -1 447 --- scanner 16 --- -1 448 645,-660,-815 -1 449 686,-400,877 -1 450 -788,541,-551 -1 451 -582,-777,-582 -1 452 549,-417,906 -1 453 -726,-490,687 -1 454 0,107,10 -1 455 -169,-72,58 -1 456 621,-366,752 -1 457 -751,-515,730 -1 458 800,-659,-703 -1 459 -545,700,768 -1 460 725,515,512 -1 461 -482,-755,-724 -1 462 -571,851,725 -1 463 -816,457,-490 -1 464 737,678,-369 -1 465 557,694,-371 -1 466 -648,-739,-637 -1 467 717,434,447 -1 468 -642,-568,674 -1 469 -880,524,-442 -1 470 585,-617,-730 -1 471 706,640,505 -1 472 492,702,-362 -1 473 -590,696,763 -1 474 -1 475 --- scanner 17 --- -1 476 -786,419,-780 -1 477 580,542,522 -1 478 -753,-461,678 -1 479 -671,506,-702 -1 480 660,-476,-725 -1 481 -723,-515,665 -1 482 491,710,-689 -1 483 -659,-635,-482 -1 484 460,561,-702 -1 485 4,11,-37 -1 486 -133,118,35 -1 487 -477,757,820 -1 488 -550,-652,-390 -1 489 -828,-586,678 -1 490 -449,680,728 -1 491 554,557,-634 -1 492 598,607,360 -1 493 539,-552,439 -1 494 686,533,440 -1 495 -412,869,783 -1 496 617,-325,-699 -1 497 543,-372,449 -1 498 613,-462,562 -1 499 -598,-719,-454 -1 500 -573,373,-764 -1 501 655,-480,-680 -1 502 -1 503 --- scanner 18 --- -1 504 -626,741,779 -1 505 -621,839,736 -1 506 870,-429,299 -1 507 -329,-456,-530 -1 508 -481,-415,-436 -1 509 474,-784,-723 -1 510 769,358,-552 -1 511 -484,-508,-443 -1 512 862,-314,445 -1 513 72,37,-49 -1 514 707,453,-662 -1 515 -564,805,649 -1 516 862,-423,263 -1 517 -328,-337,452 -1 518 757,548,-556 -1 519 437,-755,-678 -1 520 544,738,582 -1 521 -292,-331,465 -1 522 483,751,701 -1 523 -633,427,-669 -1 524 -390,-425,517 -1 525 505,825,670 -1 526 -724,453,-680 -1 527 -534,474,-658 -1 528 549,-803,-745 -1 529 -1 530 --- scanner 19 --- -1 531 885,-364,-767 -1 532 -758,-757,-795 -1 533 -620,501,549 -1 534 -808,378,-727 -1 535 -652,-436,692 -1 536 -654,530,693 -1 537 563,-461,767 -1 538 -36,-26,43 -1 539 -602,-465,731 -1 540 -643,533,789 -1 541 754,-346,-734 -1 542 81,100,-56 -1 543 697,508,518 -1 544 614,-468,555 -1 545 541,493,-604 -1 546 -818,-793,-838 -1 547 484,497,-614 -1 548 872,-359,-899 -1 549 -882,491,-615 -1 550 -891,-677,-813 -1 551 519,-462,626 -1 552 -817,602,-732 -1 553 844,429,496 -1 554 576,675,-637 -1 555 -600,-367,828 -1 556 794,577,548 -1 557 -1 558 --- scanner 20 --- -1 559 521,799,641 -1 560 -814,-478,803 -1 561 564,734,-498 -1 562 -816,-536,666 -1 563 -505,755,-478 -1 564 416,854,546 -1 565 -715,-478,664 -1 566 626,864,-562 -1 567 446,818,519 -1 568 346,-834,447 -1 569 322,-829,393 -1 570 633,-584,-876 -1 571 -483,786,-552 -1 572 -488,391,596 -1 573 724,-595,-850 -1 574 -397,424,594 -1 575 534,-573,-829 -1 576 621,821,-464 -1 577 -544,667,-565 -1 578 -757,-471,-755 -1 579 -47,63,-74 -1 580 259,-760,415 -1 581 -707,-577,-850 -1 582 -435,554,651 -1 583 -769,-467,-945 -1 584 -1 585 --- scanner 21 --- -1 586 693,-762,-734 -1 587 616,828,628 -1 588 -684,-626,636 -1 589 -595,479,-482 -1 590 -383,525,-446 -1 591 674,-607,-772 -1 592 -568,-625,-730 -1 593 -392,572,557 -1 594 782,844,715 -1 595 682,866,573 -1 596 -445,-535,-656 -1 597 -363,646,506 -1 598 448,-368,481 -1 599 56,54,26 -1 600 -671,-572,606 -1 601 -72,160,-43 -1 602 513,604,-739 -1 603 538,579,-696 -1 604 476,-452,542 -1 605 -684,-501,711 -1 606 384,-435,433 -1 607 -455,-715,-660 -1 608 -471,488,-412 -1 609 622,657,-683 -1 610 -315,512,408 -1 611 719,-611,-777 -1 612 -1 613 --- scanner 22 --- -1 614 -426,-460,-817 -1 615 430,-548,757 -1 616 17,-21,65 -1 617 645,-446,-810 -1 618 -502,-376,-732 -1 619 702,-493,-691 -1 620 312,721,-517 -1 621 477,-544,865 -1 622 283,-543,859 -1 623 -616,518,-622 -1 624 676,-492,-734 -1 625 332,738,-554 -1 626 -96,88,-105 -1 627 -863,-797,685 -1 628 -934,800,393 -1 629 -454,579,-687 -1 630 498,874,776 -1 631 -752,909,393 -1 632 -611,-463,-784 -1 633 473,807,749 -1 634 535,829,715 -1 635 -898,794,385 -1 636 369,646,-663 -1 637 -444,537,-659 -1 638 -907,-693,571 -1 639 -833,-653,676 -1 640 -1 641 --- scanner 23 --- -1 642 614,503,499 -1 643 -741,-573,-430 -1 644 666,496,-326 -1 645 586,590,-331 -1 646 -874,485,504 -1 647 70,134,-24 -1 648 -764,665,-640 -1 649 709,-743,589 -1 650 -855,603,556 -1 651 -860,543,-641 -1 652 -739,-631,-531 -1 653 680,-638,-489 -1 654 -799,-406,850 -1 655 870,-642,-477 -1 656 -67,-30,81 -1 657 801,-715,512 -1 658 -878,-631,-432 -1 659 -783,-619,896 -1 660 764,-780,400 -1 661 567,650,495 -1 662 -829,494,587 -1 663 555,524,472 -1 664 -817,623,-556 -1 665 646,573,-506 -1 666 775,-532,-539 -1 667 -721,-521,763 -1 668 -1 669 --- scanner 24 --- -1 670 -804,350,366 -1 671 456,-494,-642 -1 672 363,-619,389 -1 673 -411,-594,552 -1 674 261,606,745 -1 675 284,599,-445 -1 676 341,-681,423 -1 677 372,534,-507 -1 678 278,586,-409 -1 679 -878,381,388 -1 680 -1,-117,40 -1 681 -791,469,427 -1 682 -127,5,-73 -1 683 -670,-495,-397 -1 684 435,-446,-785 -1 685 543,-509,-828 -1 686 -403,-518,594 -1 687 -734,-428,-464 -1 688 296,-644,362 -1 689 -858,402,-681 -1 690 376,752,753 -1 691 -849,-457,-445 -1 692 -892,315,-738 -1 693 370,788,745 -1 694 -794,272,-743 -1 695 -418,-406,604 -1 696 -1 697 --- scanner 25 --- -1 698 86,149,-150 -1 699 -572,-670,-518 -1 700 748,-704,-522 -1 701 569,-536,361 -1 702 -723,-522,310 -1 703 563,566,-778 -1 704 -419,589,553 -1 705 -665,-309,333 -1 706 -597,-464,-470 -1 707 829,-696,-457 -1 708 739,901,432 -1 709 806,837,480 -1 710 561,-471,352 -1 711 -628,-622,-575 -1 712 722,809,541 -1 713 -623,602,-609 -1 714 585,-716,359 -1 715 623,-685,-515 -1 716 -470,657,-672 -1 717 -474,589,-578 -1 718 412,592,-735 -1 719 -286,527,455 -1 720 1,56,27 -1 721 567,611,-773 -1 722 -332,511,668 -1 723 -768,-400,393
diff --git a/2021/19/part1.rs b/2021/19/part1.rs
@@ -0,0 +1,174 @@
-1 1 use std::collections::HashSet;
-1 2 use std::env::args;
-1 3 use std::fs::File;
-1 4 use std::io::BufRead;
-1 5 use std::io::BufReader;
-1 6
-1 7 struct Scanner {
-1 8 beacons: Vec<[i32; 3]>,
-1 9 position: [i32; 3],
-1 10 }
-1 11
-1 12 fn get_data() -> Vec<Vec<[i32; 3]>> {
-1 13 let path = args().nth(1).unwrap();
-1 14 let file = File::open(path).unwrap();
-1 15
-1 16 let mut scanners = vec![];
-1 17 let mut beacons = vec![];
-1 18
-1 19 for line in BufReader::new(file).lines() {
-1 20 match line.unwrap().split(",").collect::<Vec<&str>>()[..] {
-1 21 [""] => {
-1 22 scanners.push(beacons);
-1 23 beacons = vec![];
-1 24 },
-1 25 [a, b, c] => {
-1 26 beacons.push([
-1 27 a.parse::<i32>().unwrap(),
-1 28 b.parse::<i32>().unwrap(),
-1 29 c.parse::<i32>().unwrap(),
-1 30 ])
-1 31 },
-1 32 [_] => {},
-1 33 _ => unreachable!(),
-1 34 }
-1 35 }
-1 36 scanners.push(beacons);
-1 37
-1 38 return scanners;
-1 39 }
-1 40
-1 41 fn apply_rotation(beacon: [i32; 3], rotation: u8) -> [i32; 3] {
-1 42 let [x, y, z] = beacon;
-1 43 let [x1, y1, z1] = match rotation / 4 {
-1 44 0 => [ x, y, z],
-1 45 1 => [-z, y, x],
-1 46 2 => [-x, y, -z],
-1 47 3 => [ z, y, -x],
-1 48 4 => [ x, -z, y],
-1 49 5 => [ x, z, -y],
-1 50 _ => unreachable!(),
-1 51 };
-1 52 return match rotation % 4 {
-1 53 0 => [ x1, y1, z1],
-1 54 1 => [-y1, x1, z1],
-1 55 2 => [-x1, -y1, z1],
-1 56 3 => [ y1, -x1, z1],
-1 57 _ => unreachable!(),
-1 58 };
-1 59 }
-1 60
-1 61 fn apply_position(beacons: &Vec<[i32; 3]>, position: [i32; 3], rotation: u8) -> Vec<[i32; 3]> {
-1 62 let [dx, dy, dz] = position;
-1 63 beacons
-1 64 .iter()
-1 65 .map(|beacon| apply_rotation(*beacon, rotation))
-1 66 .map(|[x, y, z]| [x + dx, y + dy, z + dz])
-1 67 .collect()
-1 68 }
-1 69
-1 70 fn in_scanner_range(beacon: [i32; 3], a: [i32; 3], b: [i32; 3]) -> bool {
-1 71 let [x, y, z] = beacon;
-1 72 let [ax, ay, az] = a;
-1 73 let [bx, by, bz] = b;
-1 74 (
-1 75 (ax <= bx && bx - 1000 <= x && x <= ax + 1000)
-1 76 || (bx <= ax && ax - 1000 <= x && x <= bx + 1000)
-1 77 ) && (
-1 78 (ay <= by && by - 1000 <= y && y <= ay + 1000)
-1 79 || (by <= ay && ay - 1000 <= y && y <= by + 1000)
-1 80 ) && (
-1 81 (az <= bz && bz - 1000 <= z && z <= az + 1000)
-1 82 || (bz <= az && az - 1000 <= z && z <= bz + 1000)
-1 83 )
-1 84 }
-1 85
-1 86 fn check_overlap(a: &Scanner, b: &Vec<[i32; 3]>, b_position: [i32; 3], b_rotation: u8) -> bool {
-1 87 let a_position = a.position;
-1 88 let a_area: HashSet<[i32; 3]> = a.beacons.clone().into_iter().filter(|beacon|
-1 89 in_scanner_range(*beacon, a_position, b_position)
-1 90 ).collect();
-1 91 let n = a_area.len();
-1 92 if n < 12 {
-1 93 return false;
-1 94 }
-1 95
-1 96 // TODO PERF: if match we could reuse this
-1 97 let b_mapped = apply_position(b, b_position, b_rotation);
-1 98 let b_area: HashSet<[i32; 3]> = b_mapped.into_iter().filter(|beacon|
-1 99 in_scanner_range(*beacon, a_position, b_position)
-1 100 ).collect();
-1 101
-1 102 return b_area.len() == n && a_area.intersection(&b_area).count() == n;
-1 103 }
-1 104
-1 105 fn find_overlap(a: &Scanner, b: &Vec<[i32; 3]>) -> Option<([i32; 3], u8)> {
-1 106 for rotation in 0..24 {
-1 107 for beacon in b.iter() {
-1 108 let [bx1, by1, bz1] = apply_rotation(*beacon, rotation);
-1 109 // PERF: we can skip up to 11 beacons because we need to match at least 12
-1 110 for [ax1, ay1, az1] in a.beacons[11..].iter() {
-1 111 let pos = [ax1 - bx1, ay1 - by1, az1 - bz1];
-1 112 if check_overlap(a, b, pos, rotation) {
-1 113 return Some((pos, rotation));
-1 114 }
-1 115 }
-1 116 }
-1 117 }
-1 118 return None;
-1 119 }
-1 120
-1 121 fn main() {
-1 122 let mut unsettled = get_data();
-1 123 let mut queue: Vec<Scanner> = vec![];
-1 124 let mut settled: Vec<Scanner> = vec![];
-1 125
-1 126 let first = unsettled.pop().unwrap();
-1 127 queue.push(Scanner {
-1 128 beacons: first,
-1 129 position: [0, 0, 0],
-1 130 });
-1 131
-1 132 while queue.len() > 0 {
-1 133 println!("unsettled: {} queued: {} settled: {}", unsettled.len(), queue.len(), settled.len());
-1 134 let cur = queue.pop().unwrap();
-1 135 let mut i = 0;
-1 136 while i < unsettled.len() {
-1 137 match find_overlap(&cur, &unsettled[i]) {
-1 138 None => i += 1,
-1 139 Some((position, rotation)) => {
-1 140 let beacons = unsettled.remove(i);
-1 141 let mapped = apply_position(&beacons, position, rotation);
-1 142 queue.push(Scanner {
-1 143 beacons: mapped,
-1 144 position,
-1 145 });
-1 146 },
-1 147 }
-1 148 }
-1 149 settled.push(cur);
-1 150 }
-1 151
-1 152 assert_eq!(unsettled.len(), 0);
-1 153
-1 154 let mut beacons = HashSet::new();
-1 155 for scanner in settled.iter() {
-1 156 for beacon in scanner.beacons.iter() {
-1 157 beacons.insert(beacon);
-1 158 }
-1 159 }
-1 160 println!("{}", beacons.len());
-1 161
-1 162 let mut max_distance = 0;
-1 163 for a in settled.iter() {
-1 164 let [ax, ay, az] = a.position;
-1 165 for b in settled.iter() {
-1 166 let [bx, by, bz] = b.position;
-1 167 let d = (ax - bx).abs() + (ay - by).abs() + (az - bz).abs();
-1 168 if d > max_distance {
-1 169 max_distance = d;
-1 170 }
-1 171 }
-1 172 }
-1 173 println!("{}", max_distance);
-1 174 }
diff --git a/2021/19/test.txt b/2021/19/test.txt
@@ -0,0 +1,136 @@ -1 1 --- scanner 0 --- -1 2 404,-588,-901 -1 3 528,-643,409 -1 4 -838,591,734 -1 5 390,-675,-793 -1 6 -537,-823,-458 -1 7 -485,-357,347 -1 8 -345,-311,381 -1 9 -661,-816,-575 -1 10 -876,649,763 -1 11 -618,-824,-621 -1 12 553,345,-567 -1 13 474,580,667 -1 14 -447,-329,318 -1 15 -584,868,-557 -1 16 544,-627,-890 -1 17 564,392,-477 -1 18 455,729,728 -1 19 -892,524,684 -1 20 -689,845,-530 -1 21 423,-701,434 -1 22 7,-33,-71 -1 23 630,319,-379 -1 24 443,580,662 -1 25 -789,900,-551 -1 26 459,-707,401 -1 27 -1 28 --- scanner 1 --- -1 29 686,422,578 -1 30 605,423,415 -1 31 515,917,-361 -1 32 -336,658,858 -1 33 95,138,22 -1 34 -476,619,847 -1 35 -340,-569,-846 -1 36 567,-361,727 -1 37 -460,603,-452 -1 38 669,-402,600 -1 39 729,430,532 -1 40 -500,-761,534 -1 41 -322,571,750 -1 42 -466,-666,-811 -1 43 -429,-592,574 -1 44 -355,545,-477 -1 45 703,-491,-529 -1 46 -328,-685,520 -1 47 413,935,-424 -1 48 -391,539,-444 -1 49 586,-435,557 -1 50 -364,-763,-893 -1 51 807,-499,-711 -1 52 755,-354,-619 -1 53 553,889,-390 -1 54 -1 55 --- scanner 2 --- -1 56 649,640,665 -1 57 682,-795,504 -1 58 -784,533,-524 -1 59 -644,584,-595 -1 60 -588,-843,648 -1 61 -30,6,44 -1 62 -674,560,763 -1 63 500,723,-460 -1 64 609,671,-379 -1 65 -555,-800,653 -1 66 -675,-892,-343 -1 67 697,-426,-610 -1 68 578,704,681 -1 69 493,664,-388 -1 70 -671,-858,530 -1 71 -667,343,800 -1 72 571,-461,-707 -1 73 -138,-166,112 -1 74 -889,563,-600 -1 75 646,-828,498 -1 76 640,759,510 -1 77 -630,509,768 -1 78 -681,-892,-333 -1 79 673,-379,-804 -1 80 -742,-814,-386 -1 81 577,-820,562 -1 82 -1 83 --- scanner 3 --- -1 84 -589,542,597 -1 85 605,-692,669 -1 86 -500,565,-823 -1 87 -660,373,557 -1 88 -458,-679,-417 -1 89 -488,449,543 -1 90 -626,468,-788 -1 91 338,-750,-386 -1 92 528,-832,-391 -1 93 562,-778,733 -1 94 -938,-730,414 -1 95 543,643,-506 -1 96 -524,371,-870 -1 97 407,773,750 -1 98 -104,29,83 -1 99 378,-903,-323 -1 100 -778,-728,485 -1 101 426,699,580 -1 102 -438,-605,-362 -1 103 -469,-447,-387 -1 104 509,732,623 -1 105 647,635,-688 -1 106 -868,-804,481 -1 107 614,-800,639 -1 108 595,780,-596 -1 109 -1 110 --- scanner 4 --- -1 111 727,592,562 -1 112 -293,-554,779 -1 113 441,611,-461 -1 114 -714,465,-776 -1 115 -743,427,-804 -1 116 -660,-479,-426 -1 117 832,-632,460 -1 118 927,-485,-438 -1 119 408,393,-506 -1 120 466,436,-512 -1 121 110,16,151 -1 122 -258,-428,682 -1 123 -393,719,612 -1 124 -211,-452,876 -1 125 808,-476,-593 -1 126 -575,615,604 -1 127 -485,667,467 -1 128 -680,325,-822 -1 129 -627,-443,-432 -1 130 872,-547,-609 -1 131 833,512,582 -1 132 807,604,487 -1 133 839,-516,451 -1 134 891,-625,532 -1 135 -652,-548,-490 -1 136 30,-46,-14