From 381c8a19daa4196195b8dd4b0ab032b92fd57e28 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Sun, 19 Dec 2021 21:50:59 +0200 Subject: Day 19 --- inputs/day_19.txt | 856 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/day_19.rs | 223 ++++++++++++++ 2 files changed, 1079 insertions(+) create mode 100644 inputs/day_19.txt create mode 100644 src/bin/day_19.rs diff --git a/inputs/day_19.txt b/inputs/day_19.txt new file mode 100644 index 0000000..e2f977f --- /dev/null +++ b/inputs/day_19.txt @@ -0,0 +1,856 @@ +--- scanner 0 --- +785,-772,752 +548,703,908 +571,658,844 +-654,-601,-321 +509,339,-583 +113,-24,5 +-685,476,-691 +-573,-837,487 +667,-785,773 +417,248,-660 +567,-853,-801 +531,655,675 +543,245,-584 +-569,714,648 +520,-824,-758 +-551,613,646 +-6,-155,84 +-645,452,-613 +-665,-681,-424 +-624,-798,555 +763,-844,821 +-455,763,640 +-583,-753,-380 +382,-897,-773 +-550,444,-612 +-567,-808,562 + +--- scanner 1 --- +-762,-848,417 +-470,575,-597 +510,-362,658 +-452,659,-532 +-951,675,325 +650,413,654 +653,-412,637 +-847,-836,444 +525,-542,600 +-952,-828,466 +-534,-483,-635 +263,625,-879 +487,-833,-665 +-478,-438,-584 +-58,30,-29 +494,-775,-599 +576,364,635 +283,615,-897 +-505,-387,-655 +-450,583,-662 +289,498,-824 +-955,537,301 +609,384,498 +505,-724,-559 +-929,545,377 + +--- scanner 2 --- +-4,133,0 +409,846,-912 +511,-669,287 +-727,-315,505 +397,674,-855 +-391,-664,-755 +455,-676,267 +-681,708,805 +-534,702,800 +-840,-409,440 +-455,-619,-732 +544,867,356 +469,-702,368 +391,832,420 +-624,-616,-772 +-547,811,-518 +410,-260,-715 +429,-224,-632 +397,616,-957 +-814,-307,456 +534,-227,-752 +-478,883,-540 +-528,703,707 +-526,824,-636 +509,845,344 + +--- scanner 3 --- +900,-493,416 +-792,754,522 +-424,262,-635 +-368,454,-613 +-746,-725,-569 +-752,649,599 +456,-364,-590 +-446,-588,509 +-634,-755,-694 +839,573,-420 +-749,645,413 +690,673,-399 +569,-382,-585 +-725,-651,-724 +-563,-606,561 +-516,-779,510 +804,717,-336 +845,465,483 +-362,321,-724 +772,-525,555 +406,-491,-567 +37,-7,32 +687,484,510 +821,-464,374 +751,405,481 + +--- scanner 4 --- +-540,515,741 +856,756,328 +562,-779,560 +797,612,394 +482,-908,548 +-585,-571,-807 +709,770,412 +-478,433,677 +-549,-545,527 +521,-609,-513 +-505,-521,-879 +-461,-510,-902 +-337,-612,537 +-32,43,-140 +644,-634,-445 +-550,533,700 +766,728,-558 +-14,-68,35 +814,686,-634 +-712,690,-680 +781,596,-529 +676,-895,583 +559,-558,-534 +-789,611,-631 +-464,-655,596 +-718,530,-751 + +--- scanner 5 --- +619,-451,-778 +-517,534,-801 +-617,683,-780 +-379,406,390 +423,-502,-802 +-704,-496,482 +-69,-98,-19 +485,767,293 +470,695,473 +-473,648,-864 +573,771,459 +-389,301,412 +-720,-612,534 +445,-434,-848 +532,321,-712 +-364,382,382 +-618,-586,385 +520,288,-704 +-869,-518,-476 +725,-500,380 +-736,-524,-587 +-928,-580,-565 +614,471,-707 +779,-495,407 +671,-428,522 + +--- scanner 6 --- +-665,672,665 +-565,744,642 +-933,-475,-523 +389,717,-914 +254,-687,-701 +523,758,561 +-662,504,-786 +468,-298,310 +480,885,502 +-960,-354,-558 +234,-687,-751 +439,637,-842 +-173,107,-115 +-647,682,706 +260,-481,-766 +413,673,492 +11,-28,-159 +418,-340,447 +369,-299,251 +-736,-356,408 +-727,-524,477 +378,761,-937 +-904,-282,-562 +-743,433,-666 +-684,-386,371 +-822,510,-715 + +--- scanner 7 --- +465,801,-361 +-583,551,482 +-521,633,546 +-593,533,523 +434,583,-327 +-451,-805,455 +-611,-835,-355 +666,296,811 +-574,648,-470 +30,-123,175 +-119,-152,-16 +439,-652,399 +436,-717,520 +813,310,895 +413,670,-390 +-618,484,-380 +-515,-704,545 +406,-557,567 +-581,-804,602 +754,454,829 +-765,-854,-475 +573,-842,-568 +-827,-846,-405 +718,-754,-533 +497,-753,-472 +-626,481,-462 + +--- scanner 8 --- +-834,731,729 +-579,282,-466 +-376,-761,734 +655,-969,-550 +641,575,492 +-789,667,706 +722,-978,710 +-530,-683,-261 +654,596,610 +693,-935,757 +538,441,-831 +-124,-92,62 +532,588,-826 +-477,308,-482 +-448,-778,-293 +-470,-760,768 +-379,-837,860 +-475,-627,-288 +-485,395,-531 +-786,498,746 +713,644,514 +719,-888,-497 +533,594,-733 +766,-950,895 +743,-966,-388 + +--- scanner 9 --- +374,-543,718 +-699,-584,548 +-401,-360,-681 +-666,527,782 +-147,-126,155 +695,385,-533 +-735,442,672 +763,439,817 +395,-581,769 +-676,315,715 +668,563,756 +808,-860,-376 +-438,-462,-763 +740,483,806 +-577,779,-632 +784,-767,-244 +797,-770,-315 +-564,834,-466 +-435,-398,-748 +-687,-504,419 +-12,-91,-12 +662,477,-577 +-592,758,-411 +306,-666,693 +-722,-698,432 +620,459,-474 + +--- scanner 10 --- +-57,48,-5 +507,768,-684 +490,702,-604 +517,-605,-365 +-442,-603,-255 +-812,583,625 +692,-604,914 +369,691,-619 +486,386,918 +-476,-772,765 +537,-625,-311 +353,-589,-374 +-896,597,781 +-904,615,790 +-358,-698,669 +-511,-531,-348 +-499,749,-395 +-332,-694,727 +624,-745,922 +398,356,966 +654,-852,912 +452,403,810 +-467,856,-399 +-477,-661,-349 +38,-3,171 +-428,739,-376 + +--- scanner 11 --- +709,533,-849 +-495,-544,650 +-488,600,604 +736,464,642 +-462,762,641 +-325,776,-552 +153,177,47 +-505,-304,-506 +-423,591,584 +853,499,615 +540,-737,-707 +54,23,-83 +756,-686,346 +-574,-217,-397 +808,608,647 +-412,839,-613 +-489,-491,547 +716,-646,426 +-505,-414,-420 +834,555,-697 +-518,-470,473 +800,-801,448 +683,420,-707 +471,-645,-649 +572,-781,-675 +-282,894,-529 + +--- scanner 12 --- +-438,505,-689 +630,785,420 +-391,-486,434 +645,789,392 +-436,452,649 +402,-547,-680 +37,27,31 +579,865,382 +-460,493,-724 +818,609,-455 +-599,491,705 +-567,-453,350 +858,631,-541 +354,-422,756 +-689,-808,-836 +-442,-405,279 +760,549,-435 +407,-440,640 +-631,-706,-836 +-459,-763,-824 +344,-643,-802 +-508,546,645 +393,-433,644 +87,142,-114 +332,-520,-754 +-473,569,-842 + +--- scanner 13 --- +-830,923,434 +-517,-584,-423 +526,-422,-325 +-820,786,372 +440,701,541 +-740,-600,715 +-884,499,-539 +597,-679,703 +358,548,-251 +-727,442,-487 +697,-656,775 +-741,-747,845 +302,544,-323 +-704,-546,-468 +535,-491,-493 +-640,-585,-311 +-909,441,-436 +329,509,-444 +-758,792,378 +-640,-657,781 +-53,73,94 +578,-385,-355 +615,-720,713 +519,652,464 +600,772,535 + +--- scanner 14 --- +574,-540,704 +285,381,-354 +515,-466,779 +300,317,-351 +471,-558,746 +733,689,881 +-554,416,557 +416,-860,-493 +804,686,868 +367,279,-317 +582,-915,-480 +13,37,-48 +-390,-407,604 +-590,513,-476 +-512,-378,568 +672,779,892 +-491,-464,-576 +-478,413,641 +-551,-420,687 +-508,525,647 +-672,399,-455 +-153,-91,69 +-406,-483,-711 +-675,542,-562 +637,-839,-508 +-516,-428,-610 + +--- scanner 15 --- +-654,605,-887 +290,437,636 +-681,722,-852 +449,-680,271 +-2,-62,-147 +-655,-593,-589 +478,505,-851 +596,-674,276 +259,-587,-558 +396,-562,-499 +316,335,620 +364,504,-669 +-675,388,841 +-880,-861,605 +-619,333,814 +-692,-619,-751 +339,474,-774 +-712,-554,-760 +-961,-797,552 +-958,-885,714 +-770,306,809 +602,-675,369 +-144,-143,-11 +341,-570,-441 +-649,677,-743 +403,343,571 + +--- scanner 16 --- +-692,-623,449 +543,-617,-551 +784,-472,679 +560,-738,-414 +803,723,736 +-868,-717,-800 +-756,-686,376 +-6,81,-80 +-528,436,506 +772,951,-366 +695,860,-458 +696,954,-492 +724,755,601 +80,-14,78 +-732,541,-520 +514,-735,-636 +-625,-757,393 +-833,-698,-600 +-534,586,602 +-796,496,-497 +-843,-726,-747 +-536,485,620 +-563,544,-480 +725,747,696 +739,-536,621 +630,-507,673 + +--- scanner 17 --- +-754,753,-378 +-683,-534,-954 +533,-622,603 +498,403,-673 +-907,673,-415 +811,-522,-627 +650,-422,-612 +-703,732,237 +569,491,723 +526,405,-595 +366,476,-633 +584,549,543 +-724,652,-426 +535,-770,576 +-880,-851,629 +-907,-681,559 +-680,-511,-926 +454,-669,691 +1,38,-78 +-823,-796,553 +-578,-470,-910 +799,-467,-509 +-893,683,257 +712,512,673 +-788,705,249 + +--- scanner 18 --- +-844,226,329 +602,395,686 +478,-694,534 +-348,-651,505 +-613,490,-691 +348,-738,-528 +99,-39,-2 +368,-688,-528 +-469,-664,619 +-819,-510,-740 +-790,-549,-933 +-605,-684,511 +582,323,-917 +-821,433,267 +465,-566,523 +483,264,-916 +-846,-545,-861 +532,460,-875 +-716,303,258 +-622,421,-859 +579,362,756 +-50,-119,-96 +-570,384,-829 +625,314,789 +545,-638,566 +374,-753,-734 + +--- scanner 19 --- +878,378,296 +-797,-402,-756 +718,453,-561 +862,-402,-635 +-789,-416,-632 +-580,-705,635 +-512,590,-477 +-786,752,516 +-487,713,-545 +-436,675,-566 +845,-482,-688 +-773,558,551 +808,420,-666 +-679,-738,771 +734,437,362 +962,-292,489 +-23,-11,11 +865,-472,-504 +892,525,380 +-737,-513,-660 +767,-284,520 +-657,672,528 +841,-333,477 +162,-53,-105 +850,468,-590 +-697,-659,753 + +--- scanner 20 --- +557,-760,464 +-477,-322,-599 +525,781,-733 +-396,-771,757 +-418,-697,598 +-517,-468,-611 +467,781,-835 +697,769,-790 +714,-334,-432 +765,-489,-513 +-115,33,18 +718,634,478 +-409,768,-593 +-376,644,-630 +-373,749,-510 +696,669,466 +-818,667,409 +-471,-462,-594 +40,-70,140 +683,787,542 +-825,723,389 +589,-405,-480 +-851,709,490 +648,-700,519 +-440,-600,673 +720,-704,425 + +--- scanner 21 --- +748,-630,-477 +545,-599,511 +834,985,537 +887,764,-454 +-703,755,410 +-650,656,-642 +879,715,-541 +-555,-682,-789 +617,-743,516 +-462,-670,549 +916,953,632 +-669,973,441 +-568,653,-650 +-497,-582,694 +-625,-674,-851 +717,-707,-616 +889,958,481 +100,41,-32 +718,-525,-502 +-675,-663,-635 +-560,820,-598 +-640,842,389 +785,780,-428 +-558,-581,473 +500,-708,543 + +--- scanner 22 --- +791,545,-530 +816,515,-425 +896,-546,-641 +-417,694,544 +-399,436,-637 +379,650,683 +670,-910,856 +759,-521,-700 +-833,-911,715 +359,617,546 +-367,551,523 +-461,-898,-819 +-853,-721,764 +408,691,527 +6,59,88 +-514,517,-738 +-537,-841,-764 +814,-529,-758 +677,546,-348 +-29,-122,-30 +532,-914,880 +-531,-925,-649 +-547,566,581 +-841,-806,737 +-487,515,-590 +540,-888,804 + +--- scanner 23 --- +-600,-462,-505 +969,676,350 +539,367,-688 +-757,638,-532 +659,-710,231 +589,-880,258 +420,-428,-674 +-404,819,242 +476,551,-652 +-504,-344,-579 +-747,668,-425 +981,703,435 +-768,-702,610 +514,-463,-616 +-412,743,268 +-749,706,-673 +961,654,245 +-562,-318,-583 +513,-497,-746 +106,77,-23 +-631,-761,635 +-686,-819,627 +-542,795,246 +665,-825,315 +530,531,-672 + +--- scanner 24 --- +-319,-979,-426 +-664,465,584 +-793,385,596 +-430,-646,617 +885,612,732 +-705,449,-405 +-372,-954,-417 +511,359,-469 +727,700,750 +533,-628,-549 +548,-575,467 +648,-647,444 +380,411,-440 +630,-637,403 +598,380,-406 +700,-680,-541 +-780,579,561 +871,759,816 +6,-30,-98 +-568,432,-526 +697,-672,-459 +-540,-561,548 +-497,-434,607 +-483,403,-408 +-519,-944,-445 +124,-106,71 + +--- scanner 25 --- +794,-593,-715 +-657,696,404 +-560,621,382 +743,-397,-739 +-789,-588,481 +659,644,448 +-852,-457,-625 +665,954,-502 +817,-645,585 +-132,31,-22 +749,730,545 +52,-21,55 +811,-419,-785 +-935,-576,441 +745,-699,443 +721,762,-524 +-497,487,-593 +750,-753,470 +633,746,597 +727,895,-413 +-923,-409,-750 +-486,780,360 +-768,-490,-801 +-557,542,-684 +-553,448,-756 +-795,-571,435 + +--- scanner 26 --- +-716,663,621 +-706,477,-410 +823,361,-502 +-749,-353,928 +-770,-739,-500 +768,334,-558 +821,555,433 +-767,-517,-454 +-649,-602,-483 +464,-656,856 +922,-661,-636 +70,56,10 +-634,666,629 +-730,-553,893 +919,-787,-712 +-769,564,-431 +-626,499,577 +512,-673,623 +-758,-406,903 +850,366,-653 +-735,346,-462 +813,604,520 +828,-695,-635 +719,539,407 +509,-633,792 + +--- scanner 27 --- +-781,-794,775 +523,883,-452 +491,838,-561 +-497,635,-530 +497,-432,-715 +-773,-768,699 +534,-458,-553 +690,830,848 +-417,-426,-746 +-905,811,422 +712,746,693 +-643,-790,751 +-954,737,441 +17,148,31 +591,-459,538 +-499,-409,-863 +665,-488,517 +-119,39,-120 +-522,665,-635 +-636,666,-453 +496,766,-417 +488,-465,591 +-934,770,578 +-554,-401,-805 +554,-393,-544 +792,786,733 + +--- scanner 28 --- +875,474,732 +751,669,-640 +-354,949,-878 +-553,986,-871 +567,-363,592 +894,-337,-815 +-322,-415,-682 +786,-364,-722 +679,761,-750 +-346,603,885 +-375,-418,576 +492,-334,586 +-419,-490,494 +902,-282,-642 +560,-373,535 +702,557,-769 +17,32,-102 +-309,425,877 +-335,-280,-784 +-417,563,824 +-328,-250,-663 +106,126,67 +815,410,807 +-316,-570,505 +823,424,663 +-456,959,-777 + +--- scanner 29 --- +-741,-481,-792 +-625,503,-421 +431,449,245 +585,319,-378 +460,-572,554 +-482,-517,538 +512,336,-367 +-738,270,467 +-790,320,398 +-574,543,-588 +504,-644,636 +-693,-540,-696 +881,-472,-596 +564,370,-525 +401,-724,625 +-730,256,323 +853,-428,-411 +-672,-553,-814 +-475,-527,595 +502,409,306 +-23,-53,-119 +-407,-488,544 +-595,419,-588 +838,-501,-549 +394,271,253 + +--- scanner 30 --- +850,573,-382 +-386,-445,574 +810,650,-487 +807,464,-491 +425,667,659 +631,651,711 +353,-371,673 +-781,-369,-563 +-746,-285,-419 +-771,932,682 +-632,-348,-463 +-629,561,-652 +336,-301,499 +-419,-437,586 +426,-562,-682 +482,-584,-874 +-3,40,-88 +-85,187,75 +-693,532,-731 +-569,-442,668 +-787,534,-671 +-699,946,479 +-671,944,575 +404,-347,477 +504,638,724 +420,-673,-815 diff --git a/src/bin/day_19.rs b/src/bin/day_19.rs new file mode 100644 index 0000000..3fd8291 --- /dev/null +++ b/src/bin/day_19.rs @@ -0,0 +1,223 @@ +use nom::{ + bytes::complete::tag, + character::complete::{char as nom_char, i32 as nom_i32, line_ending, not_line_ending}, + combinator::map, + multi::{many1, separated_list1}, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeSet, fs}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_19.txt")?; + let mut scanner_data = parse_scanner_cloud(&input).unwrap().1; + scanner_data.align_scanners(); + let beacons = scanner_data.combine_beacons(); + dbg!(&beacons.len()); + dbg!(scanner_data.max_aligned_sensor_distance()); + Ok(()) +} + +#[derive(Default, Debug)] +struct ScannerCloud { + aligned_scanners: Vec, + aligned_checking_for_neighbours_scanners: Vec, + unaligned_scanners: Vec, +} + +impl ScannerCloud { + fn new(mut scanners: Vec) -> ScannerCloud { + if let Some(first_aligned_scanner) = scanners.pop() { + ScannerCloud { + aligned_scanners: Vec::new(), + aligned_checking_for_neighbours_scanners: vec![first_aligned_scanner], + unaligned_scanners: scanners, + } + } else { + ScannerCloud::default() + } + } + + fn align_scanners(&mut self) { + while let Some(current_aligned_scanner) = + self.aligned_checking_for_neighbours_scanners.pop() + { + let mut to_remove_indices = Vec::new(); + for i in 0..self.unaligned_scanners.len() { + if let Some(aligned) = + self.unaligned_scanners[i].try_align_with(¤t_aligned_scanner) + { + to_remove_indices.push(i); + self.aligned_checking_for_neighbours_scanners.push(aligned); + } + } + for i in to_remove_indices.into_iter().rev() { + self.unaligned_scanners.remove(i); + } + + self.aligned_scanners.push(current_aligned_scanner); + } + + assert_eq!( + self.unaligned_scanners.len(), + 0, + "Not all scanners were aligned" + ); + assert_eq!( + self.aligned_checking_for_neighbours_scanners.len(), + 0, + "Not all aligned scanners were processed" + ); + } + + fn combine_beacons(&self) -> BTreeSet { + let mut combined_beacons = BTreeSet::new(); + for scanner in &self.aligned_scanners { + combined_beacons.append(&mut scanner.beacons.clone()) + } + combined_beacons + } + + fn max_aligned_sensor_distance(&self) -> i32 { + let mut max_distance = 0; + for a in &self.aligned_scanners { + for b in &self.aligned_scanners { + let distance = a.position.manhattan_distance(&b.position); + if distance > max_distance { + max_distance = distance; + } + } + } + max_distance + } +} + +#[derive(Debug, Clone)] +struct Scanner { + position: Point, + beacons: BTreeSet, +} + +impl Scanner { + fn try_align_with(&self, other: &Scanner) -> Option { + for (roll, pitch) in [(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (0, 3)] { + for yaw in [0, 1, 2, 3] { + let candidate = self.spin(roll, pitch, yaw); + for candidate_position in candidate.beacons.iter() { + for other_position in other.beacons.iter() { + let aligned_candidate = + candidate.position(*other_position - *candidate_position); + if aligned_candidate.count_overlap(other) >= 12 { + return Some(aligned_candidate); + } + } + } + } + } + None + } + + fn spin(&self, roll: u8, pitch: u8, yaw: u8) -> Scanner { + let beacons = self + .beacons + .clone() + .into_iter() + .map(|mut beacon| { + for _ in 0..roll { + beacon = beacon.roll(); + } + beacon + }) + .map(|mut beacon| { + for _ in 0..pitch { + beacon = beacon.pitch(); + } + beacon + }) + .map(|mut beacon| { + for _ in 0..yaw { + beacon = beacon.yaw(); + } + beacon + }) + .collect(); + Scanner { + position: self.position, // this is wrong, but doesn't matter because we spin then position + beacons, + } + } + + fn position(&self, offset: Point) -> Scanner { + Scanner { + position: self.position + offset, + beacons: self.beacons.iter().map(|b| *b + offset).collect(), + } + } + + fn count_overlap(&self, other: &Scanner) -> usize { + self.beacons.intersection(&other.beacons).count() + } +} + +#[derive( + Debug, Default, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, derive_more::Sub, derive_more::Add, +)] +struct Point { + x: i32, + y: i32, + z: i32, +} + +impl Point { + fn roll(self) -> Self { + Point { + x: self.x, + y: self.z, + z: -self.y, + } + } + + fn pitch(self) -> Self { + Point { + x: -self.z, + y: self.y, + z: self.x, + } + } + + fn yaw(self) -> Self { + Point { + x: -self.y, + y: self.x, + z: self.z, + } + } + + fn manhattan_distance(&self, other: &Point) -> i32 { + (self.x - other.x).abs() + (self.y - other.y).abs() + (self.z - other.z).abs() + } +} + +fn parse_scanner_cloud(input: &str) -> IResult<&str, ScannerCloud> { + map( + separated_list1(many1(line_ending), parse_scanner), + ScannerCloud::new, + )(input) +} + +fn parse_scanner(input: &str) -> IResult<&str, Scanner> { + let (input, _) = tuple((tag("--- scanner"), not_line_ending, line_ending))(input)?; + map(separated_list1(line_ending, parse_point), |beacons| { + Scanner { + position: Point::default(), + beacons: beacons.into_iter().collect(), + } + })(input) +} + +fn parse_point(input: &str) -> IResult<&str, Point> { + map( + tuple((nom_i32, nom_char(','), nom_i32, nom_char(','), nom_i32)), + |(x, _, y, _, z)| Point { x, y, z }, + )(input) +} -- cgit v1.2.3