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//! The number of skips grows geometrically, or `O(ln n)` overall effort, learning the answer in
18//! just a few thousand iterations.
19//!
20//! [`div_ceil`]: usize::div_ceil
21use crate::util::parse::*;
22
23type Input = (usize, usize);
24
25pub fn parse(input: &str) -> Input {
26    let step = input.unsigned::<usize>() + 1;
27
28    // For part one, track the index every node had when inserted.
29    let mut index = 0;
30    let indices: Vec<_> = (1..=2017)
31        .map(|n| {
32            index = (index + step) % n;
33            index
34        })
35        .collect();
36
37    // Now back up to find the prior node that shares the same index, accounting for when
38    // the index moved because an intermediate number was assigned an earlier index.
39    let mut next = (index + 1) % 2017;
40    let mut part_one = 0;
41
42    for (i, &o) in indices.iter().enumerate().rev() {
43        if o == next {
44            part_one = i + 1;
45            break;
46        }
47        if o < next {
48            next -= 1;
49        }
50    }
51
52    // For part two, we only need to focus on nodes inserted at index 0.
53    let mut n = 2017;
54    let mut part_two = 0;
55
56    while n <= 50_000_000 {
57        if index == 0 {
58            part_two = n;
59        }
60
61        let skip = (n - index).div_ceil(step - 1);
62        n += skip;
63        // Here, n is larger than 2017, while step is on the order of 300 to 400; therefore, step
64        // wraps only once, and subtraction works instead of modulus.
65        index = index + skip * step - n;
66    }
67
68    (part_one, part_two)
69}
70
71pub fn part1(input: &Input) -> usize {
72    input.0
73}
74
75pub fn part2(input: &Input) -> usize {
76    input.1
77}
aoc/year2017/day17.rs

aoc/year2017/
day17.rs
