path: root/2021/src/bin/day_19.rs

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(&current_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)
}