aoc/year2015/
day17.rs

1//! # No Such Thing as Too Much
2//!
3//! Given `n` items the number of possible subsets is `2ⁿ`. We could brute force through each
4//! subset by iterating from 0 to 2ⁿ using the binary bits to indicate if a container is present.
5//! This will work but is a little slow as there are 20 containers, giving 2²⁰ = 1048576
6//! combinations to check.
7//!
8//! We speed things up by noticing that some containers are the same size, so the total number
9//! of combinations is fewer. For example if there are 3 containers of size `x` that is only
10//! 4 possibilities rather than 8.
11//!
12//! We have to multiply the result by [nCr](https://en.wikipedia.org/wiki/Combination)
13//! or the number of ways of choosing `r` items from `n`. For example if 2 containers out of 3
14//! are used in a solution then there are 3 ways of selecting the 2 containers. This solution
15//! hardcodes nCr tables for `n` up to 4.
16//!
17//! As an optimization containers are ordered from largest to smallest so that the
18//! recursive checking can exit as early as possible if we exceed 150 litres.
19use crate::util::parse::*;
20use std::collections::BTreeMap;
21
22/// nCr for `n` from 0 to 4 inclusive.
23const NCR: [[u32; 5]; 5] =
24    [[1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 2, 1, 0, 0], [1, 3, 3, 1, 0], [1, 4, 6, 4, 1]];
25
26struct State {
27    size: Vec<u32>,
28    freq: Vec<usize>,
29    result: Vec<u32>,
30}
31
32pub fn parse(input: &str) -> Vec<u32> {
33    // Collect size and frequency of each container.
34    let mut containers = BTreeMap::new();
35
36    for size in input.iter_unsigned() {
37        containers.entry(size).and_modify(|e| *e += 1).or_insert(1);
38    }
39
40    // Convenience struct to group size and frequency of each container, plus the number of
41    // combinations grouped by total number of containers.
42    let mut state = State {
43        size: containers.keys().copied().collect(),
44        freq: containers.values().copied().collect(),
45        result: vec![0; containers.len()],
46    };
47
48    // As an optimization order largest containers first so that we can exit early if the total
49    // size is greater than 150.
50    state.size.reverse();
51    state.freq.reverse();
52
53    combinations(&mut state, 0, 0, 0, 1);
54    state.result
55}
56
57/// We only care about the total combinations, so sum the entire vec.
58pub fn part1(input: &[u32]) -> u32 {
59    input.iter().sum()
60}
61
62/// We want the number of combination with the fewest containers, so find first non-zero value.
63pub fn part2(input: &[u32]) -> u32 {
64    *input.iter().find(|&&n| n > 0).unwrap()
65}
66
67/// Recursively try every possible combination, returning early if the size exceeds 150 litres.
68///
69/// `state`: Convenience struct to reduce parameters
70/// `index`: Current container
71/// `containers`: Number of containers used so far
72/// `litres`: How many litres of eggnog stored so far
73/// `factor`: The total different number of ways of selecting previous containers
74fn combinations(state: &mut State, index: usize, containers: usize, litres: u32, factor: u32) {
75    let n = state.freq[index];
76    let mut next = litres;
77
78    for r in 0..(n + 1) {
79        if next < 150 {
80            if index < state.size.len() - 1 {
81                combinations(state, index + 1, containers + r, next, factor * NCR[n][r]);
82            }
83        } else {
84            if next == 150 {
85                state.result[containers + r] += factor * NCR[n][r];
86            }
87            break;
88        }
89        next += state.size[index];
90    }
91}
aoc/year2015/day17.rs

aoc/year2015/
day17.rs
