year2024/
day11.rs

1use std::collections::VecDeque;
2use utils::hash::FastMap;
3use utils::prelude::*;
4
5/// Counting dividing stones.
6#[derive(Clone, Debug)]
7pub struct Day11 {
8    pub counts: Vec<u64>,
9    pub next: Vec<(usize, usize)>,
10    pub max_idx: Vec<usize>,
11}
12
13// Placeholder stone number, used as the second stone when a stone only splits into one
14const PLACEHOLDER: u64 = u64::MAX;
15
16impl Day11 {
17    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
18        let mut builder = Builder::new(75);
19
20        let mut counts = Vec::new();
21        for n in parser::u64().repeat(b' ', 1).parse_complete(input)? {
22            let idx = builder.index(n, 0);
23            if idx >= counts.len() {
24                counts.resize(idx + 1, 0);
25            }
26            counts[idx] += 1;
27        }
28
29        // Precompute all stone divisions
30        let (next, max_idx) = builder.finish();
31
32        Ok(Self {
33            counts,
34            next,
35            max_idx,
36        })
37    }
38
39    #[must_use]
40    pub fn part1(&self) -> u64 {
41        self.stones(25)
42    }
43
44    #[must_use]
45    pub fn part2(&self) -> u64 {
46        self.stones(75)
47    }
48
49    fn stones(&self, blinks: usize) -> u64 {
50        let mut counts = vec![0; self.next.len()];
51        let mut next = vec![0; self.next.len()];
52        counts[..self.counts.len()].copy_from_slice(&self.counts);
53
54        for blink in 0..blinks {
55            for (c, &(a, b)) in counts[..=self.max_idx[blink]].iter_mut().zip(&self.next) {
56                if *c > 0 {
57                    next[a] += *c;
58                    next[b] += *c;
59                    *c = 0;
60                }
61            }
62
63            // Clear placeholder stones
64            next[0] = 0;
65
66            (counts, next) = (next, counts);
67        }
68
69        counts.iter().sum()
70    }
71}
72
73struct Builder {
74    num_map: FastMap<u64, usize>,
75    next: Vec<(usize, usize)>,
76    max_idx: Vec<usize>,
77    todo: VecDeque<(u64, usize, u32)>,
78}
79
80impl Builder {
81    fn new(blinks: u32) -> Self {
82        let mut num_map = FastMap::with_capacity(5000);
83        let mut next = Vec::with_capacity(5000);
84
85        // Always insert placeholder stone as index 0
86        num_map.insert(PLACEHOLDER, 0);
87        next.push((0, 0));
88
89        Self {
90            num_map,
91            next,
92            todo: VecDeque::with_capacity(500),
93            max_idx: vec![0; blinks as usize],
94        }
95    }
96
97    fn index(&mut self, n: u64, blinks: u32) -> usize {
98        let next_idx = self.num_map.len();
99        *self.num_map.entry(n).or_insert_with(|| {
100            self.next.push((0, 0));
101            if (blinks as usize) < self.max_idx.len() {
102                self.max_idx[blinks as usize] = self.max_idx[blinks as usize].max(next_idx);
103                self.todo.push_back((n, next_idx, blinks));
104            }
105            next_idx
106        })
107    }
108
109    fn finish(mut self) -> (Vec<(usize, usize)>, Vec<usize>) {
110        while let Some((n, idx, blink)) = self.todo.pop_front() {
111            self.next[idx] = if n == 0 {
112                (self.index(1, blink + 1), 0)
113            } else {
114                let log = n.ilog10() + 1;
115                if log.is_multiple_of(2) {
116                    let pow = 10u64.pow(log / 2);
117                    (
118                        self.index(n / pow, blink + 1),
119                        self.index(n % pow, blink + 1),
120                    )
121                } else {
122                    (self.index(n * 2024, blink + 1), 0)
123                }
124            };
125        }
126
127        // Max index is an optimization to reduce the number of indexes iterated over in the first
128        // blinks. Ensure it is always increasing, as the insert function only updates it when
129        // adding a new number, which means that blinks with no new numbers will have max_idx = 0
130        // without this.
131        for i in 1..self.max_idx.len() {
132            self.max_idx[i] = self.max_idx[i].max(self.max_idx[i - 1]);
133        }
134
135        (self.next, self.max_idx)
136    }
137}
138
139examples!(Day11 -> (u64, u64) [
140    {input: "125 17", part1: 55312},
141]);
year2024/day11.rs

year2024/
day11.rs
