aoc/year2024/
day11.rs

1//! # Plutonian Pebbles
2//!
3//! The transformation rules have an interesting property that the total number of
4//! distinct stone numbers is not very large, about 2000 for part one and 4000 for part two.
5//!
6//! This means that we can store the count of each distinct stone in a small contiguous array
7//! that is much faster to process than a recursive memoization approach.
8use crate::util::hash::*;
9use crate::util::parse::*;
10
11pub fn parse(input: &str) -> Vec<u64> {
12    input.iter_unsigned().collect()
13}
14
15pub fn part1(input: &[u64]) -> u64 {
16    count(input, 25)
17}
18
19pub fn part2(input: &[u64]) -> u64 {
20    count(input, 75)
21}
22
23fn count(input: &[u64], blinks: usize) -> u64 {
24    // Allocate enough room to prevent reallocations.
25    let mut stones = Vec::with_capacity(5000);
26    // Maps number on stone to a much smaller contiguous range of indices.
27    let mut indices = FastMap::with_capacity(5000);
28    // Numbers of any new stones generated during the previous blink.
29    let mut todo = Vec::new();
30    let mut numbers = Vec::new();
31    // Amount of each stone of a particular number.
32    let mut current = Vec::with_capacity(5000);
33    let mut next = Vec::with_capacity(5000);
34
35    // Initialize stones from input.
36    for &number in input {
37        if let Some(&index) = indices.get(&number) {
38            current[index] += 1;
39        } else {
40            indices.insert(number, indices.len());
41            todo.push(number);
42            current.push(1);
43        }
44    }
45
46    for _ in 0..blinks {
47        // If a stone number has already been seen then return its index,
48        // otherwise queue it for processing during the next blink.
49        (numbers, todo) = (todo, numbers);
50
51        let mut index_of = |number| {
52            let size = indices.len();
53            *indices.entry(number).or_insert_with(|| {
54                todo.push(number);
55                size
56            })
57        };
58
59        // Apply the transformation logic to stones added in the previous blink.
60        for number in numbers.drain(..) {
61            let (first, second) = if number == 0 {
62                (index_of(1), usize::MAX)
63            } else {
64                let digits = number.ilog10() + 1;
65                if digits.is_multiple_of(2) {
66                    let power = 10_u64.pow(digits / 2);
67                    (index_of(number / power), index_of(number % power))
68                } else {
69                    (index_of(number * 2024), usize::MAX)
70                }
71            };
72
73            stones.push((first, second));
74        }
75
76        // Add amount of each stone to either 1 or 2 stones in the next blink.
77        next.clear();
78        next.resize(indices.len(), 0);
79
80        for (&(first, second), &amount) in stones.iter().zip(&current) {
81            next[first] += amount;
82            if second != usize::MAX {
83                next[second] += amount;
84            }
85        }
86
87        (current, next) = (next, current);
88    }
89
90    current.iter().sum()
91}
aoc/year2024/day11.rs

aoc/year2024/
day11.rs
