aoc/year2015/day24.rs
1//! # It Hangs in the Balance
2//!
3//! To simplify things the solution assumes that the remaining items after the first best
4//! combination is found can be split evenly.
5//!
6//! This problem is the same as [`Day 17`] part two and we use the same dynamic programming approach
7//! with two tables. This approach is described in detail in the day 17 solution.
8//!
9//! The key difference is that we store the partial quantum entanglement as we build the table.
10//! If the number of items from a take/not take choice is fewer, then we just use that quantum
11//! entanglement. If the number of items is the same then we use the smaller value. Otherwise
12//! we do nothing.
13//!
14//! [`Day 17`]: crate::year2015::day17
15use crate::util::parse::*;
16
17pub fn parse(input: &str) -> Vec<usize> {
18 input.iter_unsigned().collect()
19}
20
21pub fn part1(input: &[usize]) -> usize {
22 arrangements(input, 3)
23}
24
25pub fn part2(input: &[usize]) -> usize {
26 arrangements(input, 4)
27}
28
29fn arrangements(input: &[usize], groups: usize) -> usize {
30 let goal = input.iter().sum::<usize>() / groups;
31
32 // Zero weight needs zero packages.
33 let mut minimum = vec![u32::MAX; goal + 1];
34 minimum[0] = 0;
35
36 // Define quantum entanglement for zero packages to be 1.
37 let mut qe = vec![usize::MAX; goal + 1];
38 qe[0] = 1;
39
40 for &item in input {
41 for i in (item..goal + 1).rev() {
42 let take = minimum[i - item].saturating_add(1);
43 let not_take = minimum[i];
44
45 if take < not_take {
46 // Taking the item result in fewer packages, use the new quantum entanglement even
47 // if it's greater than the existing value.
48 qe[i] = item.saturating_mul(qe[i - item]);
49 minimum[i] = take;
50 } else if take == not_take {
51 // Number of packages is the same, so choose the minimum quantum entanglement.
52 qe[i] = qe[i].min(item.saturating_mul(qe[i - item]));
53 }
54 }
55 }
56
57 qe[goal]
58}