day19.rs

use std::collections::BTreeSet;

type Point = [i64; 3];
type Rotation = [u8; 3];

#[derive(Debug)]
struct Orientation {
    signs: [i8; 3],
    rotation: Rotation,
}

#[rustfmt::skip]
const ORIENTATIONS: &'static [Orientation] = &[
    Orientation { signs: [1, 1, 1], rotation: [0, 1, 2] },
    Orientation { signs: [1, 1, 1], rotation: [0, 2, 1] },
    Orientation { signs: [1, 1, 1], rotation: [1, 0, 2] },
    Orientation { signs: [1, 1, 1], rotation: [1, 2, 0] },
    Orientation { signs: [1, 1, 1], rotation: [2, 0, 1] },
    Orientation { signs: [1, 1, 1], rotation: [2, 1, 0] },
    Orientation { signs: [1, 1, -1], rotation: [0, 1, 2] },
    Orientation { signs: [1, 1, -1], rotation: [0, 2, 1] },
    Orientation { signs: [1, 1, -1], rotation: [1, 0, 2] },
    Orientation { signs: [1, 1, -1], rotation: [1, 2, 0] },
    Orientation { signs: [1, 1, -1], rotation: [2, 0, 1] },
    Orientation { signs: [1, 1, -1], rotation: [2, 1, 0] },
    Orientation { signs: [1, -1, 1], rotation: [0, 1, 2] },
    Orientation { signs: [1, -1, 1], rotation: [0, 2, 1] },
    Orientation { signs: [1, -1, 1], rotation: [1, 0, 2] },
    Orientation { signs: [1, -1, 1], rotation: [1, 2, 0] },
    Orientation { signs: [1, -1, 1], rotation: [2, 0, 1] },
    Orientation { signs: [1, -1, 1], rotation: [2, 1, 0] },
    Orientation { signs: [1, -1, -1], rotation: [0, 1, 2] },
    Orientation { signs: [1, -1, -1], rotation: [0, 2, 1] },
    Orientation { signs: [1, -1, -1], rotation: [1, 0, 2] },
    Orientation { signs: [1, -1, -1], rotation: [1, 2, 0] },
    Orientation { signs: [1, -1, -1], rotation: [2, 0, 1] },
    Orientation { signs: [1, -1, -1], rotation: [2, 1, 0] },
    Orientation { signs: [-1, 1, 1], rotation: [0, 1, 2] },
    Orientation { signs: [-1, 1, 1], rotation: [0, 2, 1] },
    Orientation { signs: [-1, 1, 1], rotation: [1, 0, 2] },
    Orientation { signs: [-1, 1, 1], rotation: [1, 2, 0] },
    Orientation { signs: [-1, 1, 1], rotation: [2, 0, 1] },
    Orientation { signs: [-1, 1, 1], rotation: [2, 1, 0] },
    Orientation { signs: [-1, 1, -1], rotation: [0, 1, 2] },
    Orientation { signs: [-1, 1, -1], rotation: [0, 2, 1] },
    Orientation { signs: [-1, 1, -1], rotation: [1, 0, 2] },
    Orientation { signs: [-1, 1, -1], rotation: [1, 2, 0] },
    Orientation { signs: [-1, 1, -1], rotation: [2, 0, 1] },
    Orientation { signs: [-1, 1, -1], rotation: [2, 1, 0] },
    Orientation { signs: [-1, -1, 1], rotation: [0, 1, 2] },
    Orientation { signs: [-1, -1, 1], rotation: [0, 2, 1] },
    Orientation { signs: [-1, -1, 1], rotation: [1, 0, 2] },
    Orientation { signs: [-1, -1, 1], rotation: [1, 2, 0] },
    Orientation { signs: [-1, -1, 1], rotation: [2, 0, 1] },
    Orientation { signs: [-1, -1, 1], rotation: [2, 1, 0] },
    Orientation { signs: [-1, -1, -1], rotation: [0, 1, 2] },
    Orientation { signs: [-1, -1, -1], rotation: [0, 2, 1] },
    Orientation { signs: [-1, -1, -1], rotation: [1, 0, 2] },
    Orientation { signs: [-1, -1, -1], rotation: [1, 2, 0] },
    Orientation { signs: [-1, -1, -1], rotation: [2, 0, 1] },
    Orientation { signs: [-1, -1, -1], rotation: [2, 1, 0] },
];

fn negate_point(p: Point) -> Point {
    [-p[0], -p[1], -p[2]]
}

fn add_points(p1: Point, p2: Point) -> Point {
    [p1[0] + p2[0], p1[1] + p2[1], p1[2] + p2[2]]
}

fn sub_points(p1: Point, p2: Point) -> Point {
    add_points(p1, negate_point(p2))
}

fn rotate(p: Point, rotation: Rotation) -> Point {
    [
        p[rotation[0] as usize],
        p[rotation[1] as usize],
        p[rotation[2] as usize],
    ]
}

fn reorient_points(o: &Orientation, points: &Vec<Point>) -> Vec<Point> {
    points
        .iter()
        .map(|p| {
            rotate(
                [
                    p[0] * o.signs[0] as i64,
                    p[1] * o.signs[1] as i64,
                    p[2] * o.signs[2] as i64,
                ],
                o.rotation,
            )
        })
        .collect()
}

#[derive(Debug)]
struct Scanner<'a> {
    id: u8,
    position: Option<Point>,
    visible_beacons: Vec<Point>,
    orientation: Option<&'a Orientation>,
}

impl<'a> Scanner<'a> {
    fn new(id: u8, beacons: Vec<Point>) -> Scanner<'a> {
        Scanner {
            id,
            position: None,
            visible_beacons: beacons,
            orientation: None,
        }
    }

    fn commit_to_placement(&mut self, position: Point, orientation: &'static Orientation) {
        self.position.replace(position);
        self.orientation.replace(orientation);
        for (i, point) in reorient_points(orientation, &self.visible_beacons)
            .into_iter()
            .enumerate()
        {
            self.visible_beacons[i] = add_points(point, position);
        }
    }

    fn try_determine_placement(&mut self, other: &Scanner) -> bool {
        for orientation in ORIENTATIONS {
            let oriented_points = reorient_points(orientation, &self.visible_beacons);

            for point in &oriented_points {
                for other_point in &other.visible_beacons {
                    let scanner_offset = sub_points(*point, *other_point);

                    let overlapping = oriented_points
                        .iter()
                        .map(|p| sub_points(*p, scanner_offset))
                        .filter(|p| other.visible_beacons.contains(p));

                    if overlapping.count() >= 12 {
                        self.commit_to_placement(negate_point(scanner_offset), orientation);
                        return true;
                    }
                }
            }
        }

        return false;
    }
}

fn main() {
    let text = std::fs::read_to_string(".aoc-cache/2021-19.txt").unwrap();

    let mut scanners = Vec::new();
    for block in text.trim().split("\n\n").map(|block| block.split("\n")) {
        let lines: Vec<_> = block.collect();
        let id = lines[0].split(" ").nth(2).unwrap().parse::<u8>().unwrap();
        let beacons = (&lines[1..]).into_iter().map(|l| {
            let mut nums = l.split(",");
            [
                nums.next().unwrap().parse::<i64>().unwrap(),
                nums.next().unwrap().parse::<i64>().unwrap(),
                nums.next().unwrap().parse::<i64>().unwrap(),
            ]
        });
        scanners.push(Scanner::new(id, beacons.collect()));
    }

    let zero = &mut scanners[0];
    zero.position.replace([0, 0, 0]);
    zero.orientation.replace(&ORIENTATIONS[0]);

    let mut remaining_scanners: Vec<_> = scanners.iter_mut().collect();
    let mut found_scanners = vec![remaining_scanners.remove(0)];

    'outer: while !remaining_scanners.is_empty() {
        for i in 0..remaining_scanners.len() {
            let s = &mut remaining_scanners[i];
            if found_scanners
                .iter()
                .any(|s2| s.try_determine_placement(s2))
            {
                found_scanners.push(remaining_scanners.remove(i));
                println!(
                    "{}/{}",
                    found_scanners.len(),
                    found_scanners.len() + remaining_scanners.len()
                );
                continue 'outer;
            }
        }
    }

    println!(
        "{}",
        found_scanners
            .iter()
            .map(|s| &s.visible_beacons)
            .flatten()
            .collect::<BTreeSet<_>>()
            .len()
    );

    let mut max = 0;
    for s1 in &scanners {
        let p1 = s1.position.unwrap();
        for s2 in &scanners {
            let p2 = s2.position.unwrap();
            let val = (p1[0] - p2[0]).abs() + (p1[1] - p2[1]).abs() + (p1[2] - p2[2]).abs();
            if val > max {
                max = val
            }
        }
    }

    println!("{}", max);
}