diff options
Diffstat (limited to '19/src')
| -rw-r--r-- | 19/src/main.rs | 344 |
1 files changed, 344 insertions, 0 deletions
diff --git a/19/src/main.rs b/19/src/main.rs new file mode 100644 index 0000000..8b13d80 --- /dev/null +++ b/19/src/main.rs @@ -0,0 +1,344 @@ +use advent_lib::prelude::*; + +use std::collections::BTreeSet; + + +#[derive(Debug, Clone, PartialOrd, Ord, PartialEq, Eq)] +struct Point { + x: i64, + y: i64, + z: i64, +} + +#[derive(Debug, Clone)] +struct Rotation { + top: RotationAngle, + front: RotationAngle, + right: RotationAngle, +} + +#[derive(Debug, Clone, Copy)] +enum RotationAngle { + None, + Ninety, + OneEighty, + TwoSeventy, +} + + +fn main() -> Result<()> { + let mut args = std::env::args(); + if args.len() != 2 { + eprintln!("Usage: advent input"); + } + let _ = args.next(); + let filename = args.next().unwrap(); + + let input = advent_lib::group_lines_by_blanks( + advent_lib::read_lines_file(&filename)?); + + let mut scanners = Vec::new(); + for group in &input { + let mut scanner = Vec::new(); + for line in group.iter().skip(1) { + let values: Vec<&str> = line.split(",").collect(); + let x = values[0].parse::<i64>().unwrap(); + let y = values[1].parse::<i64>().unwrap(); + let z = values[2].parse::<i64>().unwrap(); + scanner.push(Point { x, y, z }); + } + scanners.push(scanner); + } + + let (merged_points, largest_distance) = + compare_all_scanners(&scanners, false); + println!("{}", merged_points.len()); + println!("{}", largest_distance); + + Ok(()) +} + + +fn compare_all_scanners(all_scanners: &Vec<Vec<Point>>, perform_sort: bool) + -> (Vec<Point>, i64) +{ + let mut unvisited_scanners = all_scanners.clone(); + let mut visited_scanner_offsets = Vec::new(); + + visited_scanner_offsets.push(Point { x: 0, y: 0, z: 0 }); + + loop { + let mut found_match = false; + + //println!("{} scanners remain", unvisited_scanners.len()); + + for i in 0 .. unvisited_scanners.len() - 1 { + for j in i + 1 .. unvisited_scanners.len() { + //println!("comparing {} vs {}", i, j); + let scanner_a = &unvisited_scanners[i]; + let scanner_b = &unvisited_scanners[j]; + + match compare_scanners(scanner_a, scanner_b) { + None => { }, + Some((a_b_unioned_points, offset)) => { + //println!("matched {} vs {} for {} beacons", i, j, + // a_b_unioned_points.len()); + + unvisited_scanners.remove(j); + unvisited_scanners[i] = a_b_unioned_points; + if perform_sort { + unvisited_scanners.sort_by(|a, b| + a.len().partial_cmp(&b.len()).unwrap()); + } + + visited_scanner_offsets.push(offset); + + found_match = true; + }, + } + + if found_match { + break; + } + } + + if found_match { + break; + } + } + + if !found_match { + break; + } + } + + let mut largest_distance = None; + for i in 0 .. visited_scanner_offsets.len() - 1 { + for j in i + 1 .. visited_scanner_offsets.len() { + let a = &visited_scanner_offsets[i]; + let b = &visited_scanner_offsets[j]; + let new_distance = compute_distance(a, b); + + match largest_distance { + None => { + largest_distance = Some(new_distance); + } + Some(old_distance) => { + if new_distance > old_distance { + largest_distance = Some(new_distance); + } + } + } + } + } + + (unvisited_scanners[0].clone(), largest_distance.unwrap()) +} + + +fn compare_scanners(scanner_a: &Vec<Point>, scanner_b: &Vec<Point>) + -> Option<(Vec<Point>,Point)> +{ + let all_rotations = compute_all_rotations(); + + for rotation in &all_rotations { + let mut sorted_scanner_a = scanner_a.clone(); + sorted_scanner_a.sort(); + + let mut sorted_scanner_b = Vec::new(); + for point in scanner_b { + let rotated_point = apply_rotation(point, rotation); + sorted_scanner_b.push(rotated_point); + } + sorted_scanner_b.sort(); + + for a_i in 0 .. sorted_scanner_a.len() { + for b_i in 0 .. sorted_scanner_b.len() { + let a_origin_point = sorted_scanner_a[a_i].clone(); + let b_origin_point = sorted_scanner_b[b_i].clone(); + + let mut n_matches = 0; + let mut a_j = 0; + let mut b_j = 0; + loop { + if a_j >= sorted_scanner_a.len() { + break; + } + if b_j >= sorted_scanner_b.len() { + break; + } + + let a_point = point_difference( + &sorted_scanner_a[a_j], &a_origin_point); + let b_point = point_difference( + &sorted_scanner_b[b_j], &b_origin_point); + + if a_point == b_point { + n_matches += 1; + a_j += 1; + b_j += 1; + } else if a_point < b_point { + a_j += 1; + } else { + b_j += 1; + } + } + + if n_matches >= 12 { + let b_offset = point_difference(&a_origin_point, &b_origin_point); + + let mut unioned_points = BTreeSet::new(); + for point in sorted_scanner_a { + unioned_points.insert(point.clone()); + } + + for point in sorted_scanner_b { + let adjusted_point = point_sum(&point, &b_offset); + unioned_points.insert(adjusted_point); + } + + let mut result = Vec::new(); + for point in unioned_points { + result.push(point); + } + result.sort(); + + return Some((result, b_offset)); + } + } + } + } + + None +} + + +fn point_difference(left: &Point, right: &Point) -> Point { + Point { + x: left.x - right.x, + y: left.y - right.y, + z: left.z - right.z, + } +} + + +fn point_sum(left: &Point, right: &Point) -> Point { + Point { + x: left.x + right.x, + y: left.y + right.y, + z: left.z + right.z, + } +} + + +/* top 0, top 1, top 2, top 3 (front, right 0) + * top 0, top 1, top 2, top 3 (front 1, right 0) + * top 0, top 1, top 2, top 3 (front 2, right 0) + * top 0, top 1, top 2, top 3 (front 3, right 0) + * top 0, top 1, top 2, top 3 (front 0, right 1) + * top 0, top 1, top 2, top 3 (front 0, right 3) + */ +fn compute_all_rotations() -> Vec<Rotation> { + let mut result = Vec::new(); + + let all_angles = vec![ + RotationAngle::None, + RotationAngle::Ninety, + RotationAngle::OneEighty, + RotationAngle::TwoSeventy, + ]; + + for front in 0 .. 4 { + for top in 0 .. 4 { + result.push(Rotation { + top: all_angles[top], + front: all_angles[front], + right: RotationAngle::None, + }); + } + } + + for right in [1, 3].iter() { + for top in 0 .. 4 { + result.push(Rotation { + top: all_angles[top], + front: RotationAngle::None, + right: all_angles[*right], + }); + } + } + + result +} + + +/* + * x is left-right, y is top-bottom, z is front-back. + * top, front, right have their standard Rubik's cube meanings. + */ +fn apply_rotation(point: &Point, rotation: &Rotation) -> Point { + let mut result = point.clone(); + + match rotation.top { + RotationAngle::None => { } + RotationAngle::Ninety => { + let temp_x = result.x; + result.x = result.z; + result.z = -temp_x; + } + RotationAngle::OneEighty => { + result.x = -result.x; + result.z = -result.z; + } + RotationAngle::TwoSeventy => { + let temp_x = result.x; + result.x = -result.z; + result.z = temp_x; + } + } + + match rotation.front { + RotationAngle::None => { } + RotationAngle::Ninety => { + let temp_x = result.x; + result.x = result.y; + result.y = -temp_x; + } + RotationAngle::OneEighty => { + result.x = -result.x; + result.y = -result.y; + } + RotationAngle::TwoSeventy => { + let temp_x = result.x; + result.x = -result.y; + result.y = temp_x; + } + } + + match rotation.right { + RotationAngle::None => { } + RotationAngle::Ninety => { + let temp_z = result.z; + result.z = result.y; + result.y = -temp_z; + } + RotationAngle::OneEighty => { + result.z = -result.z; + result.y = -result.y; + } + RotationAngle::TwoSeventy => { + let temp_z = result.z; + result.z = -result.y; + result.y = temp_z; + } + } + + result +} + + +fn compute_distance(point_a: &Point, point_b: &Point) -> i64 { + (point_a.x - point_b.x).abs() + + (point_a.y - point_b.y).abs() + + (point_a.z - point_b.z).abs() +} |