year2024/
day11.rs

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

year2024/
day11.rs
