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        .chunk::<3>()
78        .enumerate()
79        .map(|(id, [p, v, a])| Particle {
80            id,
81            position: Vector::new(p),
82            velocity: Vector::new(v),
83            acceleration: Vector::new(a),
84        })
85        .collect()
86}
87
88pub fn part1(input: &[Particle]) -> usize {
89    // Find particles with the lowest acceleration.
90    let min = input.iter().map(|p| p.acceleration.manhattan()).min().unwrap();
91    let mut candidates: Vec<_> =
92        input.iter().copied().filter(|p| p.acceleration.manhattan() == min).collect();
93
94    // Ensure all acceleration, velocity and position vectors are "aligned", that is, the
95    // particles are moving away from the origin.
96    while !candidates.iter_mut().fold(true, |acc, particle| acc & particle.align()) {}
97
98    // Tie break by velocity then by position.
99    candidates.iter().min_by_key(|p| (p.velocity.manhattan(), p.position.manhattan())).unwrap().id
100}
101
102pub fn part2(input: &[Particle]) -> usize {
103    let mut particles = input.to_vec();
104    let mut collisions = FastMap::with_capacity(input.len());
105    let mut alive = vec![true; input.len()];
106
107    for _ in 1..40 {
108        for (i, particle) in particles.iter_mut().enumerate() {
109            // Only consider particles that haven't collided in a previous tick.
110            // Multiple particles can collide in the same tick.
111            if alive[i] {
112                particle.tick();
113
114                if let Some(j) = collisions.insert(particle.position, i) {
115                    alive[i] = false;
116                    alive[j] = false;
117                }
118            }
119        }
120
121        collisions.clear();
122    }
123
124    alive.iter().filter(|&&a| a).count()
125}
aoc/year2017/day20.rs

aoc/year2017/
day20.rs
