year2020/
day15.rs

1use utils::prelude::*;
2
3/// Generating a sequence from previous occurrences.
4#[derive(Clone, Debug)]
5pub struct Day15 {
6    starting: Vec<u32>,
7}
8
9const DENSE_THRESHOLD: u32 = 65_536;
10const SPARSE_THRESHOLD: u32 = 16_777_216;
11const SPARSE_BUCKET_SHIFT: u32 = 16;
12
13impl Day15 {
14    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
15        Ok(Self {
16            starting: parser::number_range(0..=2019)
17                .repeat(b',', 1)
18                .parse_complete(input)?,
19        })
20    }
21
22    #[must_use]
23    pub fn part1(&self) -> u32 {
24        self.number_at::<2020>()
25    }
26
27    #[must_use]
28    pub fn part2(&self) -> u32 {
29        self.number_at::<30_000_000>()
30    }
31
32    #[inline]
33    fn number_at<const TARGET: u32>(&self) -> u32 {
34        if TARGET as usize <= self.starting.len() {
35            return self.starting[TARGET as usize - 1];
36        }
37
38        let dense_limit = TARGET.min(DENSE_THRESHOLD);
39        let mut dense = vec![0u32; dense_limit as usize];
40        let middle_limit = TARGET.min(SPARSE_THRESHOLD);
41        let mut middle = vec![0u32; middle_limit.saturating_sub(DENSE_THRESHOLD) as usize];
42        let sparse_buckets = TARGET
43            .saturating_sub(SPARSE_THRESHOLD)
44            .div_ceil(1 << SPARSE_BUCKET_SHIFT) as usize;
45        let mut sparse = vec![Vec::new(); sparse_buckets];
46        let mut seen = vec![0u64; TARGET.div_ceil(64) as usize];
47
48        for (turn, &number) in self.starting[..self.starting.len() - 1].iter().enumerate() {
49            dense[number as usize] = turn as u32 + 1;
50        }
51
52        let mut number = *self.starting.last().unwrap();
53        let mut turn = self.starting.len() as u32;
54        while turn < TARGET {
55            let previous = if number < DENSE_THRESHOLD {
56                std::mem::replace(&mut dense[number as usize], turn)
57            } else if number < SPARSE_THRESHOLD {
58                // Track seen numbers in a bitset to reduce random timestamp reads
59                let base = number as usize / 64;
60                let mask = 1 << (number % 64);
61                if seen[base] & mask == 0 {
62                    seen[base] |= mask;
63                    middle[(number - DENSE_THRESHOLD) as usize] = turn;
64                    0
65                } else {
66                    std::mem::replace(&mut middle[(number - DENSE_THRESHOLD) as usize], turn)
67                }
68            } else {
69                // Store rarely repeated numbers sparsely to shrink the timestamp array
70                std::hint::cold_path();
71                let base = number as usize / 64;
72                let mask = 1 << (number % 64);
73                let bucket = ((number - SPARSE_THRESHOLD) >> SPARSE_BUCKET_SHIFT) as usize;
74                if seen[base] & mask == 0 {
75                    seen[base] |= mask;
76                    sparse[bucket].push((number, turn));
77                    0
78                } else {
79                    let (_, v) = sparse[bucket]
80                        .iter_mut()
81                        .find(|&&mut (n, _)| n == number)
82                        .expect("expected previously seen number");
83                    std::mem::replace(v, turn)
84                }
85            };
86
87            if previous == 0 {
88                turn += 1;
89
90                // Process the known zero inline to avoid another pass through the range checks
91                let previous = std::mem::replace(&mut dense[0], turn);
92                number = if previous == 0 {
93                    std::hint::cold_path();
94                    0
95                } else {
96                    turn - previous
97                };
98                turn += 1;
99            } else {
100                number = turn - previous;
101                turn += 1;
102            }
103        }
104
105        if turn == TARGET {
106            number
107        } else if turn == TARGET + 1 {
108            // Target was the zero processed as part of the double turn
109            0
110        } else {
111            panic!("Reached turn {turn} but target is {TARGET}");
112        }
113    }
114}
115
116examples!(Day15 -> (u32, u32) [
117    {input: "0,3,6", part1: 436, part2: 175594},
118    {input: "1,3,2", part1: 1, part2: 2578},
119    {input: "2,1,3", part1: 10, part2: 3544142},
120    {input: "1,2,3", part1: 27, part2: 261214},
121    {input: "2,3,1", part1: 78, part2: 6895259},
122    {input: "3,2,1", part1: 438, part2: 18},
123    {input: "3,1,2", part1: 1836, part2: 362},
124]);
year2020/day15.rs

year2020/
day15.rs
