year2016/
day19.rs

1use std::num::NonZeroU32;
2use utils::prelude::*;
3
4/// Finding the winners of counting-out games.
5#[derive(Clone, Debug)]
6pub struct Day19 {
7    elves: NonZeroU32,
8}
9
10impl Day19 {
11    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
12        Ok(Self {
13            elves: parser::nonzero_u32().parse_complete(input)?,
14        })
15    }
16
17    /// See <https://en.wikipedia.org/wiki/Josephus_problem#k_=_2>.
18    #[must_use]
19    pub fn part1(&self) -> u32 {
20        let elves = self.elves.get();
21        2 * (elves - elves.isolate_highest_one()) + 1
22    }
23
24    /// See <https://www.reddit.com/r/adventofcode/comments/5j4lp1/2016_day_19_solutions/>.
25    ///
26    /// If the number of elves is a power of 3, the final elf wins. Otherwise, calculate the
27    /// largest power of 3 smaller or equal to the number of elves (`pow3`). Less than `2 * pow3`
28    /// the winner is `elves - pow3`, and after that it `2 * (elves - pow3) + pow3`.
29    #[must_use]
30    pub fn part2(&self) -> u32 {
31        let elves = self.elves.get();
32        let pow3 = 3u32.pow(elves.ilog(3));
33        if pow3 == elves {
34            pow3
35        } else {
36            let remainder = elves - pow3;
37            if remainder <= pow3 {
38                remainder
39            } else {
40                2 * remainder - pow3
41            }
42        }
43    }
44}
45
46examples!(Day19 -> (u32, u32) [
47    {input: "5", part1: 3, part2: 2},
48]);
year2016/day19.rs

year2016/
day19.rs
