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 std::mem::replace;
13
14use crate::util::parse::*;
15
16const THRESHOLD: usize = 0x10000;
17
18pub fn parse(input: &str) -> Vec<usize> {
19    input.iter_unsigned().collect()
20}
21
22pub fn part1(input: &[usize]) -> usize {
23    play(input, 2020)
24}
25
26pub fn part2(input: &[usize]) -> usize {
27    play(input, 30_000_000)
28}
29
30fn play(input: &[usize], rounds: usize) -> usize {
31    let (last, starting) = input.split_last().unwrap();
32
33    let mut last = *last;
34    let mut zeroth = 0;
35    let mut spoken = vec![0; rounds];
36    let mut seen = vec![0_u64; rounds / 64];
37
38    for (i, &n) in starting.iter().enumerate() {
39        if n == 0 {
40            zeroth = i + 1;
41        } else {
42            spoken[n] = (i + 1) as u32;
43        }
44    }
45
46    for i in input.len()..rounds {
47        if last == 0 {
48            // Handle zero specially as it occurs the most.
49            let previous = replace(&mut zeroth, i);
50            last = if previous == 0 { 0 } else { i - previous };
51        } else if last < THRESHOLD {
52            // Smaller numbers occur frequently so skip previously seen bitset check.
53            let previous = replace(&mut spoken[last], i as u32) as usize;
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 = replace(&mut spoken[last], i as u32) as usize;
69                last = i - previous;
70            }
71        }
72    }
73
74    last
75}
aoc/year2020/day15.rs

aoc/year2020/
day15.rs
