aoc/year2017/
day17.rs

1//! # Spinlock
2//!
3//! There are two insights that speed up part two.
4//!
5//! The first is that we don't need a buffer. We only need to preserve the last value inserted
6//! whenever the index becomes zero. Once 50 million values have been inserted then this value
7//! is the final result.
8//!
9//! The second trick is realizing that we can insert multiple values at a time before the index
10//! wraps around. For example if the index is 1, the current value 10,000 and the step 300,
11//! then we can insert 34 values at once. The [`div_ceil`] method is perfect for this computation.
12//!
13//! This reduces the number of loops needed to approximately √50000000 = 7071.
14//!
15//! [`div_ceil`]: usize::div_ceil
16use crate::util::parse::*;
17
18pub fn parse(input: &str) -> usize {
19    input.unsigned()
20}
21
22pub fn part1(input: &usize) -> u16 {
23    let step = input + 1;
24    let mut index = 0;
25    let mut buffer = vec![0];
26
27    for n in 0..2017 {
28        index = (index + step) % buffer.len();
29        buffer.insert(index, n + 1);
30    }
31
32    buffer[(index + 1) % buffer.len()]
33}
34
35pub fn part2(input: &usize) -> usize {
36    let step = input + 1;
37    let mut n: usize = 1;
38    let mut index = 0;
39    let mut result = 0;
40
41    while n <= 50_000_000 {
42        if index == 0 {
43            result = n;
44        }
45
46        let skip = (n - index).div_ceil(step);
47        n += skip;
48        index = (index + skip * step) % n;
49    }
50
51    result
52}
aoc/year2017/day17.rs

aoc/year2017/
day17.rs
