Skip to main content

advent_of_code/year2016/
day19.rs

1use crate::input::Input;
2
3pub fn solve(input: &Input) -> Result<u32, String> {
4    let n = u32::from(
5        input
6            .text
7            .parse::<std::num::NonZeroU32>()
8            .map_err(|e| format!("Invalid number of elves: {e}"))?,
9    );
10
11    if input.is_part_one() {
12        // See "The Josephus Problem - Numberphile": https://www.youtube.com/watch?v=uCsD3ZGzMgE
13        let most_significant_bit = 1 << (u32::BITS - n.leading_zeros() - 1);
14        let with_msb_cleared = n & !most_significant_bit;
15        let with_lsb_added = (with_msb_cleared << 1) | 1;
16        Ok(with_lsb_added)
17    } else {
18        let power_three = 3_u32.pow(n.ilog(3));
19        if n == power_three {
20            Ok(n)
21        } else if n - power_three <= power_three {
22            Ok(n - power_three)
23        } else {
24            Ok(2 * n - 3 * power_three)
25        }
26    }
27}
28
29#[test]
30pub fn tests() {
31    test_part_one!("5" => 3);
32    test_part_two!("5" => 2);
33
34    let real_input = include_str!("day19_input.txt");
35    test_part_one!(real_input => 1_808_357);
36    test_part_two!(real_input => 1_407_007);
37}