aoc/year2020/
day15.rs

1//! # Rambunctious Recitation
2//!
3//! Hybrid solution that uses both a `vec` and [`FastMap`] to store previously seen values.
4//! This approach is faster than using either data structure alone. The threshold is chosen so that
5//! about 85% of values are stored in the `vec`.
6//!
7//! To save space the `vec` is `u32` instead of `usize`. Each difference is at least one so we can
8//! use zero as a special value to indicate numbers not seen before.
9//!
10//! Accessing the map uses the [`Entry`] method as this reduces two key lookups to one.
11//!
12//! [`FastMap`]: crate::util::hash
13//! [`Entry`]: std::collections::hash_map::Entry
14use crate::util::hash::*;
15use crate::util::parse::*;
16
17const THRESHOLD: usize = 1_000_000;
18
19pub fn parse(input: &str) -> Vec<usize> {
20    input.iter_unsigned().collect()
21}
22
23pub fn part1(input: &[usize]) -> usize {
24    play(input, 2020)
25}
26
27pub fn part2(input: &[usize]) -> usize {
28    play(input, 30_000_000)
29}
30
31fn play(input: &[usize], rounds: usize) -> usize {
32    let size = input.len() - 1;
33    let mut last = input[size];
34
35    let mut spoken_low = vec![0; rounds.min(THRESHOLD)];
36    let mut spoken_high = FastMap::with_capacity(rounds / 5);
37
38    for i in 0..size {
39        spoken_low[input[i]] = (i + 1) as u32;
40    }
41
42    for i in input.len()..rounds {
43        if last < THRESHOLD {
44            let previous = spoken_low[last] as usize;
45            spoken_low[last] = i as u32;
46            last = if previous == 0 { 0 } else { i - previous };
47        } else {
48            spoken_high
49                .entry(last as u32)
50                .and_modify(|previous| {
51                    last = i - *previous as usize;
52                    *previous = i as u32;
53                })
54                .or_insert_with(|| {
55                    last = 0;
56                    i as u32
57                });
58        }
59    }
60
61    last
62}
aoc/year2020/day15.rs

aoc/year2020/
day15.rs
