From 46dbae56862f6abf10d48b543a7eb2114dd0c7b4 Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Mon, 20 Dec 2021 01:06:38 -0500 Subject: day 19 --- data/2021/19.txt | 832 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/2021/19/mod.rs | 303 +++++++++++++++++++ src/2021/mod.rs | 4 + 3 files changed, 1139 insertions(+) create mode 100644 data/2021/19.txt create mode 100644 src/2021/19/mod.rs diff --git a/data/2021/19.txt b/data/2021/19.txt new file mode 100644 index 0000000..d423970 --- /dev/null +++ b/data/2021/19.txt @@ -0,0 +1,832 @@ +--- scanner 0 --- +-880,-557,778 +-611,290,670 +598,502,694 +627,-521,631 +-908,-626,915 +-667,517,-416 +653,-608,742 +619,-567,601 +-541,508,-276 +-573,475,-350 +616,389,617 +658,483,734 +-501,223,776 +-92,5,101 +-966,-685,-334 +310,-833,-657 +-879,-602,773 +472,-843,-557 +472,-871,-567 +-510,239,817 +-861,-803,-266 +783,524,-377 +-878,-591,-260 +815,640,-317 +-16,-141,-1 +657,597,-394 + +--- scanner 1 --- +-342,623,-335 +437,-326,644 +-751,454,509 +748,716,528 +-785,566,599 +53,-5,-74 +513,-321,703 +-749,-226,-474 +588,626,-626 +-20,119,90 +524,-325,650 +-639,-293,-580 +-436,-750,548 +669,671,572 +-370,554,-472 +-371,599,-477 +528,523,-532 +503,-433,-410 +486,-567,-427 +-541,-724,467 +-433,-711,594 +-689,495,689 +519,-502,-310 +655,503,-676 +-740,-242,-433 +728,797,546 + +--- scanner 2 --- +-447,446,-705 +623,695,-536 +-532,-388,322 +349,542,589 +-467,590,-578 +-498,650,320 +761,-419,-459 +298,689,690 +-543,645,321 +534,-478,627 +-93,-60,24 +-570,496,-638 +282,648,699 +48,-137,-88 +567,-404,659 +-567,787,292 +810,-519,-397 +-618,-568,-794 +576,-544,533 +558,812,-569 +489,712,-553 +-744,-394,339 +-625,-611,-753 +819,-575,-440 +-569,-592,-825 +-626,-462,234 + +--- scanner 3 --- +339,-815,388 +-500,420,-617 +-495,-671,-609 +-526,333,-506 +-370,-712,502 +719,347,-563 +787,-838,-639 +716,250,670 +-338,-828,442 +717,335,667 +-681,683,692 +-681,655,682 +854,306,-541 +-843,645,782 +-537,-577,-492 +-555,-690,-569 +-496,-785,519 +785,247,-677 +423,-840,474 +329,-909,487 +-534,379,-476 +771,-983,-606 +-33,-41,127 +631,-897,-674 +554,240,687 + +--- scanner 4 --- +-107,-126,10 +-622,461,-286 +-558,-808,-479 +-550,-803,612 +-56,0,159 +557,315,573 +-377,758,630 +-675,-766,-385 +647,411,502 +-661,-777,525 +-598,-748,-498 +552,667,-704 +315,-485,663 +-514,730,561 +502,-533,608 +-519,729,606 +467,349,461 +505,-810,-622 +413,-899,-635 +391,-440,662 +-475,360,-235 +425,559,-717 +506,664,-743 +-691,-769,571 +394,-748,-744 +-516,351,-219 + +--- scanner 5 --- +-738,-555,723 +-662,510,693 +-694,-436,671 +322,-502,799 +-73,73,-94 +-813,-399,-583 +388,-574,840 +-827,-610,-513 +627,856,-730 +-662,414,-785 +346,-644,754 +724,825,401 +-824,-574,-637 +-653,623,561 +-549,414,-712 +464,-365,-561 +503,-392,-428 +-468,436,-812 +676,746,-667 +701,845,-823 +715,834,446 +557,790,356 +520,-310,-383 +-725,561,553 +-741,-497,785 + +--- scanner 6 --- +498,-465,753 +-291,-666,829 +568,-977,-581 +-599,740,826 +708,713,795 +851,686,-818 +-411,-886,-379 +422,-891,-574 +92,-196,0 +441,-978,-422 +-750,631,807 +813,739,714 +816,700,668 +560,-506,573 +-568,438,-378 +-481,-844,-293 +-553,-910,-334 +-389,430,-288 +-5,-12,128 +464,-577,663 +702,614,-783 +-564,308,-288 +-336,-667,905 +-661,618,715 +-384,-612,718 +675,645,-768 + +--- scanner 7 --- +650,-645,583 +-548,631,-805 +631,-833,-572 +645,-597,667 +607,449,671 +-856,723,531 +-159,-19,-111 +673,363,591 +-380,-625,689 +663,473,-639 +-506,792,-879 +-445,-665,687 +-932,-509,-946 +695,-721,-572 +-21,-134,12 +-897,783,484 +553,324,644 +485,498,-648 +-743,740,579 +-762,-575,-965 +736,-825,-707 +-394,-443,661 +-834,-564,-882 +-458,582,-873 +813,-587,573 +580,330,-627 + +--- scanner 8 --- +-535,-646,373 +49,64,7 +712,545,482 +-413,428,-787 +-564,-583,-650 +-502,520,-774 +845,-611,346 +778,-513,-798 +-872,406,510 +490,330,-589 +-564,409,-896 +-33,-62,-155 +320,432,-615 +-543,-676,419 +-546,-660,-537 +776,-475,287 +620,491,492 +762,-546,-943 +-827,330,511 +-504,-543,-631 +710,-589,387 +-509,-535,460 +469,421,-592 +622,-478,-857 +443,548,498 +-779,517,456 + +--- scanner 9 --- +-691,697,-504 +606,-525,-831 +-708,312,884 +604,-422,-859 +-879,-787,632 +-805,-755,599 +582,-530,-757 +-864,331,826 +-672,625,-560 +369,295,745 +394,311,803 +865,-899,630 +-889,-467,-679 +-895,-450,-467 +-715,666,-553 +-764,269,875 +814,-826,548 +-739,-661,641 +669,693,-398 +835,-907,511 +323,329,771 +503,633,-342 +41,-84,54 +459,696,-317 +-821,-362,-561 + +--- scanner 10 --- +700,-673,733 +565,566,545 +-655,-386,666 +-35,27,-40 +-440,-441,-330 +-588,352,-383 +432,723,-488 +-529,-330,581 +-528,-379,-456 +739,-726,613 +280,-566,-837 +-500,-339,-395 +733,545,640 +340,-613,-796 +271,797,-446 +614,-753,667 +-435,429,515 +-383,391,594 +-520,-401,719 +590,557,723 +-488,390,504 +-545,334,-423 +481,791,-398 +-646,448,-404 +323,-661,-683 + +--- scanner 11 --- +-523,667,-763 +-761,-605,298 +553,-663,332 +748,-670,-550 +427,451,-834 +481,495,-926 +-234,733,382 +-234,552,415 +746,522,514 +876,432,518 +140,27,-65 +-561,474,-740 +-537,-491,-834 +-571,597,-800 +754,432,693 +-690,-669,445 +-325,661,340 +491,494,-716 +751,-761,-571 +-547,-647,-812 +444,-682,483 +-740,-625,380 +-476,-528,-761 +725,-659,-401 +566,-571,421 + +--- scanner 12 --- +534,-664,530 +506,566,785 +-651,-482,723 +-531,374,-562 +933,613,-583 +444,-668,400 +-658,400,528 +-749,-896,-575 +535,-821,-794 +-7,-29,73 +-647,251,551 +-534,643,-546 +-559,-571,710 +-749,421,525 +463,684,849 +843,657,-425 +106,-110,-59 +507,776,795 +-670,-633,832 +449,-751,-752 +-673,-941,-574 +490,-679,-818 +-588,551,-556 +888,648,-416 +444,-843,522 +-562,-848,-520 + +--- scanner 13 --- +661,639,-831 +-683,-841,-609 +-555,-518,629 +859,376,374 +-559,681,-427 +713,528,-837 +-711,637,549 +-750,-824,-776 +-401,588,-408 +-477,611,-393 +-606,645,684 +787,387,291 +720,-842,-411 +529,-822,-422 +-655,-918,-710 +-638,-661,617 +-670,533,684 +483,-770,383 +6,-65,-36 +531,-980,377 +502,-841,-406 +755,671,-764 +-460,-686,608 +129,9,74 +957,321,310 +573,-819,451 + +--- scanner 14 --- +538,411,-771 +-675,874,471 +-837,-690,-720 +348,-523,-489 +316,-298,707 +-523,-771,931 +-731,696,526 +-692,829,553 +431,508,964 +-543,-739,767 +499,501,861 +559,425,-605 +414,-293,789 +386,549,964 +363,-287,605 +-413,-702,878 +-636,-698,-697 +414,-514,-578 +-494,434,-684 +-568,527,-695 +-124,-5,130 +-690,-633,-734 +330,-424,-459 +-519,590,-585 +616,362,-777 + +--- scanner 15 --- +-391,431,-743 +592,-436,-482 +-474,-609,-535 +516,-464,478 +706,705,-770 +512,-502,-568 +-7,-73,54 +-789,642,691 +-452,-577,411 +-346,407,-601 +-34,95,-83 +600,-459,526 +732,669,629 +678,679,721 +-699,800,735 +-744,809,726 +893,650,-818 +-305,473,-673 +675,663,452 +-592,-640,462 +817,651,-863 +-422,-653,-654 +610,-296,468 +539,-556,-443 +-360,-656,-596 +-584,-568,524 + +--- scanner 16 --- +711,389,-690 +-640,572,459 +-579,475,-510 +-447,-653,-613 +-587,452,498 +-663,480,-462 +690,-772,542 +633,-758,-703 +-667,518,584 +652,640,633 +576,430,-586 +720,-726,550 +655,-799,-838 +643,462,608 +-569,312,-452 +-501,-663,-705 +576,494,-698 +579,-685,516 +631,545,465 +519,-858,-769 +90,60,61 +-362,-635,879 +-504,-647,-436 +-286,-634,834 +-473,-689,786 + +--- scanner 17 --- +-670,636,302 +433,641,-915 +-454,541,-877 +-590,-680,-722 +-678,601,506 +-31,3,-135 +741,657,647 +467,-357,313 +685,-356,318 +496,-218,-470 +-673,-537,-710 +-465,488,-838 +877,642,566 +448,-428,-476 +-495,-512,-701 +88,176,-48 +538,-379,-544 +-690,-280,617 +-585,672,383 +473,598,-933 +-718,-357,516 +775,649,632 +-785,-374,683 +494,-376,329 +-544,436,-876 +454,699,-819 + +--- scanner 18 --- +484,-782,-326 +-828,475,486 +725,568,651 +-879,557,413 +-467,-815,-419 +-89,-133,-37 +-596,-830,782 +-760,408,-799 +791,526,557 +747,648,-673 +584,-792,-488 +-849,438,405 +824,691,-831 +-618,-932,890 +764,575,-799 +-459,-820,-543 +807,-634,950 +-620,-904,787 +574,-820,-488 +-619,479,-825 +-80,55,77 +881,-540,862 +-435,-841,-339 +875,-752,845 +865,559,525 +-752,370,-817 + +--- scanner 19 --- +278,-537,-508 +-527,901,494 +-98,173,111 +-619,812,507 +-666,-665,425 +-521,788,-749 +-585,935,-820 +-86,41,-48 +245,-556,-553 +-508,750,385 +322,542,-664 +561,768,744 +383,527,-541 +-565,853,-799 +508,-459,843 +-539,-557,412 +361,-358,894 +-620,-662,386 +-710,-796,-605 +484,750,631 +323,514,-585 +444,810,650 +402,-349,910 +-723,-641,-724 +420,-563,-614 +-608,-760,-696 + +--- scanner 20 --- +431,-704,-682 +-147,26,66 +-696,-545,-708 +426,-620,-634 +445,535,-446 +381,535,-558 +-702,-488,-531 +560,610,790 +-848,614,-306 +505,548,698 +-907,478,-375 +536,492,879 +-483,757,852 +-533,901,844 +-807,592,-441 +-477,-539,567 +414,-641,417 +-625,873,822 +-593,-578,691 +464,-627,539 +-28,-46,-73 +340,670,-454 +263,-610,-692 +520,-680,479 +-466,-669,669 +-712,-542,-439 + +--- scanner 21 --- +-266,486,648 +578,-611,-708 +-818,735,-464 +-759,-456,-789 +-691,-545,727 +407,-548,624 +-407,414,606 +496,-666,600 +-706,-562,774 +-278,471,630 +634,761,-544 +747,571,696 +-676,657,-492 +-698,-556,767 +63,-153,67 +807,624,640 +525,774,-558 +626,-676,-624 +624,-631,-871 +-627,-432,-708 +550,778,-542 +-734,-461,-727 +-742,786,-431 +869,585,746 +588,-604,655 + +--- scanner 22 --- +-658,443,-873 +688,-773,-852 +94,86,-43 +365,435,679 +316,-602,678 +-101,19,38 +-343,-416,-420 +-561,407,-825 +-462,383,561 +-405,-615,824 +-359,-493,-424 +-404,-525,719 +-443,-536,772 +636,-689,-733 +749,-675,-833 +372,-687,552 +325,374,707 +387,-740,687 +-564,-448,-433 +623,594,-764 +-348,402,662 +531,670,-784 +629,524,-772 +427,309,767 +65,-103,67 +-684,443,-722 +-366,362,619 + +--- scanner 23 --- +435,-295,689 +376,-489,-751 +-776,528,-600 +756,497,-606 +-659,601,725 +-827,580,630 +342,-579,-639 +426,-366,551 +-413,-413,-550 +-506,-524,-604 +394,425,766 +-833,-691,657 +-684,592,547 +341,464,755 +-794,-638,537 +785,355,-582 +-750,639,-687 +561,-351,604 +-144,111,172 +-458,-337,-549 +289,426,676 +25,-25,67 +438,-669,-710 +-742,669,-641 +-708,-718,603 +757,492,-651 + +--- scanner 24 --- +-111,-95,111 +361,-657,765 +-582,632,729 +505,-558,752 +-589,-581,768 +-530,716,848 +-893,-431,-711 +748,709,611 +-831,683,-691 +657,337,-287 +-853,-492,-683 +-791,-366,-771 +740,-662,-280 +63,-50,-45 +-846,630,-556 +382,-527,879 +737,-458,-369 +819,-451,-281 +656,803,580 +701,756,570 +567,372,-315 +645,506,-298 +-595,-651,760 +-469,618,829 +-902,545,-682 +-687,-727,780 + +--- scanner 25 --- +538,-604,597 +-69,170,-40 +486,-485,641 +424,-543,644 +-475,-696,544 +455,-396,-443 +-800,563,438 +-448,-571,490 +498,456,-351 +688,967,784 +369,-466,-485 +-528,-657,424 +-587,479,-752 +-497,575,-823 +410,-538,-419 +598,939,749 +676,956,615 +650,437,-438 +657,583,-352 +63,30,10 +-677,513,-864 +-753,-276,-663 +-642,-369,-717 +-815,698,491 +-871,572,576 +-829,-321,-662 + +--- scanner 26 --- +603,-662,-789 +921,616,705 +838,688,716 +-837,496,-760 +528,-777,447 +541,-717,-697 +-711,-791,683 +663,-882,455 +-705,248,837 +-627,-796,635 +-733,234,655 +-634,-758,-538 +902,786,771 +485,-686,-878 +117,-22,-80 +528,-841,559 +613,562,-659 +-731,299,615 +-824,482,-651 +-648,-808,-416 +548,646,-707 +-687,-702,-478 +-617,-959,693 +-841,480,-735 +43,-158,54 +568,809,-661 + +--- scanner 27 --- +-688,503,355 +602,-599,627 +633,-605,-905 +638,-650,-906 +666,756,-490 +-8,72,-119 +-707,-336,446 +-789,531,278 +-474,551,-638 +491,-686,601 +461,-640,593 +-400,-616,-904 +-406,-404,-887 +-555,636,-674 +-678,543,-603 +550,631,678 +775,-581,-934 +-697,-364,446 +-855,436,372 +704,677,-438 +705,767,-543 +-191,149,-166 +-474,-522,-992 +538,548,535 +-797,-374,284 +529,726,510 + +--- scanner 28 --- +-713,-683,864 +710,829,-871 +569,-596,779 +888,752,850 +561,-775,869 +-637,-474,-537 +-425,637,-643 +-779,-611,823 +-544,681,380 +-474,747,-706 +126,-94,-57 +88,32,118 +525,-912,-725 +480,-912,-684 +824,634,807 +-598,-501,-404 +653,657,-808 +-755,-753,778 +-400,736,-799 +-581,-419,-359 +632,823,-822 +439,-600,869 +593,-809,-732 +834,844,806 +-386,725,470 +-377,716,425 + +--- scanner 29 --- +423,-939,368 +496,689,481 +907,-613,-518 +-502,-588,597 +492,-886,258 +-442,-468,-499 +-476,281,-751 +680,570,-569 +561,726,535 +-322,-453,-521 +671,481,-503 +-15,4,-8 +-48,-164,-115 +901,-797,-569 +-445,-665,573 +504,712,682 +-417,456,-807 +-398,384,755 +-320,-554,-541 +896,-715,-471 +-557,396,-782 +-571,416,772 +-454,-643,535 +455,-775,388 +770,451,-485 +-477,321,741 diff --git a/src/2021/19/mod.rs b/src/2021/19/mod.rs new file mode 100644 index 0000000..b8a9368 --- /dev/null +++ b/src/2021/19/mod.rs @@ -0,0 +1,303 @@ +#[allow(clippy::type_complexity)] +const ORIENTATIONS: &[&dyn Fn(Point) -> Point] = &[ + &|p| Point::new(p.y, p.z, p.x), + &|p| Point::new(-p.y, -p.z, p.x), + &|p| Point::new(p.z, -p.y, p.x), + &|p| Point::new(-p.z, p.y, p.x), + &|p| Point::new(p.y, -p.z, -p.x), + &|p| Point::new(-p.y, p.z, -p.x), + &|p| Point::new(p.z, p.y, -p.x), + &|p| Point::new(-p.z, -p.y, -p.x), + &|p| Point::new(p.x, -p.z, p.y), + &|p| Point::new(-p.x, p.z, p.y), + &|p| Point::new(p.z, p.x, p.y), + &|p| Point::new(-p.z, -p.x, p.y), + &|p| Point::new(p.x, p.z, -p.y), + &|p| Point::new(-p.x, -p.z, -p.y), + &|p| Point::new(p.z, -p.x, -p.y), + &|p| Point::new(-p.z, p.x, -p.y), + &|p| Point::new(p.x, p.y, p.z), + &|p| Point::new(-p.x, -p.y, p.z), + &|p| Point::new(p.y, -p.x, p.z), + &|p| Point::new(-p.y, p.x, p.z), + &|p| Point::new(p.x, -p.y, -p.z), + &|p| Point::new(-p.x, p.y, -p.z), + &|p| Point::new(p.y, p.x, -p.z), + &|p| Point::new(-p.y, -p.x, -p.z), +]; + +#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq)] +struct Point { + x: i16, + y: i16, + z: i16, +} + +impl Point { + fn new(x: i16, y: i16, z: i16) -> Self { + Self { x, y, z } + } +} + +impl std::ops::Add for Point { + type Output = Point; + fn add(self, other: Point) -> Self::Output { + Point { + x: self.x + other.x, + y: self.y + other.y, + z: self.z + other.z, + } + } +} + +impl std::ops::AddAssign for Point { + fn add_assign(&mut self, other: Point) { + self.x += other.x; + self.y += other.y; + self.z += other.z; + } +} + +impl std::ops::Sub for Point { + type Output = Point; + fn sub(self, other: Point) -> Self::Output { + Point { + x: self.x - other.x, + y: self.y - other.y, + z: self.z - other.z, + } + } +} + +impl std::ops::SubAssign for Point { + fn sub_assign(&mut self, other: Point) { + self.x -= other.x; + self.y -= other.y; + self.z -= other.z; + } +} + +impl std::fmt::Display for Point { + fn fmt( + &self, + f: &mut std::fmt::Formatter<'_>, + ) -> Result<(), std::fmt::Error> { + write!(f, "({},{},{})", self.x, self.y, self.z) + } +} + +#[derive(Debug, Clone)] +struct Scanner { + beacons: Vec, +} + +impl Scanner { + fn parse(lines: &mut impl Iterator) -> Option { + if lines.next().is_some() { + let mut beacons = vec![]; + for line in lines { + if line.is_empty() { + break; + } + let mut parts = line.split(',').map(|i| i.parse().unwrap()); + let x = parts.next().unwrap(); + let y = parts.next().unwrap(); + let z = parts.next().unwrap(); + beacons.push(Point::new(x, y, z)) + } + Some(Self { beacons }) + } else { + None + } + } + + fn matches( + &self, + other: &std::collections::HashSet, + ) -> Option<(usize, Point)> { + for (i, beacons) in self.each_orientation().enumerate() { + let mut offsets = vec![]; + for beacon1 in beacons.clone() { + for beacon2 in other { + offsets.push(*beacon2 - beacon1); + } + } + for offset in offsets { + let set1: std::collections::HashSet<_> = + beacons.iter().map(|beacon| *beacon + offset).collect(); + let matches = set1.intersection(other).count(); + if matches == 0 { + panic!("bug"); + } + if matches >= 12 { + return Some((i, offset)); + } + } + } + None + } + + fn each_orientation(&self) -> impl Iterator> { + let beacons = self.beacons.clone(); + ORIENTATIONS.iter().map(move |orientation| { + beacons.iter().map(|beacon| orientation(*beacon)).collect() + }) + } + + fn at_orientation Point>( + &self, + orientation: F, + offset: Point, + ) -> Self { + Self { + beacons: self + .beacons + .iter() + .map(|beacon| orientation(*beacon) + offset) + .collect(), + } + } +} + +#[derive(Debug)] +pub struct Scan { + scanners: Vec, +} + +impl Scan { + fn parse(mut lines: impl Iterator) -> Self { + let mut scanners = vec![]; + while let Some(scanner) = Scanner::parse(lines.by_ref()) { + scanners.push(scanner); + } + Self { scanners } + } + + fn scanners(&self) -> &[Scanner] { + &self.scanners + } +} + +pub fn parse(fh: std::fs::File) -> anyhow::Result { + Ok(Scan::parse(crate::util::parse::lines(fh))) +} + +pub fn part1(scan: Scan) -> anyhow::Result { + let mut beacons: std::collections::HashSet = + std::collections::HashSet::new(); + let mut skip = None; + for (i, scanner1) in scan.scanners().iter().enumerate() { + for (j, scanner2) in scan.scanners().iter().enumerate().skip(i + 1) { + if let Some((orientation, offset)) = + scanner2.matches(&scanner1.beacons.iter().copied().collect()) + { + let scanner2 = scanner2 + .at_orientation(ORIENTATIONS[orientation], offset); + beacons.extend(scanner1.beacons.iter()); + beacons.extend(scanner2.beacons.iter()); + skip = Some((i, j)); + break; + } + } + if skip.is_some() { + break; + } + } + let skip = skip.unwrap(); + let mut scanners = scan.scanners().to_vec(); + scanners.remove(skip.1); + scanners.remove(skip.0); + + let mut found = None; + loop { + for (i, scanner) in scanners.iter().enumerate() { + if let Some((orientation, offset)) = scanner.matches(&beacons) { + let scanner = + scanner.at_orientation(ORIENTATIONS[orientation], offset); + beacons.extend(scanner.beacons.iter()); + found = Some(i); + break; + } + } + if let Some(idx) = found { + scanners.remove(idx); + found = None; + } else { + break; + } + } + Ok(beacons.len().try_into()?) +} + +pub fn part2(scan: Scan) -> anyhow::Result { + let mut beacons: std::collections::HashSet = + std::collections::HashSet::new(); + let mut skip = None; + let mut offsets = vec![]; + for (i, scanner1) in scan.scanners().iter().enumerate() { + for (j, scanner2) in scan.scanners().iter().enumerate().skip(i + 1) { + if let Some((orientation, offset)) = + scanner2.matches(&scanner1.beacons.iter().copied().collect()) + { + let scanner2 = scanner2 + .at_orientation(ORIENTATIONS[orientation], offset); + beacons.extend(scanner1.beacons.iter()); + beacons.extend(scanner2.beacons.iter()); + skip = Some((i, j)); + offsets.push(Point::new(0, 0, 0)); + offsets.push(offset); + break; + } + } + if skip.is_some() { + break; + } + } + let skip = skip.unwrap(); + let mut scanners = scan.scanners().to_vec(); + scanners.remove(skip.1); + scanners.remove(skip.0); + + let mut found = None; + loop { + for (i, scanner) in scanners.iter().enumerate() { + if let Some((orientation, offset)) = scanner.matches(&beacons) { + let scanner = + scanner.at_orientation(ORIENTATIONS[orientation], offset); + beacons.extend(scanner.beacons.iter()); + offsets.push(offset); + found = Some(i); + break; + } + } + if let Some(idx) = found { + scanners.remove(idx); + found = None; + } else { + break; + } + } + let mut max = 0; + for offset1 in &offsets { + for offset2 in &offsets { + let dist = *offset1 - *offset2; + let dist = dist.x.abs() + dist.y.abs() + dist.z.abs(); + if dist > max { + max = dist; + } + } + } + Ok(max.into()) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(crate::util::data(2021, 19).unwrap()).unwrap()).unwrap(), + 338 + ); + assert_eq!( + part2(parse(crate::util::data(2021, 19).unwrap()).unwrap()).unwrap(), + 9862 + ); +} diff --git a/src/2021/mod.rs b/src/2021/mod.rs index 507251e..a5b6ab3 100644 --- a/src/2021/mod.rs +++ b/src/2021/mod.rs @@ -34,6 +34,8 @@ mod day16; mod day17; #[path = "18/mod.rs"] mod day18; +#[path = "19/mod.rs"] +mod day19; // NEXT MOD pub fn run(day: u8, puzzle: u8) -> anyhow::Result { @@ -74,6 +76,8 @@ pub fn run(day: u8, puzzle: u8) -> anyhow::Result { (17, 2) => day17::part2(day17::parse(crate::util::data(2021, 17)?)?), (18, 1) => day18::part1(day18::parse(crate::util::data(2021, 18)?)?), (18, 2) => day18::part2(day18::parse(crate::util::data(2021, 18)?)?), + (19, 1) => day19::part1(day19::parse(crate::util::data(2021, 19)?)?), + (19, 2) => day19::part2(day19::parse(crate::util::data(2021, 19)?)?), // NEXT PART _ => Err(anyhow::anyhow!("unknown puzzle {}-{}", day, puzzle)), } -- cgit v1.2.3-54-g00ecf