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

aoc/year2017/
day20.rs
