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    #[inline]
27    fn new([x, y, z]: [i32; 3]) -> Self {
28        Vector { x, y, z }
29    }
30
31    #[inline]
32    fn manhattan(self) -> i32 {
33        self.x.abs() + self.y.abs() + self.z.abs()
34    }
35
36    #[inline]
37    fn tick(&mut self, other: Vector) {
38        self.x += other.x;
39        self.y += other.y;
40        self.z += other.z;
41    }
42}
43
44#[derive(Copy, Clone)]
45pub struct Particle {
46    id: usize,
47    position: Vector,
48    velocity: Vector,
49    acceleration: Vector,
50}
51
52impl Particle {
53    #[inline]
54    fn tick(&mut self) {
55        self.velocity.tick(self.acceleration);
56        self.position.tick(self.velocity);
57    }
58
59    // Perform a tick on particle, and return true if it is aligned.
60    #[inline]
61    fn align(&mut self) -> bool {
62        let oldp = self.position.manhattan();
63        let oldv = self.velocity.manhattan();
64        self.tick();
65        oldp <= self.position.manhattan() && oldv <= self.velocity.manhattan()
66    }
67}
68
69pub fn parse(input: &str) -> Vec<Particle> {
70    input
71        .iter_signed()
72        .chunk::<3>()
73        .chunk::<3>()
74        .enumerate()
75        .map(|(id, [p, v, a])| Particle {
76            id,
77            position: Vector::new(p),
78            velocity: Vector::new(v),
79            acceleration: Vector::new(a),
80        })
81        .collect()
82}
83
84pub fn part1(input: &[Particle]) -> usize {
85    // Find particles with the lowest acceleration.
86    let min = input.iter().map(|p| p.acceleration.manhattan()).min().unwrap();
87    let mut candidates: Vec<_> =
88        input.iter().copied().filter(|p| p.acceleration.manhattan() == min).collect();
89
90    // Ensure all acceleration, velocity and position vectors are "aligned", that is, the
91    // particles are moving away from the origin.
92    while !candidates.iter_mut().fold(true, |acc, particle| acc & particle.align()) {}
93
94    // Tie break by velocity then by position.
95    candidates.iter().min_by_key(|p| (p.velocity.manhattan(), p.position.manhattan())).unwrap().id
96}
97
98pub fn part2(input: &[Particle]) -> usize {
99    let mut particles = input.to_vec();
100    let mut collisions = FastMap::with_capacity(input.len());
101    let mut alive = vec![true; input.len()];
102
103    for _ in 1..40 {
104        for (i, particle) in particles.iter_mut().enumerate() {
105            // Only consider particles that haven't collided in a previous tick.
106            // Multiple particles can collide in the same tick.
107            if alive[i] {
108                particle.tick();
109
110                if let Some(j) = collisions.insert(particle.position, i) {
111                    alive[i] = false;
112                    alive[j] = false;
113                }
114            }
115        }
116
117        collisions.clear();
118    }
119
120    alive.iter().filter(|&&a| a).count()
121}
aoc/year2017/day20.rs

aoc/year2017/
day20.rs
