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

year2017/
day20.rs
