year2015/
day20.rs

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

year2015/
day20.rs
