191 lines
8.5 KiB
Rust
191 lines
8.5 KiB
Rust
use std::fs::read_to_string;
|
|
use std::time::Instant;
|
|
|
|
fn get_numbers_in_line_split_iter<T: std::str::FromStr>(str: &str) -> impl Iterator<Item=T> + '_ {
|
|
str.split([' ', ',']).filter_map(|substr| substr.parse::<T>().ok())
|
|
}
|
|
|
|
struct Hailstone {
|
|
pos: (i64, i64, i64),
|
|
vel: (i64, i64, i64),
|
|
}
|
|
|
|
enum LineIntersection<T: PartialOrd> {
|
|
// Has position of intersection
|
|
Intersects((T, T)),
|
|
// Has coefficient of the line (a, b, c), with line being ax + bx + c = 0
|
|
Colinear((T, T, T)),
|
|
None,
|
|
}
|
|
|
|
// lXpY = line X point Y
|
|
fn xy_intersection<T>(l1p1: (T, T), l1p2: (T, T), l2p1: (T, T), l2p2: (T, T)) -> LineIntersection<T>
|
|
where T: PartialOrd + std::ops::Neg<Output=T> + std::ops::Sub<Output=T> + num::Zero,
|
|
for<'a> &'a T: std::ops::Sub<Output=T> + std::ops::Mul<Output=T> + std::ops::Div<Output=T>
|
|
{
|
|
let l1xdiff = &l1p1.0 - &l1p2.0;
|
|
let l1ydiff = &l1p1.1 - &l1p2.1;
|
|
let l2xdiff = &l2p1.0 - &l2p2.0;
|
|
let l2ydiff = &l2p1.1 - &l2p2.1;
|
|
let denom = &l1xdiff * &l2ydiff - &l1ydiff * &l2xdiff;
|
|
if denom == T::zero() {
|
|
let proj1 = &l1p1.0 * &l1ydiff - &l1p1.1 * &l1xdiff;
|
|
let proj2 = &l2p1.0 * &l1ydiff - &l2p1.1 * &l1xdiff;
|
|
if &proj1 - &proj2 == T::zero() {
|
|
return LineIntersection::Colinear((l1xdiff, -l1ydiff, -proj1));
|
|
} else {
|
|
return LineIntersection::None;
|
|
}
|
|
}
|
|
let l1det = (&l1p1.0 * &l1p2.1) - (&l1p1.1 * &l1p2.0);
|
|
let l2det = (&l2p1.0 * &l2p2.1) - (&l2p1.1 * &l2p2.0);
|
|
let detx = &l1det * &l2xdiff - &l2det * &l1xdiff;
|
|
let dety = &l1det * &l2ydiff - &l2det * &l1ydiff;
|
|
LineIntersection::Intersects((&detx / &denom, &dety / &denom))
|
|
}
|
|
|
|
fn vec_add<T>(v1: (T, T, T), v2: (T, T, T)) -> (T, T, T)
|
|
where T: std::ops::Add<Output=T> {
|
|
(v1.0 + v2.0, v1.1 + v2.1, v1.2 + v2.2)
|
|
}
|
|
|
|
fn cross_prod<T>(v1: (T, T, T), v2: (T, T, T)) -> (T, T, T)
|
|
where T: std::ops::Sub<T, Output=T>, for<'a> &'a T: std::ops::Mul<&'a T, Output=T> {
|
|
(&v1.1 * &v2.2 - &v1.2 * &v2.1, &v1.2 * &v2.0 - &v1.0 * &v2.2, &v1.0 * &v2.1 - &v1.1 * &v2.0)
|
|
}
|
|
|
|
|
|
// Get integer intersecting line at the right timeframes: (x, y, z), (vx, vy, vz)
|
|
fn get_intersecting_line(hailstones: &[Hailstone]) -> ((i64, i64, i64), (i64, i64, i64)) {
|
|
// Moving the frame of reference to hailstones[0] so we can compute the rest around origin
|
|
// With one line being reduced to start (0, 0, 0) and velocity (0, 0, 0) it'll be simpler
|
|
let map_pos = hailstones[0].pos;
|
|
let map_vel = hailstones[0].vel;
|
|
let hails = hailstones[1..=2].iter().map(
|
|
|hail| {
|
|
let pos = ((hail.pos.0 - map_pos.0) as i128, (hail.pos.1 - map_pos.1) as i128, (hail.pos.2 - map_pos.2) as i128);
|
|
let vel = ((hail.vel.0 - map_vel.0) as i128, (hail.vel.1 - map_vel.1) as i128, (hail.vel.2 - map_vel.2) as i128);
|
|
(pos, vel)
|
|
}
|
|
).collect::<Vec<_>>();
|
|
// cross product of vectors from origin to two points of the first other line
|
|
let plane1 = cross_prod(hails[0].0, vec_add(hails[0].0, hails[0].1));
|
|
// cross product of vectors from origin to two points of the second other line
|
|
let plane2 = cross_prod(hails[1].0, vec_add(hails[1].0, hails[1].1));
|
|
// cross product of thw two planes to reduce the space to a single line
|
|
let line = cross_prod(plane1, plane2);
|
|
// The line now represents a good direction with potentially wrong length (not a problem),
|
|
// and potentially wrong sign (a problem)
|
|
// find the smallest possible vel using gcd
|
|
let gcd = [line.0, line.1, line.2].iter()
|
|
.fold(0i128, |acc, &elem| num::integer::gcd(acc, elem));
|
|
let mut vel = (line.0 / gcd, line.1 / gcd, line.2 / gcd);
|
|
// We need to find the start point
|
|
// We know of one line at (0, 0, 0) due to mapping, we'll use it with another line to figure
|
|
// out the exact starting position (mapped)
|
|
// start + t0 * vel = 0 - the line at 0
|
|
// start + t1 * vel = p1 + t1*vel1 - the other line
|
|
// becomes
|
|
// start = p1 + t1 * (vel1 - vel)
|
|
// start = -t0 * vel
|
|
// get rid of start
|
|
// t0 * vel + t1 * (vel1 - vel) = -p1 - the vectors are 3 dimensional and we have 2 variables
|
|
// solve system of just taking the x and y from vectors
|
|
let mut det = vel.0 * (hails[1].1.1 - vel.1) - vel.1 * (hails[1].1.0 - vel.0);
|
|
let mut t0 = -hails[1].0.0 * (hails[1].1.1 - vel.1) / det + hails[1].0.1 * (hails[1].1.0 - vel.0) / det;
|
|
let mut start = (-t0 * vel.0, -t0 * vel.1, -t0 * vel.2);
|
|
// check on other 2 hailstones if the answer is consistent, otherwise flip sign
|
|
let mut wrong = false;
|
|
let rock_pos = [start.0, start.1, start.2];
|
|
let rock_vel = [vel.0, vel.1, vel.2];
|
|
'outer: for i in 0..2 {
|
|
let mut last_solution: Option<i128> = None;
|
|
let hail_pos = [hails[i].0.0, hails[i].0.1, hails[i].0.2];
|
|
let hail_vel = [hails[i].1.0, hails[i].1.1, hails[i].1.2];
|
|
for j in 0..3 {
|
|
let denom = rock_vel[j] - hail_vel[j];
|
|
if denom != 0 {
|
|
let new_solution = (hail_pos[j] - rock_pos[j]) / denom;
|
|
if new_solution < 0 {
|
|
wrong = true;
|
|
break 'outer;
|
|
}
|
|
match last_solution {
|
|
None => last_solution = Some(new_solution),
|
|
Some(s) => {
|
|
if s != new_solution {
|
|
wrong = true;
|
|
break 'outer;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
// flip the sign
|
|
if wrong {
|
|
vel = (-vel.0, -vel.1, -vel.2);
|
|
det = vel.0 * (hails[1].1.1 - vel.1) - vel.1 * (hails[1].1.0 - vel.0);
|
|
t0 = -hails[1].0.0 * (hails[1].1.1 - vel.1) / det + hails[1].0.1 * (hails[1].1.0 - vel.0) / det;
|
|
start = (-t0 * vel.0, -t0 * vel.1, -t0 * vel.2);
|
|
}
|
|
let start_unmapped = (start.0 as i64 + map_pos.0, start.1 as i64 + map_pos.1, start.2 as i64 + map_pos.2);
|
|
let vel_unmapped = (vel.0 as i64 + map_vel.0, vel.1 as i64 + map_vel.1, vel.2 as i64 + map_vel.2);
|
|
(start_unmapped, vel_unmapped)
|
|
}
|
|
|
|
fn main() {
|
|
let time_start = Instant::now();
|
|
let input_str = read_to_string("input.txt").unwrap();
|
|
let time_start_no_io = Instant::now();
|
|
// Shift the interval to be centered around 0, avoids numerical errors
|
|
const COORD_SHIFT: i64 = -3e14 as i64;
|
|
const MIN_POS: f64 = -1e14;
|
|
const MAX_POS: f64 = 1e14;
|
|
let hailstones = input_str.lines().map(|line| {
|
|
let mut it = get_numbers_in_line_split_iter::<i64>(line);
|
|
Hailstone {
|
|
pos: (it.next().unwrap() + COORD_SHIFT, it.next().unwrap() + COORD_SHIFT, it.next().unwrap() + COORD_SHIFT),
|
|
vel: (it.next().unwrap(), it.next().unwrap(), it.next().unwrap()),
|
|
}
|
|
}).collect::<Vec<_>>();
|
|
// Part 1
|
|
let mut count1 = 0;
|
|
for (i, h1) in hailstones.iter().enumerate() {
|
|
for h2 in hailstones[i + 1..].iter() {
|
|
let l1p1 = (h1.pos.0 as f64, h1.pos.1 as f64);
|
|
let l1p2 = ((h1.pos.0 + h1.vel.0) as f64, (h1.pos.1 + h1.vel.1) as f64);
|
|
let l2p1 = (h2.pos.0 as f64, h2.pos.1 as f64);
|
|
let l2p2 = ((h2.pos.0 + h2.vel.0) as f64, (h2.pos.1 + h2.vel.1) as f64);
|
|
match xy_intersection(l1p1, l1p2, l2p1, l2p2) {
|
|
LineIntersection::Intersects((x, y)) => {
|
|
// Check if it's not in the past, thankfully velocity components are never 0
|
|
if (x - h1.pos.0 as f64) / h1.vel.0 as f64 >= 0.
|
|
&& (x - h2.pos.0 as f64) / h2.vel.0 as f64 >= 0. {
|
|
if x >= MIN_POS && x <= MAX_POS && y >= MIN_POS && y <= MAX_POS {
|
|
count1 += 1;
|
|
}
|
|
}
|
|
}
|
|
LineIntersection::Colinear((_, _, _)) => {
|
|
// Seems this case isn't used
|
|
// otherwise I'd have to check if they go in the same direction
|
|
}
|
|
LineIntersection::None => {
|
|
}
|
|
}
|
|
}
|
|
}
|
|
// Part 2
|
|
let (start, vel) = get_intersecting_line(&hailstones);
|
|
let corrected_start = (start.0 - COORD_SHIFT, start.1 - COORD_SHIFT, start.2 - COORD_SHIFT);
|
|
let summed_coords = corrected_start.0 + corrected_start.1 + corrected_start.2;
|
|
let elapsed = time_start.elapsed().as_micros();
|
|
let elapsed_no_io = time_start_no_io.elapsed().as_micros();
|
|
println!("Time: {}us", elapsed);
|
|
println!("Time without file i/o: {}us", elapsed_no_io);
|
|
println!("Count1: {}", count1);
|
|
println!("Start: {:?}, vel: {:?}", corrected_start, vel);
|
|
println!("Summed start coords: {:?}", summed_coords);
|
|
}
|