year2017/
day20.rs

1use std::collections::HashMap;
2use utils::point::Point3D;
3use utils::prelude::*;
4
5/// Simulating colliding particles.
6#[derive(Clone, Debug)]
7pub struct Day20 {
8    particles: Vec<Particle>,
9}
10
11#[derive(Clone, Debug)]
12struct Particle {
13    position: Point3D<i64>,
14    velocity: Point3D<i64>,
15    acceleration: Point3D<i64>,
16}
17
18impl Day20 {
19    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
20        let vector = parser::i64()
21            .repeat_n(b',')
22            .map(|[x, y, z]| Point3D::new(x, y, z));
23
24        Ok(Self {
25            particles: vector
26                .with_prefix("p=<")
27                .then(vector.with_prefix(">, v=<"))
28                .then(vector.with_prefix(">, a=<").with_suffix(">"))
29                .map(|(position, velocity, acceleration)| Particle {
30                    position,
31                    velocity,
32                    acceleration,
33                })
34                .parse_lines(input)?,
35        })
36    }
37
38    #[must_use]
39    pub fn part1(&self) -> usize {
40        self.particles
41            .iter()
42            .enumerate()
43            .min_by_key(|&(_, p)| p.position_at_time(1_000_000).manhattan_distance())
44            .unwrap()
45            .0
46    }
47
48    #[must_use]
49    pub fn part2(&self) -> usize {
50        let mut particles = self.particles.clone();
51        let mut destroyed = vec![false; particles.len()];
52
53        let mut positions = HashMap::new();
54        let mut last_destroyed = 0;
55        for t in 0.. {
56            positions.clear();
57
58            for (i, p) in particles.iter_mut().enumerate() {
59                if destroyed[i] {
60                    continue;
61                }
62
63                p.tick();
64
65                if let Some(j) = positions.insert(p.position, i) {
66                    destroyed[i] = true;
67                    destroyed[j] = true;
68                    last_destroyed = t;
69                }
70            }
71
72            // Stop when nothing has been destroyed for 10 turns and at least one particle has been
73            // destroyed.
74            if last_destroyed <= t - 10 && destroyed.iter().any(|&x| x) {
75                break;
76            }
77        }
78
79        particles.len() - destroyed.iter().filter(|&&p| p).count()
80    }
81}
82
83impl Particle {
84    fn position_at_time(&self, time: u64) -> Point3D<i64> {
85        self.position
86            + (self.velocity * time as i64)
87            + (self.acceleration * (time as i64 * time as i64 / 2))
88    }
89
90    fn tick(&mut self) {
91        self.velocity += self.acceleration;
92        self.position += self.velocity;
93    }
94}
95
96examples!(Day20 -> (usize, usize) [
97    {
98        input: "p=<3,0,0>, v=<2,0,0>, a=<-1,0,0>\n\
99            p=<4,0,0>, v=<0,0,0>, a=<-2,0,0>",
100        part1: 0,
101    },
102    {
103        input: "p=<-6,0,0>, v=<3,0,0>, a=<0,0,0>\n\
104            p=<-4,0,0>, v=<2,0,0>, a=<0,0,0>\n\
105            p=<-2,0,0>, v=<1,0,0>, a=<0,0,0>\n\
106            p=<3,0,0>, v=<-1,0,0>, a=<0,0,0>",
107        part2: 1,
108    },
109]);
year2017/day20.rs

year2017/
day20.rs
