1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

//! # Particle Swarm
//!
//! ## Part One
//!
//! The particle that remains closest to the origin as time goes to infinity has the lowest
//! acceleration, measured via its manhattan value. If more than one particle shares the same
//! lowest acceleration then ties are broken by velocity then by position.
//!
//! ## Part Two
//!
//! The input is constructed so that all collisions happen within 40 ticks so a simple brute force
//! solution is much faster than more elegant alternatives, for example solving the quadratic
//! equation describing each particle's position.
use crate::util::hash::*;
use crate::util::iter::*;
use crate::util::parse::*;

#[derive(Copy, Clone, PartialEq, Eq, Hash)]
struct Vector {
    x: i32,
    y: i32,
    z: i32,
}

impl Vector {
    fn new(cs: [i32; 3]) -> Self {
        Vector { x: cs[0], y: cs[1], z: cs[2] }
    }

    fn manhattan(&self) -> i32 {
        self.x.abs() + self.y.abs() + self.z.abs()
    }

    fn tick(&mut self, other: &Vector) {
        self.x += other.x;
        self.y += other.y;
        self.z += other.z;
    }
}

#[derive(Copy, Clone)]
pub struct Particle {
    id: usize,
    position: Vector,
    velocity: Vector,
    acceleration: Vector,
}

impl Particle {
    fn tick(&mut self) {
        self.velocity.tick(&self.acceleration);
        self.position.tick(&self.velocity);
    }
}

pub fn parse(input: &str) -> Vec<Particle> {
    input
        .iter_signed()
        .chunk::<3>()
        .chunk::<3>()
        .enumerate()
        .map(|(id, cs)| Particle {
            id,
            position: Vector::new(cs[0]),
            velocity: Vector::new(cs[1]),
            acceleration: Vector::new(cs[2]),
        })
        .collect()
}

pub fn part1(input: &[Particle]) -> usize {
    let mut candidates = Vec::new();
    let mut min = i32::MAX;

    // Find particles with the lowest acceleration.
    for particle in input {
        let next = particle.acceleration.manhattan();

        if next < min {
            candidates.clear();
            min = next;
        }
        if next == min {
            candidates.push(*particle);
        }
    }

    // Ensure all acceleration, velocity and position vectors are "aligned", that is the
    // sign of each component is the same, for example a particle with a negative x acceleration
    // should also have a negative x velocity and negative x position.
    for _ in 0..1000 {
        candidates.iter_mut().for_each(Particle::tick);
    }

    // Tie break by velocity then by position.
    candidates.sort_unstable_by(|a, b| {
        let first = a.velocity.manhattan().cmp(&b.velocity.manhattan());
        let second = a.position.manhattan().cmp(&b.position.manhattan());
        first.then(second)
    });

    candidates[0].id
}

pub fn part2(input: &[Particle]) -> usize {
    let mut particles = input.to_vec();
    let mut collisions = FastMap::with_capacity(input.len());
    let mut exists = vec![i64::MAX; input.len()];

    for time in 1..40 {
        for (i, particle) in particles.iter_mut().enumerate() {
            // Only consider particles that haven't collided in a previous tick.
            // Multiple particles can collide in the same tick.
            if exists[i] >= time {
                particle.tick();

                if let Some(j) = collisions.insert(particle.position, i) {
                    exists[i] = time;
                    exists[j] = time;
                }
            }
        }

        collisions.clear();
    }

    exists.iter().filter(|&&t| t == i64::MAX).count()
}