aoc/year2017/
day17.rs

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

aoc/year2017/
day17.rs
