AoC 2015 Puzzle 17

Info

I solved this puzzle. You can find the code here, but I have yet to write a good explanation of the solution here. I will do this shortly, thank you for your patience.

Day 17: No Such Thing as Too Much

The elves bought too much eggnog again - 150 liters this time. To fit it all into your refrigerator, you'll need to move it into smaller containers. You take an inventory of the capacities of the available containers.

For example, suppose you have containers of size 20, 15, 10, 5, and 5 liters. If you need to store 25 liters, there are four ways to do it:

  • 15 and 10
  • 20 and 5 (the first 5)
  • 20 and 5 (the second 5)
  • 15, 5, and 5

Filling all containers entirely, how many different combinations of containers can exactly fit all 150 liters of eggnog?

Part 2

While playing with all the containers in the kitchen, another load of eggnog arrives! The shipping and receiving department is requesting as many containers as you can spare.

Find the minimum number of containers that can exactly fit all 150 liters of eggnog. How many different ways can you fill that number of containers and still hold exactly 150 litres?

In the example above, the minimum number of containers was two. There were three ways to use that many containers, and so the answer there would be 3.

Complete Solution

int[][] combinations(int[] input) {
    int len = input.length;

    // As we use a 32 value to store, can not be longer
    // then 31
    if (len > 31)
        throw new IllegalArgumentException();

    int numCombos = (1 << len) - 1;
    int[][] combos = new int[numCombos][];

    // i will hold the number of combinations
    // starting at 0 would include an empty set
    for (int i = 1; i <= numCombos; i++) {
        // Count the number of bits in i that are set
        int[] combo = new int[Integer.bitCount(i)];

        // loop over the input array to create combos
        for (int j = 0, x = 0; j < len; j++) {
            // if the bit is set, add the input value to
            // the combination
            if ((i & (1 << j)) > 0)
                combo[x++] = input[j];
        }

        // Add the combination to the output array
        // Remember we started at 1, so subtract it
        combos[i - 1] = combo;
    }

    return combos;
}

long countOfCombinedValue(int[][] combos, int targetValue) {
    return Arrays.stream(combos).mapToInt(a -> Arrays.stream(a).sum()).filter(s -> s == targetValue).count();
}

long countOfContainersToSpare(int[][] combos, int targetValue) {
    // Grab the combinations that add up to a value
    Object[] intsOfValue =  Arrays.stream(combos).filter(a -> Arrays.stream(a).sum() == targetValue).toArray();
    // Get the minimum length of the arrays
    int minSize = Arrays.stream(intsOfValue).mapToInt(a -> ((int[]) a).length).min().getAsInt();
    // count the number of combinations of that size
    return Arrays.stream(intsOfValue).filter(a -> ((int[]) a).length == minSize).count();

}

@Override
public String part1(List<String> input) {
    int[] in = input.stream().mapToInt(s -> Integer.parseInt(s)).toArray();
    int[][] combos = combinations(in);

    return String.valueOf(countOfCombinedValue(combos, 150));
}

@Override
public String part2(List<String> input) {
    int[] in = input.stream().mapToInt(s -> Integer.parseInt(s)).toArray();
    int[][] combos = combinations(in);

    return String.valueOf(countOfContainersToSpare(combos, 150));
}