diff options
Diffstat (limited to '2021/src/bin/day_19.rs')
| -rw-r--r-- | 2021/src/bin/day_19.rs | 223 |
1 files changed, 223 insertions, 0 deletions
diff --git a/2021/src/bin/day_19.rs b/2021/src/bin/day_19.rs new file mode 100644 index 0000000..3fd8291 --- /dev/null +++ b/2021/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<dyn std::error::Error>> { + 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<Scanner>, + aligned_checking_for_neighbours_scanners: Vec<Scanner>, + unaligned_scanners: Vec<Scanner>, +} + +impl ScannerCloud { + fn new(mut scanners: Vec<Scanner>) -> 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<Point> { + 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<Point>, +} + +impl Scanner { + fn try_align_with(&self, other: &Scanner) -> Option<Scanner> { + 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) +} |