From 7c0dd5d118d60fb7ef1094f6664237f79a54240e Mon Sep 17 00:00:00 2001 From: Leah Neukirchen Date: Mon, 20 Dec 2021 17:42:32 +0100 Subject: day19 --- day19 | 1028 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ day19.clj | 94 ++++++ 2 files changed, 1122 insertions(+) create mode 100644 day19 create mode 100644 day19.clj diff --git a/day19 b/day19 new file mode 100644 index 0000000..dec6605 --- /dev/null +++ b/day19 @@ -0,0 +1,1028 @@ +--- scanner 0 --- +518,-324,325 +-757,492,-559 +-804,-678,847 +-64,-12,64 +371,698,-494 +467,-524,299 +-920,-609,814 +428,613,-347 +731,378,348 +467,-704,-403 +-766,564,-509 +-581,-437,-419 +785,563,361 +-732,-659,761 +-157,-74,-106 +282,582,-425 +387,-696,-454 +-570,-484,-507 +-654,350,668 +-760,359,665 +-522,-424,-636 +499,-332,281 +693,551,425 +333,-713,-333 +-740,458,696 +-770,423,-443 + +--- scanner 1 --- +371,568,-587 +-599,701,-690 +-513,-505,867 +730,-849,-571 +-445,709,906 +568,323,494 +589,363,707 +-544,-470,921 +-555,768,923 +527,445,588 +-158,-85,60 +-411,-823,-426 +309,464,-682 +-5,43,125 +257,-498,922 +661,-760,-455 +241,-685,891 +-447,-900,-351 +-599,742,-625 +-496,-440,728 +-551,-849,-451 +808,-703,-540 +432,626,-671 +255,-669,958 +-621,725,-667 +-410,710,843 + +--- scanner 2 --- +-701,-443,-920 +554,-925,-548 +-505,704,-530 +419,431,418 +-513,-502,-879 +-109,-145,-127 +470,-909,-731 +-564,-674,438 +-752,371,454 +-700,393,567 +666,-876,-680 +-671,688,-596 +417,-684,686 +506,-629,736 +390,671,-790 +-624,-644,341 +-162,-69,52 +469,345,375 +324,-667,704 +463,776,-910 +-698,-643,418 +-577,-474,-904 +486,265,414 +-522,788,-569 +342,786,-839 +-714,526,517 + +--- scanner 3 --- +745,-414,606 +98,32,-1 +584,-745,-450 +-459,807,528 +674,891,-539 +396,761,746 +643,-643,-519 +-556,698,506 +502,882,-596 +-583,-400,620 +-510,-464,752 +759,-432,575 +-564,-449,655 +-615,759,549 +-344,907,-491 +671,-820,-556 +-466,-577,-463 +-545,-585,-529 +-467,933,-414 +817,-391,573 +567,935,-641 +-462,800,-552 +-474,-765,-513 +421,825,718 +380,637,777 + +--- scanner 4 --- +418,688,451 +-688,-444,530 +735,-462,-655 +-447,822,753 +618,721,466 +-801,300,-569 +-466,736,681 +-516,789,869 +852,733,-797 +873,528,-797 +514,568,466 +594,-768,706 +-793,256,-550 +850,550,-772 +600,-812,631 +472,-833,596 +-701,-661,471 +107,-143,36 +-421,-428,-518 +-601,274,-518 +-641,-532,519 +-429,-479,-438 +535,-482,-587 +-412,-358,-384 +621,-410,-695 + +--- scanner 5 --- +-108,-59,-141 +627,313,281 +-592,-712,-605 +-487,683,553 +-752,428,-384 +-666,-346,805 +-450,-594,-573 +814,-564,591 +643,380,267 +836,-381,588 +430,-700,-550 +59,-32,-32 +-87,67,39 +-751,365,-419 +-713,-385,821 +-654,-420,633 +-571,-500,-647 +782,-483,530 +456,349,283 +-405,564,615 +-810,348,-529 +426,-544,-637 +-365,777,594 +422,-539,-462 +463,404,-487 +398,543,-470 +428,350,-518 + +--- scanner 6 --- +743,320,649 +-758,-625,753 +796,304,-726 +710,-783,-638 +516,-869,482 +-915,595,-514 +568,422,671 +414,-953,506 +681,353,-678 +593,377,728 +-723,607,919 +674,-843,-435 +436,-961,451 +-486,-430,-529 +-553,645,861 +-867,-502,806 +-866,463,-402 +-465,-399,-496 +-899,412,-598 +-645,714,844 +786,233,-605 +740,-960,-549 +-693,-560,751 +-675,-437,-542 +21,-94,89 + +--- scanner 7 --- +494,879,534 +438,836,579 +548,-792,-893 +-853,669,682 +-415,571,-714 +545,-592,445 +360,-733,-852 +-425,665,-760 +-819,-359,-653 +32,64,-17 +-707,-310,-521 +-888,632,562 +411,-561,465 +-533,540,-709 +471,-591,368 +-570,-551,713 +-659,-606,763 +424,-761,-877 +303,581,-771 +-623,-326,-704 +294,524,-599 +250,626,-706 +-135,-69,14 +341,833,565 +-477,-568,731 +-760,706,566 + +--- scanner 8 --- +795,755,647 +277,-364,-462 +-864,-338,-607 +-942,-484,-576 +417,-338,-487 +502,509,-840 +-650,486,578 +-662,527,450 +-391,-689,886 +27,-32,-62 +-712,608,542 +410,-717,885 +-389,-518,922 +362,-747,692 +409,436,-792 +379,-682,831 +586,394,-774 +-780,710,-625 +-730,701,-697 +313,-287,-387 +-375,-502,855 +822,730,622 +-159,13,21 +730,713,775 +-795,-427,-491 +-846,714,-766 + +--- scanner 9 --- +547,-387,715 +634,495,479 +563,-496,-567 +-637,-417,-717 +-437,925,-704 +408,-433,-529 +-840,-705,693 +-607,-320,-657 +741,551,-776 +-610,504,448 +560,434,446 +-577,576,471 +-876,-681,614 +430,-546,-581 +-788,-702,470 +-406,941,-580 +618,-345,803 +825,590,-759 +-608,562,489 +-109,-47,-74 +-465,900,-768 +650,404,359 +-25,34,68 +-606,-397,-583 +725,617,-610 +762,-326,738 + +--- scanner 10 --- +-822,-854,486 +-503,681,509 +592,-666,-332 +-678,781,-366 +-59,-27,58 +447,-408,479 +2,-131,-84 +452,325,-407 +582,405,-479 +579,-696,-350 +-830,-926,-623 +-791,-818,361 +512,438,683 +623,-680,-345 +-698,-738,474 +-748,-874,-550 +-729,807,-566 +379,476,693 +-697,825,-374 +441,-508,355 +585,329,-522 +-854,-753,-556 +435,471,821 +-411,745,521 +461,-514,425 +-465,758,336 + +--- scanner 11 --- +-490,801,756 +-770,-350,518 +-822,-407,659 +-513,758,631 +682,477,652 +-731,729,-763 +-862,-529,-479 +378,-671,556 +717,526,-657 +699,557,-671 +-7,44,90 +-805,-693,-429 +-753,-622,-557 +-452,811,721 +-766,-501,599 +740,559,-729 +709,-685,-738 +731,512,671 +667,380,598 +-88,-38,-71 +326,-641,513 +378,-725,522 +-824,789,-706 +-846,781,-723 +742,-611,-799 +829,-701,-829 + +--- scanner 12 --- +130,21,-111 +-656,-401,-533 +-702,759,697 +554,-554,-934 +-585,-259,-532 +519,732,677 +446,-653,-904 +-16,170,-52 +735,802,-897 +531,-604,-952 +-753,-281,783 +-798,-450,757 +760,942,-871 +-591,-302,-583 +559,-582,732 +496,754,653 +561,754,694 +-674,789,603 +-636,-416,810 +835,906,-948 +-780,544,-489 +-681,532,-515 +521,-555,607 +-705,691,696 +522,-683,577 +-727,449,-443 + +--- scanner 13 --- +-387,408,298 +-360,-677,-365 +819,400,647 +-794,-575,446 +-328,596,257 +891,-568,267 +-359,472,273 +803,566,581 +-577,426,-582 +134,-81,19 +-570,-631,-403 +-761,-771,497 +779,-738,-809 +786,-495,387 +815,-535,-749 +930,560,-762 +903,417,608 +901,-447,338 +-810,-659,629 +-556,474,-738 +-381,-644,-396 +845,-624,-926 +882,756,-734 +-38,47,-5 +-599,535,-679 +942,781,-732 + +--- scanner 14 --- +415,-791,688 +-423,-346,-630 +890,652,453 +111,-5,-108 +888,592,458 +866,563,575 +471,-440,-707 +-47,-31,63 +-823,430,787 +554,-808,753 +599,-375,-749 +624,-348,-724 +-396,-438,-648 +361,-760,723 +-533,-641,725 +-531,541,-866 +-443,-336,-542 +-787,524,790 +-791,556,745 +-689,-728,721 +-586,630,-844 +546,512,-569 +-468,718,-860 +438,562,-623 +-528,-816,729 +454,451,-562 + +--- scanner 15 --- +357,847,-506 +431,735,445 +392,-401,404 +-416,-604,-802 +-860,-246,637 +633,789,457 +-552,446,-529 +-396,710,604 +-479,-536,-686 +318,-362,462 +-131,49,-91 +397,899,-391 +-578,504,-608 +641,-411,-375 +-630,-226,588 +33,86,13 +414,907,-413 +691,-575,-432 +563,-504,-484 +335,-472,434 +605,643,441 +-457,425,-510 +-429,647,537 +-427,-702,-765 +-741,-281,720 +-382,767,612 + +--- scanner 16 --- +-633,-674,333 +-760,481,-460 +668,819,527 +550,-559,686 +-659,644,592 +680,680,-645 +-369,-571,-867 +695,694,589 +-68,-97,-89 +-687,-708,333 +803,710,-763 +-312,-712,-815 +878,629,-690 +-692,481,-371 +418,-632,622 +-463,-631,-811 +796,-599,-558 +84,61,-152 +-603,-717,281 +515,-578,637 +-660,500,-537 +558,720,539 +849,-509,-497 +-751,651,653 +839,-474,-535 +-767,590,542 + +--- scanner 17 --- +-635,-235,-728 +856,593,-529 +42,138,10 +-628,796,-357 +620,929,867 +-642,-758,687 +415,-579,694 +524,-482,716 +443,887,885 +-812,609,859 +536,814,933 +463,-423,673 +549,-399,-813 +-688,-796,477 +764,610,-682 +-696,622,790 +-546,-412,-698 +770,-429,-825 +-678,715,-449 +-616,837,-485 +-749,-352,-662 +-746,613,718 +-655,-765,498 +-89,21,94 +829,568,-554 +745,-427,-765 + +--- scanner 18 --- +423,690,-627 +465,808,-674 +-681,-556,721 +430,673,-675 +-795,510,-788 +-525,-433,-454 +-797,681,-824 +-463,-351,-573 +-620,-614,805 +885,-699,-394 +528,450,736 +-322,861,705 +738,-488,424 +-811,697,-757 +464,358,724 +-244,715,674 +-743,-452,816 +-484,-311,-360 +814,-580,-456 +174,59,-29 +806,-589,-322 +-391,772,589 +52,30,126 +771,-565,562 +451,412,909 +733,-432,552 + +--- scanner 19 --- +742,468,518 +71,-35,-37 +-710,627,527 +361,-802,-714 +383,484,-899 +291,-811,-848 +-819,-578,600 +-390,280,-450 +-743,-535,597 +681,384,576 +412,-794,-794 +-672,637,394 +-367,-422,-663 +-823,-463,467 +305,515,-753 +-403,465,-396 +672,-512,444 +757,-600,483 +757,-398,454 +-323,-430,-682 +-467,453,-488 +-341,-622,-714 +804,373,414 +-677,765,450 +452,600,-810 + +--- scanner 20 --- +-544,629,-427 +20,-171,-93 +371,-709,-476 +-807,-622,-421 +-806,-694,-491 +-755,-685,-481 +-944,497,344 +-131,-48,-22 +369,626,403 +481,-697,-472 +320,674,288 +393,-780,491 +-945,-503,648 +453,366,-586 +-767,586,374 +-564,653,-501 +438,-723,516 +336,-701,341 +249,553,298 +437,359,-706 +410,-789,-558 +449,306,-624 +-827,383,410 +-762,647,-443 +-937,-558,670 +-853,-534,568 + +--- scanner 21 --- +-403,620,751 +378,-908,681 +483,-788,754 +-544,-708,434 +497,564,-657 +596,-719,-595 +-626,-720,487 +-385,709,721 +809,377,675 +621,564,-506 +368,-837,802 +-474,684,-344 +-396,-786,-581 +-345,751,653 +-392,-676,-569 +-536,554,-353 +421,-821,-573 +-506,-704,494 +-42,50,68 +-592,768,-366 +723,420,725 +889,416,658 +-478,-747,-661 +571,-764,-652 +78,-91,-29 +591,547,-650 + +--- scanner 22 --- +-627,-326,675 +675,671,-519 +644,-874,521 +-619,505,-796 +-583,-508,-362 +676,-892,329 +582,751,-406 +870,-748,-554 +-477,-505,-353 +908,-825,-381 +-555,-412,656 +-743,-359,606 +-304,638,483 +9,95,-66 +-598,600,-727 +625,807,505 +962,-812,-566 +-449,666,429 +519,686,511 +-724,642,-840 +78,-93,-116 +695,-848,321 +543,859,578 +551,787,-531 +-563,-477,-461 +-425,503,444 + +--- scanner 23 --- +449,677,-648 +-173,-153,18 +619,686,465 +406,-769,-584 +-657,687,422 +619,618,376 +600,586,542 +-678,721,510 +420,-754,650 +471,-952,695 +-566,241,-447 +-402,-806,-446 +-30,-38,107 +-722,596,510 +281,-742,-522 +390,-877,768 +-688,265,-536 +-420,-783,-496 +-740,-427,645 +510,693,-537 +-650,-424,811 +-747,-398,662 +-571,243,-507 +380,-632,-534 +456,585,-587 +-450,-891,-397 + +--- scanner 24 --- +-590,-629,-597 +710,304,866 +154,-67,33 +688,327,841 +-288,796,-335 +682,-762,-820 +-485,-498,-550 +517,559,-397 +16,-171,107 +626,-756,-590 +-417,748,-451 +710,-586,650 +550,759,-382 +663,-870,-675 +670,663,-397 +-665,-529,-537 +-560,-462,847 +-464,524,743 +-637,-635,812 +505,325,866 +766,-481,778 +-475,763,-295 +-343,554,742 +-559,-562,928 +-363,493,860 +700,-557,850 + +--- scanner 25 --- +-360,517,826 +-696,281,-570 +603,-630,-328 +398,826,514 +-72,20,78 +-595,-629,-756 +-679,373,-723 +751,693,-833 +-491,-582,706 +781,741,-640 +481,-719,-304 +716,724,-779 +365,-769,828 +-534,-518,-740 +335,-670,720 +99,8,-67 +317,-720,743 +-721,308,-595 +-475,601,892 +-366,-644,679 +486,-659,-306 +-465,-632,569 +321,790,439 +-402,694,844 +-541,-579,-648 +372,686,539 + +--- scanner 26 --- +-644,-564,-581 +-78,-46,-124 +746,-537,581 +679,-547,-661 +341,710,-518 +-514,-868,621 +651,701,772 +-691,362,751 +807,-504,507 +-636,583,-730 +-539,692,-708 +-719,558,799 +-548,-868,567 +-695,644,-687 +665,-529,-630 +690,718,688 +-590,-579,-484 +-663,-515,-616 +-689,337,811 +300,522,-459 +837,-417,597 +-505,-920,537 +316,646,-490 +737,-506,-663 +624,552,672 + +--- scanner 27 --- +-485,-881,-896 +-662,-839,-914 +611,-700,578 +149,-77,-47 +922,661,522 +-360,475,736 +-690,627,-723 +-335,477,796 +870,652,606 +-569,-766,-962 +664,-776,-639 +517,503,-631 +661,-646,686 +550,-707,670 +-276,-520,525 +-581,530,-745 +-249,-545,500 +581,576,-499 +676,-875,-749 +-642,471,-702 +614,-750,-776 +-341,-562,653 +-31,-55,-158 +-556,447,784 +870,618,552 +566,522,-596 + +--- scanner 28 --- +537,-616,-435 +403,497,789 +-734,976,683 +363,-484,745 +-758,-554,-727 +-701,-382,724 +419,605,-563 +393,742,-513 +378,-561,-443 +631,-541,-453 +-437,483,-376 +-103,105,28 +-808,-619,-628 +-637,950,832 +-389,568,-425 +380,-348,803 +433,620,671 +-554,-468,688 +-407,591,-475 +-727,947,666 +484,422,716 +450,-304,752 +294,632,-501 +-809,-548,-770 +-599,-363,804 + +--- scanner 29 --- +416,-491,827 +-403,-379,-560 +-420,-665,528 +-735,829,-657 +469,699,586 +70,37,-13 +474,-452,901 +-363,-501,578 +-379,809,822 +-455,-322,-419 +-401,817,805 +576,664,-334 +-773,839,-622 +453,553,614 +-459,-473,-500 +619,505,-259 +-712,786,-532 +715,-713,-664 +627,599,-366 +-95,-46,95 +-494,757,862 +457,645,788 +-472,-594,656 +812,-716,-773 +446,-562,884 +750,-569,-730 + +--- scanner 30 --- +-647,-426,-938 +-860,-733,501 +574,-687,514 +585,-616,682 +-42,57,-114 +-646,444,613 +521,512,511 +-628,360,-435 +-787,378,617 +429,562,430 +-597,282,-581 +834,849,-599 +-718,494,604 +752,-392,-623 +557,574,389 +651,-718,696 +-851,-730,607 +-512,429,-524 +-832,-413,-884 +751,-427,-488 +-752,-761,587 +865,833,-786 +-17,-118,12 +704,-385,-606 +901,835,-615 +-659,-490,-846 + +--- scanner 31 --- +836,-615,-464 +-771,679,586 +-424,-320,450 +768,-856,848 +549,430,-434 +804,-557,-333 +558,555,-331 +532,596,-446 +-605,-583,-478 +18,16,-2 +-510,869,-324 +-522,697,-398 +465,910,698 +-584,-541,-690 +-366,-465,370 +-463,885,-363 +442,769,719 +-726,-509,-572 +900,-504,-440 +745,-834,885 +873,-804,817 +432,914,739 +-425,-355,387 +-811,658,799 +-689,617,705 + +--- scanner 32 --- +-381,-530,548 +-619,-781,-721 +860,415,575 +45,-33,-11 +-40,124,57 +-642,380,358 +709,658,-482 +552,761,-482 +-643,560,-540 +-689,419,342 +632,627,-484 +806,517,633 +778,-429,-380 +-630,454,530 +480,-315,880 +-341,-743,569 +-647,479,-393 +-729,-709,-800 +838,598,572 +-610,-647,-729 +643,-428,-345 +-463,-649,610 +660,-476,-338 +667,-346,896 +-664,620,-466 +651,-279,882 + +--- scanner 33 --- +-81,29,111 +639,-815,-688 +664,-497,366 +-620,623,686 +-407,651,-441 +-383,610,-675 +284,832,-400 +-733,-571,888 +574,770,671 +-689,-396,-337 +-783,-402,824 +-651,-294,-463 +521,-799,-600 +-429,682,-517 +576,-821,-511 +711,-603,468 +684,-585,376 +-644,-458,-481 +-780,-486,894 +-548,705,686 +418,766,758 +316,790,-526 +579,774,846 +-525,576,739 +320,835,-494 + +--- scanner 34 --- +709,-623,-800 +618,-691,646 +664,618,671 +-542,704,-886 +-941,-740,636 +-655,-650,-435 +680,-691,-803 +-772,-679,-413 +-937,770,332 +-923,-690,613 +-886,666,432 +41,-133,-56 +688,596,648 +-893,-789,721 +-860,806,407 +-507,673,-940 +705,618,606 +750,-682,-769 +672,772,-925 +-109,-42,-127 +588,-819,645 +731,662,-942 +-777,-739,-411 +673,807,-862 +-477,721,-747 +743,-718,608 + +--- scanner 35 --- +437,680,-609 +-66,-30,0 +455,-616,-602 +-601,-822,-631 +-387,658,-849 +345,-491,357 +511,659,-669 +453,-693,-571 +364,663,-750 +-559,646,-775 +-852,788,661 +407,348,463 +-906,875,779 +350,428,557 +489,353,491 +-510,-480,509 +-875,697,692 +390,-552,432 +377,-591,394 +-353,-410,470 +-434,-474,366 +453,-536,-468 +-662,-790,-712 +-604,-844,-814 +-371,705,-810 + +--- scanner 36 --- +-426,485,-390 +-615,-449,-336 +-148,-62,57 +-378,356,-274 +614,664,523 +547,837,547 +604,-896,648 +469,-434,-551 +620,785,629 +519,-381,-739 +-620,411,803 +642,616,-300 +-681,431,921 +-650,532,804 +14,-121,179 +-849,-437,927 +681,481,-421 +450,-348,-623 +-870,-642,927 +45,66,33 +804,-870,699 +-847,-620,902 +796,-914,680 +-411,543,-234 +696,644,-445 +-511,-602,-336 +-415,-482,-321 diff --git a/day19.clj b/day19.clj new file mode 100644 index 0000000..9465025 --- /dev/null +++ b/day19.clj @@ -0,0 +1,94 @@ +(ns org.vuxu.aoc2021.day19 + (:require [clojure.string :as str] + [clojure.set :as set])) + +(def data + (for [scanner (str/split (slurp "day19") #"\n\n")] + (->> (str/split-lines scanner) + (drop 1) + (map #(str/split % #",")) + (mapv (partial mapv parse-long))))) + +(def axes [[0 1 0] [0 -1 0] [1 0 0] [-1 0 0] [0 0 1] [0 0 -1]]) + +(defn transform [[x y z] up rot] + (let [[rx ry rz] (case up + [ 0 1 0] [x y z] + [ 0 -1 0] [x (- y) (- z)] + [ 1 0 0] [y x (- z)] + [-1 0 0] [y (- x) z] + [ 0 0 1] [y z x] + [ 0 0 -1] [y (- z) (- x)])] + (case rot + 0 [rx ry rz] + 1 [rz ry (- rx)] + 2 [(- rx) ry (- rz)] + 3 [(- rz) ry rx]))) + +(defn translate [p v] + (mapv + p v)) + +(defn diff [v1 v2] + (mapv - v1 v2)) + +(defn align [beacons1 beacons2] + (first + (for [axis axes + rotation (range 4) + :let [rotated-beacons2 (map #(transform % axis rotation) beacons2)] + b1 beacons1 + matching-b1-in-b2 rotated-beacons2 + :let [delta (diff b1 matching-b1-in-b2) + transformed-beacons2 (set (map #(translate % delta) rotated-beacons2)) + intersection (set/intersection transformed-beacons2 beacons1)] + :when (>= (count intersection) 12)] + [transformed-beacons2 delta axis rotation]))) + +(defn reduc [scans scanners] + (let [[to-remove scans scanners] + (loop [to-remove #{} + scans scans + scanners scanners + i 0 + j 1] + (prn [i j]) + (if (>= i (dec (count scans))) + [to-remove scans scanners] + (if (>= j (count scans)) + (recur to-remove scans scanners (inc i) (+ i 2)) + (if (to-remove j) + (recur to-remove scans scanners i (inc j)) + + (if-let [[agt trs up rot] (align (scans i) (scans j))] + (recur (conj to-remove j) + (update scans i set/union agt) + (update scanners i set/union + (set (map #(translate trs (transform % up rot)) (scanners j)))) + i + (inc j)) + (recur to-remove scans scanners i (inc j)))))))] + [(vec (keep-indexed #(when (not (to-remove %1)) %2) scans)) + (vec (keep-indexed #(when (not (to-remove %1)) %2) scanners))])) + +;; very slow :/ +(def reducd + (loop [[scans scanners] + [(mapv set data) (mapv (constantly #{[0 0 0]}) data)]] + (if (> (count scans) 1) + (recur (reduc scans scanners)) + [(first scans) + (first scanners)]))) + +(def part1 + (count (first reducd))) +;; => 445 + +(defn manhattan [a b] + (apply + (map #(Math/abs %) (diff a b)))) + +(def part2 + (apply max + (for [b1 (second reducd) + b2 (second reducd)] + (manhattan b1 b2)))) +;; => 13225 -- cgit 1.4.1