Module aoc::year2015::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.