year2017/
day06.rs

1use utils::prelude::*;
2
3/// Finding cycles.
4///
5/// See <https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algorithm>, which avoids storing and
6/// hashing every visited state at the expense of calculating extra iterations.
7#[derive(Clone, Debug)]
8pub struct Day06 {
9    part1: u32,
10    part2: u32,
11}
12
13impl Day06 {
14    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
15        let banks = parser::u32()
16            .with_suffix(parser::one_of((b' ', b'\t', parser::eof())))
17            .parse_all(input)?;
18
19        let (mut power, mut lambda) = (1, 1);
20        let mut tortoise = banks.clone();
21        let mut hare = banks.clone();
22        Self::next(&mut hare);
23
24        while tortoise != hare {
25            if power == lambda {
26                tortoise.copy_from_slice(hare.as_slice());
27                power *= 2;
28                lambda = 0;
29            }
30            Self::next(&mut hare);
31            lambda += 1;
32        }
33
34        tortoise.copy_from_slice(banks.as_slice());
35        hare.copy_from_slice(banks.as_slice());
36        for _ in 0..lambda {
37            Self::next(&mut hare);
38        }
39
40        let mut mu = 0;
41        while tortoise != hare {
42            Self::next(&mut tortoise);
43            Self::next(&mut hare);
44            mu += 1;
45        }
46
47        Ok(Self {
48            part1: mu + lambda,
49            part2: lambda,
50        })
51    }
52
53    fn next(banks: &mut [u32]) {
54        let (mut idx, mut remaining) = banks
55            .iter()
56            .copied()
57            .enumerate()
58            .rev()
59            .max_by_key(|&(_, v)| v)
60            .unwrap();
61
62        banks[idx] = 0;
63
64        while remaining > 0 {
65            idx = (idx + 1) % banks.len();
66            banks[idx] += 1;
67            remaining -= 1;
68        }
69    }
70
71    #[must_use]
72    pub fn part1(&self) -> u32 {
73        self.part1
74    }
75
76    #[must_use]
77    pub fn part2(&self) -> u32 {
78        self.part2
79    }
80}
81
82examples!(Day06 -> (u32, u32) [
83    {input: "0\t2\t7\t0", part1: 5, part2: 4},
84]);
year2017/day06.rs

year2017/
day06.rs
