aoc/year2017/
day20.rs

1//! # Particle Swarm
2//!
3//! ## Part One
4//!
5//! The particle that remains closest to the origin as time goes to infinity has the lowest
6//! acceleration, measured via its manhattan value. If more than one particle shares the same
7//! lowest acceleration then ties are broken by velocity then by position.
8//!
9//! ## Part Two
10//!
11//! The input is constructed so that all collisions happen within 40 ticks so a simple brute force
12//! solution is much faster than more elegant alternatives, for example solving the quadratic
13//! equation describing each particle's position.
14use crate::util::hash::*;
15use crate::util::iter::*;
16use crate::util::parse::*;
17
18#[derive(Copy, Clone, PartialEq, Eq, Hash)]
19struct Vector {
20    x: i32,
21    y: i32,
22    z: i32,
23}
24
25impl Vector {
26    fn new(cs: [i32; 3]) -> Self {
27        Vector { x: cs[0], y: cs[1], z: cs[2] }
28    }
29
30    fn manhattan(&self) -> i32 {
31        self.x.abs() + self.y.abs() + self.z.abs()
32    }
33
34    fn tick(&mut self, other: &Vector) {
35        self.x += other.x;
36        self.y += other.y;
37        self.z += other.z;
38    }
39}
40
41#[derive(Copy, Clone)]
42pub struct Particle {
43    id: usize,
44    position: Vector,
45    velocity: Vector,
46    acceleration: Vector,
47}
48
49impl Particle {
50    fn tick(&mut self) {
51        self.velocity.tick(&self.acceleration);
52        self.position.tick(&self.velocity);
53    }
54}
55
56pub fn parse(input: &str) -> Vec<Particle> {
57    input
58        .iter_signed()
59        .chunk::<3>()
60        .chunk::<3>()
61        .enumerate()
62        .map(|(id, cs)| Particle {
63            id,
64            position: Vector::new(cs[0]),
65            velocity: Vector::new(cs[1]),
66            acceleration: Vector::new(cs[2]),
67        })
68        .collect()
69}
70
71pub fn part1(input: &[Particle]) -> usize {
72    let mut candidates = Vec::new();
73    let mut min = i32::MAX;
74
75    // Find particles with the lowest acceleration.
76    for particle in input {
77        let next = particle.acceleration.manhattan();
78
79        if next < min {
80            candidates.clear();
81            min = next;
82        }
83        if next == min {
84            candidates.push(*particle);
85        }
86    }
87
88    // Ensure all acceleration, velocity and position vectors are "aligned", that is the
89    // sign of each component is the same, for example a particle with a negative x acceleration
90    // should also have a negative x velocity and negative x position.
91    for _ in 0..1000 {
92        candidates.iter_mut().for_each(Particle::tick);
93    }
94
95    // Tie break by velocity then by position.
96    candidates.sort_unstable_by(|a, b| {
97        let first = a.velocity.manhattan().cmp(&b.velocity.manhattan());
98        let second = a.position.manhattan().cmp(&b.position.manhattan());
99        first.then(second)
100    });
101
102    candidates[0].id
103}
104
105pub fn part2(input: &[Particle]) -> usize {
106    let mut particles = input.to_vec();
107    let mut collisions = FastMap::with_capacity(input.len());
108    let mut exists = vec![i64::MAX; input.len()];
109
110    for time in 1..40 {
111        for (i, particle) in particles.iter_mut().enumerate() {
112            // Only consider particles that haven't collided in a previous tick.
113            // Multiple particles can collide in the same tick.
114            if exists[i] >= time {
115                particle.tick();
116
117                if let Some(j) = collisions.insert(particle.position, i) {
118                    exists[i] = time;
119                    exists[j] = time;
120                }
121            }
122        }
123
124        collisions.clear();
125    }
126
127    exists.iter().filter(|&&t| t == i64::MAX).count()
128}
aoc/year2017/day20.rs

aoc/year2017/
day20.rs
