Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- use std::collections::{HashMap, HashSet};
- use itertools::Itertools;
- use pathfinding::num_traits::{abs, pow};
- use pathfinding::prelude::absdiff;
- use std::borrow::Borrow;
- use fxhash::{FxBuildHasher, FxHasher, FxHashMap, FxHashSet};
- 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_2UNSTABLE(){
- let mut inputs: Vec<HashSet<(i64, i64, i64), FxBuildHasher>> = Vec::new();
- include_str!("../temp19").split("\r\n\r\n").for_each(|x| {
- let mut inner: HashSet<(i64, i64, i64), FxBuildHasher> = FxHashSet::default();
- 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 = FxHashSet::default();
- let mut distances_dict = FxHashMap::default();
- 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);
- }
- 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 first1 = &all_distances_dict[0];
- let mut translation = FxHashMap::default();
- 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();
- rel_dists.push(x.0.0);
- 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 = FxHashSet::default();
- let mut distances_dict = FxHashMap::default();
- 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());
- 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;
- }
- pub fn day19_2stable() {
- let mut inputs = Vec::new();
- include_str!("../temp19").split("\r\n\r\n").for_each(|x| {
- let mut inner = FxHashSet::default();
- 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 = FxHashSet::default();
- let mut distances_dict = FxHashMap::default();
- 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 = FxHashMap::default();
- 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 = FxHashSet::default();
- let mut distances_dict = FxHashMap::default();
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement