year2015/
day17.rs

1use utils::prelude::*;
2
3/// Counting subset sums.
4#[derive(Clone, Debug)]
5pub struct Day17 {
6    part1: u16,
7    part2: u16,
8}
9
10impl Day17 {
11    pub fn new(input: &str, input_type: InputType) -> Result<Self, InputError> {
12        let parsed = parser::u8().parse_lines(input)?;
13        let (part1, part2) = match input_type {
14            InputType::Example => Self::calculate::<25>(&parsed),
15            InputType::Real => Self::calculate::<150>(&parsed),
16        };
17        Ok(Self { part1, part2 })
18    }
19
20    fn calculate<const N: usize>(sizes: &[u8]) -> (u16, u16) {
21        // matrix[number of containers - 1][total capacity - 1] = combinations
22        let mut matrix = vec![[0; N]; sizes.len()];
23
24        for (i, size) in sizes.iter().copied().enumerate() {
25            // Reverse order is required to avoid double counting container
26            for containers in (1..=i).rev() {
27                for total in 0..N - size as usize {
28                    matrix[containers][total + size as usize] += matrix[containers - 1][total];
29                }
30            }
31            matrix[0][size as usize - 1] += 1;
32        }
33
34        (
35            matrix.iter().map(|x| x[N - 1]).sum(),
36            matrix
37                .iter()
38                .map(|x| x[N - 1])
39                .find(|&x| x > 0)
40                .unwrap_or(0),
41        )
42    }
43
44    #[must_use]
45    pub fn part1(&self) -> u16 {
46        self.part1
47    }
48
49    #[must_use]
50    pub fn part2(&self) -> u16 {
51        self.part2
52    }
53}
54
55examples!(Day17 -> (u16, u16) [
56    {input: "20\n15\n10\n5\n5", part1: 4, part2: 3},
57]);
year2015/day17.rs

year2015/
day17.rs
