Advent of Code 2021 - Day 19: Beacon Scanner

beacon_scanner.rs

fn main() {
    let scanners = parse_scanners(INPUT);
    let map = Map::from(scanners);

    println!("Beacons: {}", map.beacon_count());
    println!("Manhattan distance: {:?}", map.max_manhattan_distance());
}

fn parse_scanners(input: &str) -> Vec<Scanner> {
    let scanners = input
        .split("\n\n")
        .map(|s| {
            let beacons = s
                .lines()
                .skip(1)
                .map(|b| {
                    let mut coords = b.split(',').map(|n| n.parse::<i16>().unwrap());
                    Vector::new(
                        coords.next().unwrap(),
                        coords.next().unwrap(),
                        coords.next().unwrap(),
                    )
                })
                .collect();

            Scanner { beacons }
        })
        .collect();

    scanners
}

struct Map {
    beacons: HashSet<Vector>,
    scanners: Vec<Vector>,
}

impl From<Vec<Scanner>> for Map {
    fn from(scanners: Vec<Scanner>) -> Self {
        let mut map = Map::new(scanners.len());

        map.map_scanners(&scanners, 0, &mut Vec::new(), &mut HashSet::new());

        map
    }
}

impl Map {
    fn new(size: usize) -> Self {
        Self {
            beacons: HashSet::new(),
            scanners: vec![Vector::new(0, 0, 0); size],
        }
    }

    fn beacon_count(&self) -> usize {
        self.beacons.len()
    }

    fn max_manhattan_distance(&self) -> i16 {
        let mut max = 0;

        for o in 0..self.scanners.len() {
            for i in (o + 1)..self.scanners.len() {
                let distance = self.scanners[o].manhattan_distance(&self.scanners[i]);
                if distance > max {
                    max = distance;
                }
            }
        }

        max
    }

    fn map_scanners(
        &mut self,
        scanners: &[Scanner],
        current: usize,
        transformations: &mut Vec<(Rotation, Vector)>,
        visited: &mut HashSet<usize>,
    ) {
        self.scanners[current] = Vector::new(0, 0, 0).apply_transformations(transformations);

        scanners[current]
            .beacons
            .iter()
            .map(|&p| p.apply_transformations(transformations))
            .for_each(|p| {
                self.beacons.insert(p);
            });

        visited.insert(current);

        for i in 0..scanners.len() {
            if current != i && !visited.contains(&i) {
                if let Some(transformation) = scanners[current].matches(&scanners[i]) {
                    transformations.push(transformation);
                    self.map_scanners(scanners, i, transformations, visited);
                    transformations.pop();
                }
            }
        }
    }
}

struct Scanner {
    beacons: HashSet<Vector>,
}

impl Scanner {
    const MIN_MATCHES: usize = 12;

    fn matches(&self, other: &Scanner) -> Option<(Rotation, Vector)> {
        let own_max_misses = self.beacons.len() - Self::MIN_MATCHES;
        let other_max_misses = other.beacons.len() - Self::MIN_MATCHES;

        for rotation in rotations() {
            let mut own_misses = 0;

            for own_candidate in &self.beacons {
                let mut other_misses = 0;

                for other_candidate in &other.beacons {
                    let translation = *own_candidate - rotation(*other_candidate);

                    let mut matches = 0;
                    let mut misses = 0;

                    for beacon in &other.beacons {
                        let rotated = rotation(*beacon);
                        let transformed = rotated + translation;

                        if self.beacons.contains(&transformed) {
                            matches += 1;
                        } else {
                            misses += 1;
                        }

                        if misses > other_max_misses {
                            break;
                        }

                        if matches >= Self::MIN_MATCHES {
                            return Some((rotation, translation));
                        }
                    }

                    other_misses += 1;

                    if other_misses > other_max_misses {
                        break;
                    }
                }

                own_misses += 1;

                if own_misses > own_max_misses {
                    break;
                }
            }
        }

        None
    }
}

#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
struct Vector {
    x: i16,
    y: i16,
    z: i16,
}

impl Add<Vector> for Vector {
    type Output = Vector;

    fn add(self, rhs: Vector) -> Self::Output {
        Vector::new(self.x + rhs.x, self.y + rhs.y, self.z + rhs.z)
    }
}

impl Sub<Vector> for Vector {
    type Output = Vector;

    fn sub(self, rhs: Vector) -> Self::Output {
        Vector::new(self.x - rhs.x, self.y - rhs.y, self.z - rhs.z)
    }
}

impl Vector {
    fn new(x: i16, y: i16, z: i16) -> Self {
        Vector { x, y, z }
    }

    fn manhattan_distance(&self, other: &Vector) -> i16 {
        (self.x - other.x).abs() + (self.y - other.y).abs() + (self.z - other.z).abs()
    }

    fn apply_transformations(&self, transformations: &[(Rotation, Vector)]) -> Vector {
        let mut result = *self;

        for (rotation, translation) in transformations.iter().rev() {
            result = rotation(result);
            result = result + *translation;
        }

        result
    }
}

type Rotation = Box<dyn Fn(Vector) -> Vector>;

fn rotations() -> Vec<Rotation> {
    let mut rotations = Vec::<Rotation>::new();

    for xd in [1, -1] {
        for yd in [1, -1] {
            for zd in [1, -1] {
                rotations.push(Box::new(move |p| Vector::new(p.x * xd, p.y * yd, p.z * zd)));
                rotations.push(Box::new(move |p| Vector::new(p.x * xd, p.z * zd, p.y * yd)));
                rotations.push(Box::new(move |p| Vector::new(p.y * yd, p.x * xd, p.z * zd)));
                rotations.push(Box::new(move |p| Vector::new(p.y * yd, p.z * zd, p.x * xd)));
                rotations.push(Box::new(move |p| Vector::new(p.z * zd, p.x * xd, p.y * yd)));
                rotations.push(Box::new(move |p| Vector::new(p.z * zd, p.y * yd, p.x * xd)));
            }
        }
    }

    rotations
}