Module day17

No Such Thing as Too Much

Given n items the number of possible subsets is 2ⁿ. We could brute force through each subset by iterating from 0 to 2ⁿ using the binary bits to indicate if a container is present. This will work but is a little slow as there are 20 containers, giving 2²⁰ = 1048576 combinations to check.

We speed things up by noticing that some containers are the same size, so the total number of combinations is fewer. For example if there are 3 containers of size x that is only 4 possibilities rather than 8.

We have to multiply the result by nCr or the number of ways of choosing r items from n. For example if 2 containers out of 3 are used in a solution then there are 3 ways of selecting the 2 containers. This solution hardcodes nCr tables for n up to 4.

As an optimization containers are ordered from largest to smallest so that the recursive checking can exit as early as possible if we exceed 150 litres.

Structs

State 🔒

Constants

NCR 🔒

nCr for n from 0 to 4 inclusive.

Functions

combinations 🔒

Recursively try every possible combination, returning early if the size exceeds 150 litres.

parse

part1

We only care about the total combinations, so sum the entire vec.

part2

We want the number of combination with the fewest containers, so find first non-zero value.