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::parse::*;
10
11pub fn parse(input: &str) -> Vec<u64> {
12    let mut packages: Vec<_> = input.iter_unsigned().collect();
13    packages.sort_unstable();
14    packages
15}
16
17pub fn part1(input: &[u64]) -> u64 {
18    let sum: u64 = input.iter().sum();
19    let target = sum / 3;
20    (1..input.len()).find_map(|size| combinations(input, target, size)).unwrap()
21}
22
23pub fn part2(input: &[u64]) -> u64 {
24    let sum: u64 = input.iter().sum();
25    let target = sum / 4;
26    (1..input.len()).find_map(|size| combinations(input, target, size)).unwrap()
27}
28
29/// Check all combinations of `size` items returning `None` if no valid solution is found.
30fn combinations(packages: &[u64], target: u64, size: usize) -> Option<u64> {
31    // Mantain `size` indices, initially set to 0, 1, 2...
32    let mut indices: Vec<_> = (0..size).collect();
33    // Initial weight for first `size` items.
34    let mut weight: u64 = packages.iter().take(size).sum();
35
36    loop {
37        // Check for success
38        if weight == target {
39            let product = indices.iter().map(|&i| packages[i]).product();
40            return Some(product);
41        }
42
43        // Try to advance the last index. If the last index is at the end, then try to advance
44        // the previous index until we reach the root.
45        let mut depth = size - 1;
46        while indices[depth] == packages.len() - size + depth {
47            if depth == 0 {
48                return None;
49            }
50            depth -= 1;
51        }
52
53        // Update the first index that is not at the end.
54        let from = indices[depth];
55        let to = indices[depth] + 1;
56        indices[depth] = to;
57        weight = weight - packages[from] + packages[to];
58        depth += 1;
59
60        // "Wrap" following indices to 1 more than the previous.
61        while depth < size {
62            let from = indices[depth];
63            let to = indices[depth - 1] + 1;
64            indices[depth] = to;
65            weight = weight - packages[from] + packages[to];
66            depth += 1;
67        }
68    }
69}
aoc/year2015/day24.rs

aoc/year2015/
day24.rs
