year2015/
day20.rs

Help
1use utils::prelude::*;
2
3/// Divisor function.
4#[derive(Clone, Debug)]
5pub struct Day20 {
6    part1: u32,
7    part2: u32,
8}
9
10impl Day20 {
11    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
12        let threshold: u32 = input
13            .trim_ascii_end()
14            .parse()
15            .map_err(|_| InputError::new(input, 0, "expected u32"))?;
16
17        // (threshold/10) + 1 should always find the solutions, but attempt to find the solutions
18        // with smaller & significantly faster upper bounds first
19        for max_bound in [
20            threshold.div_ceil(40) + 1,
21            threshold.div_ceil(20) + 1,
22            threshold.div_ceil(10) + 1,
23        ] {
24            if let Some((part1, part2)) = Self::try_solve(threshold, max_bound) {
25                return Ok(Day20 { part1, part2 });
26            }
27        }
28
29        unreachable!();
30    }
31
32    fn try_solve(threshold: u32, len: u32) -> Option<(u32, u32)> {
33        let mut houses = vec![0; len as usize];
34
35        // Elves < len/50 would visit more than 50 houses, visit the first 50 for part 2 solution
36        for elf in 1..len / 50 {
37            for house in (elf..len).step_by(elf as usize).take(50) {
38                houses[house as usize] += elf;
39            }
40        }
41
42        // Elves > len/50 will visit at most 50 houses
43        for elf in (len / 50).max(1)..len / 2 {
44            for house in (elf..len).step_by(elf as usize) {
45                houses[house as usize] += elf;
46            }
47        }
48
49        // Elves >= len/2 will visit 1 house
50        for elf in (len / 2).max(1)..len {
51            houses[elf as usize] += elf;
52        }
53
54        let part2_threshold = threshold.div_ceil(11);
55        let part2 = houses.iter().position(|&c| c >= part2_threshold)?;
56
57        // After finding part 2 solution, process the previously skipped houses for elves < len/50
58        for elf in 1..len / 50 {
59            for house in (elf * 51..len).step_by(elf as usize) {
60                houses[house as usize] += elf;
61            }
62        }
63
64        let part1_threshold = threshold.div_ceil(10);
65        let part1 = houses.iter().position(|&c| c >= part1_threshold)?;
66
67        Some((part1 as u32, part2 as u32))
68    }
69
70    #[must_use]
71    pub fn part1(&self) -> u32 {
72        self.part1
73    }
74
75    #[must_use]
76    pub fn part2(&self) -> u32 {
77        self.part2
78    }
79}
80
81examples!(Day20 -> (usize, usize) []);
year2015/day20.rs

year2015/
day20.rs
