advent_of_code/year2015/
day24.rs

1use crate::common::parser::parse_lines;
2use crate::input::Input;
3
4// arr[]  ---> Input Array
5// data[] ---> Temporary array to store current combination
6// start & end ---> Staring and Ending indexes in arr[]
7// index  ---> Current index in data[]
8// r ---> Size of a combination to be printed */
9fn visit_subset_internal<F>(
10    input: &[u8],
11    output: &mut [u8],
12    input_idx: usize,
13    output_idx: usize,
14    on_subset: &mut F,
15) where
16    F: FnMut(&[u8]),
17{
18    if output_idx == output.len() {
19        on_subset(output);
20        return;
21    } else if input_idx >= input.len() {
22        return;
23    }
24
25    // Include input[input_idx]:
26    output[output_idx] = input[input_idx];
27    visit_subset_internal(input, output, input_idx + 1, output_idx + 1, on_subset);
28    // Skip input[input_idx]:
29    visit_subset_internal(input, output, input_idx + 1, output_idx, on_subset);
30}
31
32fn visit_subsets<F>(input: &[u8], subset_size: usize, on_subsete: &mut F)
33where
34    F: FnMut(&[u8]),
35{
36    let mut output = vec![0; subset_size];
37    visit_subset_internal(input, &mut output, 0, 0, on_subsete);
38}
39
40pub fn solve(input: &Input) -> Result<u128, String> {
41    let weights = parse_lines::<u8>(input.text)?;
42
43    let sum: u32 = weights.iter().map(|&w| u32::from(w)).sum();
44    let group_weight = sum / input.part_values(3, 4);
45
46    for subset_size in 1..weights.len() {
47        let mut result = None;
48        visit_subsets(&weights, subset_size, &mut |subset: &[u8]| {
49            if subset.iter().map(|&w| u32::from(w)).sum::<u32>() == group_weight {
50                let product = subset.iter().map(|&w| u128::from(w)).product();
51                if product < result.unwrap_or(u128::MAX) {
52                    result = Some(product);
53                }
54            }
55        });
56        if let Some(product) = result {
57            return Ok(product);
58        }
59    }
60
61    Err("No solution found".to_string())
62}
63
64#[test]
65pub fn tests() {
66    let real_input = include_str!("day24_input.txt");
67    test_part_one!(real_input => 10_723_906_903);
68    test_part_two!(real_input => 74_850_409);
69}
advent_of_code/year2015/day24.rs

advent_of_code/year2015/
day24.rs
