Day 19 Code

use std::env;
use std::io::{self};
use std::collections::{HashSet,HashMap};

extern crate regex;
use regex::Regex;

use point3d::point3d::Point3D;

type Tuple3D = ((i64,i64,i64),(i64,i64,i64),(i64,i64,i64));

// https://www.euclideanspace.com/maths/algebra/matrix/transforms/examples/index.htm
const ROT01: Tuple3D =
    ((  1,  0,  0),
     (  0,  1,  0),
     (  0,  0,  1));

const ROT02: Tuple3D =
    ((  1,  0,  0),
     (  0,  0, -1),
     (  0,  1,  0));

const ROT03: Tuple3D =
    ((  1,  0,  0),
     (  0, -1,  0),
     (  0,  0, -1));

const ROT04: Tuple3D =
    ((  1,  0,  0),
     (  0,  0,  1),
     (  0, -1,  0));

const ROT05: Tuple3D =
    ((  0, -1,  0),
     (  1,  0,  0),
     (  0,  0,  1));

const ROT06: Tuple3D =
    ((  0,  0,  1),
     (  1,  0,  0),
     (  0,  1,  0));

const ROT07: Tuple3D =
    ((  0,  1,  0),
     (  1,  0,  0),
     (  0,  0, -1));

const ROT08: Tuple3D =
    ((  0,  0, -1),
     (  1,  0,  0),
     (  0, -1,  0));

const ROT09: Tuple3D =
    (( -1,  0,  0),
     (  0, -1,  0),
     (  0,  0,  1));

const ROT10: Tuple3D =
    (( -1,  0,  0),
     (  0,  0, -1),
     (  0, -1,  0));

const ROT11: Tuple3D =
    (( -1,  0,  0),
     (  0,  1,  0),
     (  0,  0, -1));

const ROT12: Tuple3D =
    (( -1,  0,  0),
     (  0,  0,  1),
     (  0,  1,  0));

const ROT13: Tuple3D =
    ((  0,  1,  0),
     ( -1,  0,  0),
     ( 0,   0,  1));

const ROT14: Tuple3D =
    ((  0,  0,  1),
     ( -1,  0,  0),
     (  0, -1,  0));

const ROT15: Tuple3D =
    ((  0, -1,  0),
     ( -1,  0,  0),
     (  0,  0, -1));

const ROT16: Tuple3D =
    ((  0,  0, -1),
     ( -1,  0,  0),
     (  0,  1,  0));

const ROT17: Tuple3D =
    ((  0,  0, -1),
     (  0,  1,  0),
     (  1,  0,  0));

const ROT18: Tuple3D =
    ((  0,  1,  0),
     (  0,  0,  1),
     (  1,  0,  0));

const ROT19: Tuple3D =
    ((  0,  0,  1),
     (  0, -1,  0),
     (  1,  0,  0));

const ROT20: Tuple3D =
    ((  0, -1,  0),
     (  0,  0, -1),
     (  1,  0,  0));

const ROT21: Tuple3D =
    ((  0,  0, -1),
     (  0, -1,  0),
     ( -1,  0,  0));

const ROT22: Tuple3D =
    ((  0, -1,  0),
     (  0,  0,  1),
     ( -1,  0,  0));

const ROT23: Tuple3D =
    ((  0,  0,  1),
     (  0,  1,  0),
     ( -1,  0,  0));

const ROT24: Tuple3D =
    ((  0,  1,  0),
     (  0,  0, -1),
     ( -1,  0,  0));

const ALL_ROTATIONS: [Tuple3D; 24] =
        [ROT01, ROT02, ROT03, ROT04, ROT05, ROT06,
         ROT07, ROT08, ROT09, ROT10, ROT11, ROT12,
         ROT13, ROT14, ROT15, ROT16, ROT17, ROT18,
         ROT19, ROT20, ROT21, ROT22, ROT23, ROT24];
// https://www.euclideanspace.com/maths/algebra/matrix/transforms/examples/index.htm

#[derive(Clone)]
struct Scanner {
    id: u8,
    beacons: Vec<Point3D>,
    fixed: bool,
    origin: Point3D,
}
impl From<&str> for Scanner {
    fn from(s: &str) -> Self {
        let s: Vec<_> = s.split("\n").collect();

        // Get id
        let re = Regex::new(r"scanner (\d+)").unwrap();
        let matches = re.captures(s[0]).unwrap();
        let id = matches[1].parse().unwrap();

        // Get beacons
        let mut beacons: Vec<Point3D> = Vec::new();
        let re = Regex::new(r"(\-*\d+),(\-*\d+),(\-*\d+)").unwrap();
        for line in s[1..].into_iter() {
            let matches = re.captures(line).unwrap();
            let (x,y,z) = (matches[1].parse().unwrap(),matches[2].parse().unwrap(),matches[3].parse().unwrap());
            beacons.push(Point3D { x: x, y: y, z: z });
        }
        Self { id: id, beacons: beacons, fixed: false, origin: Point3D::zeros() }
    }
}

fn rotate_by(pt: &mut Point3D, rotation: Tuple3D) {
    let pt0 = pt.clone();
    pt.x = rotation.0.0*pt0.x + rotation.0.1*pt0.y+rotation.0.2*pt0.z;
    pt.y = rotation.1.0*pt0.x + rotation.1.1*pt0.y+rotation.1.2*pt0.z;
    pt.z = rotation.2.0*pt0.x + rotation.2.1*pt0.y+rotation.2.2*pt0.z;
}
fn rotate_all_by(pts: &mut Vec<Point3D>, rotation: Tuple3D) {
    pts.iter_mut().for_each(|mut x| rotate_by(&mut x,rotation))
}

fn translate_xyz(pt: &mut Point3D, delx: i64, dely: i64, delz: i64) {
    pt.x += delx;
    pt.y += dely;
    pt.z += delz;
}
fn translate_all_xyz(pts: &mut Vec<Point3D>, delx: i64, dely: i64, delz: i64) {
    pts.iter_mut().for_each(|mut x| translate_xyz(&mut x,delx,dely,delz))
}

fn manhattan_distance(pt1: &Point3D, pt2: &Point3D) -> i64 {
    (pt1.x-pt2.x).abs() + (pt1.y-pt2.y).abs() + (pt1.z-pt2.z).abs()
}

fn solve(input: &str) -> io::Result<()> {
    // Input
    let input_str = std::fs::read_to_string(input).unwrap();
    let input_str = input_str.trim();
    let input: Vec<_> = input_str.split("\n\n").collect();

    // Get scanner and beacon data
    let mut scanners: Vec<_> = input
        .iter()
        .map(|x| Scanner::from(*x))
        .collect();

    // Assume orientation of first scanner
    scanners[0].fixed = true;

    // Generate initial composites from scanner 0
    let mut composite: HashSet<Point3D> = HashSet::new();
    for b in &scanners[0].beacons {
        composite.insert(*b);
    }

    'main: loop {
        // Try to match unfixed scanners against fixed scanners
        'scanner: for scanner in &mut scanners {
            if scanner.fixed { continue; }

            for rot in ALL_ROTATIONS {
                let mut beacons = scanner.beacons.clone();
                rotate_all_by(&mut beacons, rot);

                // Count x-, y-, z-offsets between these and known points
                let mut xcounts: HashMap<i64,i64> = HashMap::new();
                let mut ycounts: HashMap<i64,i64> = HashMap::new();
                let mut zcounts: HashMap<i64,i64> = HashMap::new();
                for beacon in &beacons {
                    for comp in composite.iter() {
                        *xcounts.entry(comp.x - beacon.x).or_insert(0) += 1;
                        *ycounts.entry(comp.y - beacon.y).or_insert(0) += 1;
                        *zcounts.entry(comp.z - beacon.z).or_insert(0) += 1;
                    }
                }

                // Generate x-, y-, z-offsets from counts and align scanner (if applicable)
                let xoffset = xcounts.iter().find(|&(_,v)| *v >= 12).map(|(k,_)| k);
                let yoffset = ycounts.iter().find(|&(_,v)| *v >= 12).map(|(k,_)| k);
                let zoffset = zcounts.iter().find(|&(_,v)| *v >= 12).map(|(k,_)| k);

                // Sort offset results to avoid non-deterministic solution
                let mut xcounts2: Vec<_> = xcounts.iter().collect(); xcounts2.sort_by(|a,b| b.1.cmp(a.1));
                let mut ycounts2: Vec<_> = ycounts.iter().collect(); ycounts2.sort_by(|a,b| b.1.cmp(a.1));
                let mut zcounts2: Vec<_> = zcounts.iter().collect(); zcounts2.sort_by(|a,b| b.1.cmp(a.1));
                if xoffset.is_some() && yoffset.is_some() && zoffset.is_some() {

                    let (newx,_) = *xcounts2.iter().next().unwrap();
                    let (newy,_) = *ycounts2.iter().next().unwrap();
                    let (newz,_) = *zcounts2.iter().next().unwrap();

                    scanner.beacons = beacons.clone();
                    scanner.origin = Point3D::new(*newx,*newy,*newz);
                    scanner.fixed = true;

                    // Add to composite
                    translate_all_xyz(&mut beacons,*newx,*newy,*newz);
                    for beacon in &beacons {
                        composite.insert(*beacon);
                    }
                    continue 'scanner;
                }
            }
        }

        // Check all scanners have been fixed
        if scanners.iter().all(|s| s.fixed) { break 'main; }
    }
    println!("Part 1: {}", composite.len()); // 318

    // Part 2
    let mut part2 = 0;
    for scanner1 in &scanners {
        for scanner2 in &scanners {
            part2 = std::cmp::max(part2,
                manhattan_distance(&scanner1.origin,&scanner2.origin));
        }
    }
    println!("Part 2: {}",part2); // 12166


    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}