use std::collections::{HashMap, HashSet};
use itertools::Itertools;
use pathfinding::num_traits::{abs, pow};
use pathfinding::prelude::absdiff;
use std::borrow::Borrow;


fn euclid_dist(first: &(i64, i64, i64), second: &(i64, i64, i64)) -> i64 {
    pow(first.0 - second.0, 2) + pow(first.1 - second.1, 2) + pow(first.2 - second.2, 2)
}

fn rotation_matrix(a: &(i64, i64, i64)) -> Vec<((i64, i64, i64))> {
    let &(x,y,z) = a;
    vec![
        (x, y, z),
        (x, z, -y),
        (x, -y, -z),
        (x, -z, y),
        (y, x, -z),
        (y, z, x),
        (y, -x, z),
        (y, -z, -x),
        (z, x, y),
        (z, y, -x),
        (z, -x, -y),
        (z, -y, x),
        (-x, y, -z),
        (-x, z, y),
        (-x, -y, z),
        (-x, -z, -y),
        (-y, x, z),
        (-y, z, -x),
        (-y, -x, -z),
        (-y, -z, x),
        (-z, x, -y),
        (-z, y, x),
        (-z, -x, y),
        (-z, -y, -x),
    ]
}

fn rotate_and_translate_single(a: &(i64, i64, i64), rot: usize, b: &(i64, i64, i64)) -> (i64, i64, i64) {
   let &(x,y, z) = a;
   match rot {
        0 => (x + b.0, y + b.1, z + b.2),
        1 => (x + b.0, z + b.1, -y + b.2),
        2 => (x + b.0, -y + b.1, -z + b.2),
        3 => (x + b.0, -z + b.1, y + b.2),
        4 => (y + b.0, x + b.1, -z + b.2),
        5 => (y + b.0, z + b.1, x + b.2),
        6 => (y + b.0, -x + b.1, z + b.2),
        7 => (y + b.0, -z + b.1, -x + b.2),
        8 => (z + b.0, x + b.1, y + b.2),
        9 => (z + b.0, y + b.1, -x + b.2),
        10 => (z + b.0, -x + b.1, -y + b.2),
        11 => (z + b.0, -y + b.1, x + b.2),
        12 => (-x + b.0, y + b.1, -z + b.2),
        13 => (-x + b.0, z + b.1, y + b.2),
        14 => (-x + b.0, -y + b.1, z + b.2),
        15 => (-x + b.0, -z + b.1, -y + b.2),
        16 => (-y + b.0, x + b.1, z + b.2),
        17 => (-y + b.0, z + b.1, -x + b.2),
        18 => (-y + b.0, -x + b.1, -z + b.2),
        19 => (-y + b.0, -z + b.1, x + b.2),
        20 => (-z + b.0, x + b.1, -y + b.2),
        21 => (-z + b.0, y + b.1, x + b.2),
        22 => (-z + b.0, -x + b.1, y + b.2),
        23 => (-z + b.0, -y + b.1, -x + b.2),
        _ => unreachable!(),
    }
}

pub fn day19_1UNSTABLE(){
    let mut inputs: Vec<HashSet<(i64, i64, i64)>> = Vec::new();
    include_str!("../temp19").split("\r\n\r\n").for_each(|x| {
        let mut inner:HashSet<(i64,i64,i64)> = HashSet::new();
        x.lines().skip(1).for_each(|x| {
            inner.insert(x.split(',').map(|x| x.parse().unwrap()).collect_tuple().unwrap());
        });
        inputs.push(inner);
    });
    let mut all_distances = Vec::new();
    let mut all_distances_dict = Vec::new();

    for input in &inputs {
        let mut distances = HashSet::new();
        let mut distances_dict = HashMap::new();
        for (&first, &second) in input.iter().tuple_combinations() {
            let euclid_dist : i64 = euclid_dist(&first, &second);
            //let man_dist : i64 = absdiff(first.0, second.0) + absdiff(first.1, second.1) + absdiff(first.2, second.2); //euclid might be sufficient?
            distances.insert(euclid_dist);
            distances_dict.insert(euclid_dist, (first, second));
        }
        all_distances.push(distances);
        all_distances_dict.push(distances_dict);
    }
    loop {
        let mut to_stich = ((0), (Vec::new()));
        let first = &all_distances[0];
        for (i2, second) in all_distances.iter().enumerate().skip(1) {
            let intersection = first.intersection(second).collect_vec();
            if intersection.len() >= 66 { //66 not 12 since 12 * 11 / 2 = 66 and thats the amount of intersections that they would have
                //stitch the first matching thing to the first one
                to_stich = (i2, intersection);
                break;
            }
        }
        let first1 = &all_distances_dict[0];
        let mut translation = HashMap::new();
        for dists in to_stich.1 {
            //find out if these two lines (formed by two points) are translations of each other (this doesnt work right now cause I'm not accounting for rotations)
            let (p1_1, p1_2) = first1.get(dists).unwrap();
            let (p2_1, p2_2) = all_distances_dict[to_stich.0].get(dists).unwrap();
            //do another loop for rotations
            rotation_matrix(&p2_1).iter().zip(rotation_matrix(&p2_2)).enumerate().for_each(|(i, (rp2_1, rp2_2))|
                {
                    let dist_11 = euclid_dist(&rp2_1, p1_1);
                    let dist_22 = euclid_dist(&rp2_2, p1_2);
                    let dist_12 = euclid_dist(p1_1, &rp2_2);
                    let dist_21 = euclid_dist(p1_2, &rp2_1);
                    if absdiff(dist_11, dist_22) == 0 {
                        //p1_1 is the same point as p2_1
                        let counter = translation.entry(((p1_1.0 - rp2_1.0, p1_1.1 - rp2_1.1, p1_1.2 - rp2_1.2), i)).or_insert(0);
                        *counter += 1;
                    } else if absdiff(dist_12, dist_21) == 0 {
                        //other match
                        let counter = translation.entry(((p1_1.0 - rp2_2.0, p1_1.1 - rp2_2.1, p1_1.2 - rp2_2.2), i)).or_insert(0);
                        *counter += 1;
                    }
                });
        };
        let x = translation.iter().filter(|(x, &y)| y >= 66).next().unwrap(); //this assumes something to stitch
        let insert = inputs[to_stich.0].iter().map(|y| {
            rotate_and_translate_single(y, x.0.1, &x.0.0)
        }).collect_vec();

        inputs[0].extend(&mut insert.iter());
        //if that was the only element left break out of the loop.
        if inputs.len() == 2 {
            break;
        }
        //remove from everywhere it needs to be
        inputs.remove(to_stich.0);
        all_distances_dict.remove(to_stich.0);
        all_distances.remove(to_stich.0);
        //recalculate the thing
        let mut distances = HashSet::new();
        let mut distances_dict = HashMap::new();
        for (&first, &second) in inputs[0].iter().tuple_combinations() {
            let euclid_dist: i64 = euclid_dist(&first, &second);
            //let man_dist: i64 = absdiff(first.0, second.0) + absdiff(first.1, second.1) + absdiff(first.2, second.2); //euclid might be sufficient?
            distances.insert(euclid_dist);
            distances_dict.insert(euclid_dist, (first, second));
        }
        all_distances[0] = distances;
        all_distances_dict[0] = distances_dict;
    }
    println!("ANSWER {}", inputs[0].len());
    return;
}


pub fn day19_2stable() {
    let mut inputs: Vec<HashSet<(i64, i64, i64)>> = Vec::new();
    include_str!("../temp19").split("\r\n\r\n").for_each(|x| {
        let mut inner:HashSet<(i64,i64,i64)> = HashSet::new();
        x.lines().skip(1).for_each(|x| {
            inner.insert(x.split(',').map(|x| x.parse().unwrap()).collect_tuple().unwrap());
        });
        inputs.push(inner);
    });
    let mut all_distances = Vec::new();
    let mut all_distances_dict = Vec::new();

    for input in &inputs {
        let mut distances = HashSet::new();
        let mut distances_dict = HashMap::new();
        for (&first, &second) in input.iter().tuple_combinations() {
            let euclid_dist : i64 = euclid_dist(&first, &second);
            let man_dist : i64 = absdiff(first.0, second.0) + absdiff(first.1, second.1) + absdiff(first.2, second.2); //euclid might be sufficient?
            distances.insert((euclid_dist, man_dist));
            distances_dict.insert((euclid_dist, man_dist), (first, second));
        }
        all_distances.push(distances);
        all_distances_dict.push(distances_dict);
    }
    let mut rel_dists = vec![(0i64, 0i64, 0i64)];
    loop {
        let mut to_stich = ((0), (Vec::new()));
        let first = &all_distances[0];
        for (i2, second) in all_distances.iter().enumerate().skip(1) {
            let intersection = first.intersection(second).collect_vec();
            if intersection.len() >= 66 { //66 not 12 since 12 * 11 / 2 = 66 and thats the amount of intersections that they would have
                //stitch the first matching thing to the first one
                to_stich = (i2, intersection);
                break;
            }
        }
        let mut translation = HashMap::new();
        let thing = &all_distances_dict[0];
        for dists in to_stich.1 {
            //find out if these two lines (formed by two points) are translations of each other (this doesnt work right now cause I'm not accounting for rotations)
            let (p1_1, p1_2) = thing.get(dists).unwrap();
            let (p2_1, p2_2) = all_distances_dict[to_stich.0].get(dists).unwrap();
            //do another loop for rotations
            rotation_matrix(&p2_1).iter().zip(rotation_matrix(&p2_2)).enumerate().for_each(|(i, (rp2_1, rp2_2))|
                {
                    let dist_11 = euclid_dist(&rp2_1, p1_1);
                    let dist_22 = euclid_dist(&rp2_2, p1_2);
                    let dist_12 = euclid_dist(p1_1, &rp2_2);
                    let dist_21 = euclid_dist(p1_2, &rp2_1);
                    if absdiff(dist_11, dist_22) == 0 {
                        //p1_1 is the same point as p2_1
                        let counter = translation.entry(((p1_1.0 - rp2_1.0, p1_1.1 - rp2_1.1, p1_1.2 - rp2_1.2), i)).or_insert(0);
                        *counter += 1;
                    } else if absdiff(dist_12, dist_21) == 0 {
                        //other match
                        let counter = translation.entry(((p1_1.0 - rp2_2.0, p1_1.1 - rp2_2.1, p1_1.2 - rp2_2.2), i)).or_insert(0);
                        *counter += 1;
                    }
                });
        };

        let x = translation.iter().filter(|(x, &y)| y >= 66).next().unwrap(); //this assumes something to stitch
        rel_dists.push(x.0.0);
        //if that was the only element left break out of the loop. in part 2 we can leave earlier because we don't have to stitch.
        //if inputs.len() == 2 {
        //    break;
        //}
        let insert = inputs[to_stich.0].iter().map(|y| {
            rotate_and_translate_single(y, x.0.1, &x.0.0)
        }).collect_vec();

        inputs[0].extend(&mut insert.iter());

        if inputs.len() == 2 {
            break;
        }
        //remove from everywhere it needs to be
        inputs.remove(to_stich.0);
        all_distances_dict.remove(to_stich.0);
        all_distances.remove(to_stich.0);
        //recalculate the thing
        let mut distances = HashSet::new();
        let mut distances_dict = HashMap::new();
        for (&first, &second) in inputs[0].iter().tuple_combinations() {
            let euclid_dist: i64 = euclid_dist(&first, &second);
            let man_dist: i64 = absdiff(first.0, second.0) + absdiff(first.1, second.1) + absdiff(first.2, second.2); //euclid might be sufficient?
            distances.insert((euclid_dist, man_dist));
            distances_dict.insert((euclid_dist, man_dist), (first, second));
        }
        all_distances[0] = distances;
        all_distances_dict[0] = distances_dict;
    }
    println!("ANSWER PART 1 {}", inputs[0].len());
    println!("ANSWER PART 2 {}", rel_dists.iter().tuple_combinations().map(|((x1, y1, z1), (x2, y2, z2))| abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2)).max().unwrap());

    return;
}