year2016/
day19.rs

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

year2016/
day19.rs
