aoc/year2015/
day24.rs

1//! # It Hangs in the Balance
2//!
3//! To simplify things assumes that the remaining items after the first best combination is found
4//! can be split evenly.
5//!
6//! Sorts the weights in ascending order, then tries combinations of increasing size until a
7//! match in found. This will be the answer since the package count is the smallest and the
8//! quantum entaglement will also be the lowest.
9use crate::util::bitset::*;
10use crate::util::parse::*;
11
12pub fn parse(input: &str) -> Vec<u32> {
13    let mut packages: Vec<_> = input.iter_unsigned().collect();
14    packages.sort_unstable();
15    packages
16}
17
18pub fn part1(input: &[u32]) -> u64 {
19    combinations(input, 3)
20}
21
22pub fn part2(input: &[u32]) -> u64 {
23    combinations(input, 4)
24}
25
26/// Breadth first search over all possible package combinations as we want the fewest possible
27/// packages that sum to the target weight. Uses a bitmask as a set for each package combination.
28fn combinations(input: &[u32], groups: u32) -> u64 {
29    let target = input.iter().sum::<u32>() / groups;
30    let mut current = &mut Vec::with_capacity(100_000);
31    let mut next = &mut Vec::with_capacity(100_000);
32
33    // Start with no packages.
34    current.push((0_u32, 0_u32));
35
36    loop {
37        for (weight, packages) in current.drain(..) {
38            // Find the next highest power of two.
39            let start = 32 - packages.leading_zeros() as usize;
40
41            // Add one package at a time to this combination.
42            for i in start..input.len() {
43                let next_weight = weight + input[i];
44                let next_packages = packages | (1 << i);
45
46                if next_weight == target {
47                    return next_packages.biterator().map(|i| input[i] as u64).product();
48                }
49                if next_weight > target {
50                    break;
51                }
52
53                next.push((next_weight, next_packages));
54            }
55        }
56
57        (current, next) = (next, current);
58    }
59}
aoc/year2015/day24.rs

aoc/year2015/
day24.rs
