year2015/
day24.rs

1use utils::prelude::*;
2
3/// Minimizing subset size & product.
4#[derive(Clone, Debug)]
5pub struct Day24 {
6    presents: Vec<u32>,
7    remaining_totals: Vec<u32>,
8    sum: u32,
9}
10
11impl Day24 {
12    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
13        let mut presents = parser::u32().parse_lines(input)?;
14        presents.sort_unstable_by(|a, b| b.cmp(a));
15
16        // Pre-calculate the total of the remaining presents for each position, to avoid repeatedly
17        // summing the remainder of the array in min_quantum_entanglement
18        let mut remaining_totals = presents
19            .iter()
20            .rev()
21            .scan(0, |acc, x| {
22                *acc += x;
23                Some(*acc)
24            })
25            .collect::<Vec<_>>();
26        remaining_totals.reverse();
27
28        let sum: u32 = remaining_totals.first().copied().unwrap_or(0);
29        if sum % 12 != 0 {
30            return Err(InputError::new(input, 0, "Total must be multiple of 12"));
31        }
32
33        Ok(Self {
34            presents,
35            remaining_totals,
36            sum,
37        })
38    }
39
40    #[must_use]
41    pub fn part1(&self) -> u64 {
42        let mut min = (u32::MAX, u64::MAX);
43        self.min_quantum_entanglement(self.sum / 3, 0, 0, 1, &mut min);
44        min.1
45    }
46
47    #[must_use]
48    pub fn part2(&self) -> u64 {
49        let mut min = (u32::MAX, u64::MAX);
50        self.min_quantum_entanglement(self.sum / 4, 0, 0, 1, &mut min);
51        min.1
52    }
53
54    fn min_quantum_entanglement(
55        &self,
56        remaining: u32,
57        start_index: usize,
58        count: u32,
59        product: u64,
60        min_found: &mut (u32, u64),
61    ) {
62        if remaining == 0 {
63            *min_found = (*min_found).min((count, product));
64            return;
65        }
66
67        // Stop searching early if the group would contain more packages than the current minimum
68        if count >= min_found.0 {
69            return;
70        }
71
72        // Stop searching early if the group can't be competed with the remaining presents
73        // Equivalent to `self.presents[start_index..].iter().sum::<u32>() < remaining`
74        if self.remaining_totals.get(start_index).copied().unwrap_or(0) < remaining {
75            return;
76        }
77
78        for (i, &size) in self.presents[start_index..].iter().enumerate() {
79            if size <= remaining {
80                self.min_quantum_entanglement(
81                    remaining - size,
82                    start_index + i + 1,
83                    count + 1,
84                    product * u64::from(size),
85                    min_found,
86                )
87            }
88        }
89    }
90}
91
92examples!(Day24 -> (u64, u64) [
93    {input: "1\n2\n3\n4\n5\n7\n8\n9\n10\n11", part1: 99, part2: 44},
94]);
year2015/day24.rs

year2015/
day24.rs
