aoc/year2024/
day11.rs

1//! # Plutonian Pebbles
2//!
3//! The transformation rules have any 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 contigous 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 contigous 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    // Amount of each stone of a particular number.
31    let mut current = Vec::new();
32
33    // Initialize stones from input.
34    for &number in input {
35        if let Some(&index) = indices.get(&number) {
36            current[index] += 1;
37        } else {
38            indices.insert(number, indices.len());
39            todo.push(number);
40            current.push(1);
41        }
42    }
43
44    for _ in 0..blinks {
45        // If a stone number has already been seen then return its index,
46        // otherwise queue it for processing during the next blink.
47        let numbers = todo;
48        todo = Vec::with_capacity(200);
49
50        let mut index_of = |number| {
51            let size = indices.len();
52            *indices.entry(number).or_insert_with(|| {
53                todo.push(number);
54                size
55            })
56        };
57
58        // Apply the transformation logic to stones added in the previous blink.
59        for number in numbers {
60            let (first, second) = if number == 0 {
61                (index_of(1), usize::MAX)
62            } else {
63                let digits = number.ilog10() + 1;
64                if digits % 2 == 0 {
65                    let power = 10_u64.pow(digits / 2);
66                    (index_of(number / power), index_of(number % power))
67                } else {
68                    (index_of(number * 2024), usize::MAX)
69                }
70            };
71
72            stones.push((first, second));
73        }
74
75        // Add amount of each stone to either 1 or 2 stones in the next blink.
76        let mut next = vec![0; indices.len()];
77
78        for (&(first, second), amount) in stones.iter().zip(current) {
79            next[first] += amount;
80            if second != usize::MAX {
81                next[second] += amount;
82            }
83        }
84
85        current = next;
86    }
87
88    current.iter().sum()
89}
aoc/year2024/day11.rs

aoc/year2024/
day11.rs
