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

aoc/year2017/
day20.rs
