aoc/year2020/
day15.rs

1//! # Rambunctious Recitation
2//!
3//! For efficiency the `vec` storing the last previously spoken turn of numbers is `u32`.
4//! Each difference is at least one so zero is used as a special value to indicate numbers not
5//! seen before.
6//!
7//! To speed things up even more, we notice that most large numbers over a certain threshold are
8//! spoken only once. Storing if numbers have been seen before in a compact bitset prevents
9//! expensive reads to main memory and halves the time needed for the solution.
10//!
11//! Zero occurs the most so storing it as a dedicated variable saves another 2% of execution time.
12use crate::util::parse::*;
13
14const THRESHOLD: usize = 0x10000;
15
16pub fn parse(input: &str) -> Vec<usize> {
17    input.iter_unsigned().collect()
18}
19
20pub fn part1(input: &[usize]) -> usize {
21    play(input, 2020)
22}
23
24pub fn part2(input: &[usize]) -> usize {
25    play(input, 30_000_000)
26}
27
28fn play(input: &[usize], rounds: usize) -> usize {
29    let size = input.len() - 1;
30
31    let mut last = input[size];
32    let mut zeroth = 0;
33    let mut spoken = vec![0; rounds];
34    let mut seen = vec![0_u64; rounds / 64];
35
36    for i in 0..size {
37        if input[i] == 0 {
38            zeroth = i + 1;
39        } else {
40            spoken[input[i]] = (i + 1) as u32;
41        }
42    }
43
44    for i in input.len()..rounds {
45        if last == 0 {
46            // Handle zero specially as it occurs the most.
47            let previous = zeroth;
48            zeroth = i;
49            last = if previous == 0 { 0 } else { i - previous };
50        } else if last < THRESHOLD {
51            // Smaller numbers occur frequently so skip previously seen bitset check.
52            let previous = spoken[last] as usize;
53            spoken[last] = i as u32;
54            last = if previous == 0 { 0 } else { i - previous };
55        } else {
56            // An array of 30 million `u32`s needs 120 MB of memory which exceeds most caches.
57            // Writing and reading to random locations in this large array goes to main memory
58            // which is slow. Store if a number has been seen before in a compact bitset,
59            // needing only a more cache friendly 4 MB.
60            let base = last / 64;
61            let mask = 1 << (last % 64);
62
63            if seen[base] & mask == 0 {
64                seen[base] |= mask;
65                spoken[last] = i as u32;
66                last = 0;
67            } else {
68                let previous = spoken[last] as usize;
69                spoken[last] = i as u32;
70                last = i - previous;
71            }
72        }
73    }
74
75    last
76}
aoc/year2020/day15.rs

aoc/year2020/
day15.rs
