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//! ## Part One
9//!
10//! Tackling this with dynamic programming provides a much faster approach. We build a table similar
11//! to but not exactly the same as the [knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem).
12//! This approach is built atop a solution provided by [`e_blake`](http://reddit.com/u/e_blake)
13//! preserved in the [commit history](https://github.com/maneatingape/advent-of-code-rust/blob/4a08f73b40c5b93a59f0c595b97879192f986c31/src/year2015/day17.rs).
14//!
15//! The table has `target + 1` columns and `containers + 1` rows.
16//! Each `table[row, col]` is computed row by row from the sum of:
17//!
18//! * Not taking the current item, using just the existing number of ways to make the target
19//!   `table[row - 1, col]`
20//! * Taking the current item, using the existing number of ways to make the target weight less
21//!   the weight of the current item `table[row - 1, col - item]`.
22//!
23//! The table for the example looks like:
24//!
25//! ```none
26//!     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Initial
27//!     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] 20
28//!     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] 15
29//!     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1] 10
30//!     [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2] First 5
31//!     [1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 3, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4] Second 5
32//! ```
33//!
34//! The answer `4` is the bottom right cell. Since only the previous row is needed to compute
35//! the current row, we optimize by only storing a single row instead of the entire table
36//! and updating in place.
37//!
38//! ## Part Two
39//!
40//! The key insight is to keep *two* tables. The first table tracks the number of combinations as
41//! before. The second table tracks the minimum number of containers needed to store each volume
42//! up to and including the target size.
43//!
44//! If taking the item results in fewer containers then we add that number of combinations.
45//! Vice-versa if not taking the item results in fewer containers then we don't include it. If both
46//! taking and not taking the item results in the same number of containers then we add both.
47//!
48//! The new minima table for the example using `u32::MAX` to represent `∞` is:
49//!
50//! ```none
51//!     [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] Initial
52//!     [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, ∞] 20
53//!     [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, ∞] 15
54//!     [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 2] 10
55//!     [0, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 2] First 5
56//!     [0, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 1, ∞, ∞, ∞, ∞, 2] Second 5
57//! ```
58//!
59//! The minimum number of containers needed to make the target is the bottom right cell (2).
60//! The combinations table with the minimum restriction is:
61//!
62//! ```none
63//!     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Initial
64//!     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] 20
65//!     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] 15
66//!     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1] 10
67//!     [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2] First 5
68//!     [1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3] Second 5
69//! ```
70use crate::util::parse::*;
71
72pub fn parse(input: &str) -> Vec<usize> {
73    input.iter_unsigned().collect()
74}
75
76pub fn part1(input: &[usize]) -> u32 {
77    part1_testable(input, 150)
78}
79
80pub fn part2(input: &[usize]) -> u32 {
81    part2_testable(input, 150)
82}
83
84pub fn part1_testable(input: &[usize], goal: usize) -> u32 {
85    // There is one way to store 0 liters with 0 containers.
86    let mut ways = vec![0; goal + 1];
87    ways[0] = 1;
88
89    for &item in input {
90        // Iterating backwards enables us to update the same row in place
91        // instead of storing the entire table.
92        for i in (item..goal + 1).rev() {
93            ways[i] += ways[i - item];
94        }
95    }
96
97    ways[goal]
98}
99
100pub fn part2_testable(input: &[usize], goal: usize) -> u32 {
101    let mut ways = vec![0; goal + 1];
102    ways[0] = 1;
103
104    // The minimum number of containers to store 0 litres is 0.
105    let mut minimum = vec![u32::MAX; goal + 1];
106    minimum[0] = 0;
107
108    for &item in input {
109        for i in (item..goal + 1).rev() {
110            // Saturating add prevents overflow if the minimum is u32::MAX.
111            let take = minimum[i - item].saturating_add(1);
112            let not_take = minimum[i];
113
114            if take < not_take {
115                // Use only the number of combinations that result from taking the container.
116                ways[i] = ways[i - item];
117                minimum[i] = take;
118            } else if take == not_take {
119                // Use both combinations from taking and not taking the container.
120                ways[i] += ways[i - item];
121            }
122        }
123    }
124
125    ways[goal]
126}
aoc/year2015/day17.rs

aoc/year2015/
day17.rs
