Advent of Code 2015 - Day 17

Day 17: No Such Thing as Too Much

Useful Links

‹›

• 2015 Main Page
• My solution code

Concepts and Packages Demonstrated

List comprehensionCombinations

Page Navigation

• Problem Intro
• Part 1
• Part 2
• Results

Problem Intro

We have 150L of eggnog, and we need to distribute this eggnog over a bunch of containers. The volumes of the containers (in L) are our puzzle input. E.g.

20
15
10
5
5

Part 1

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

This is quite an easy problem. I used a fairly similar solution to Day 15.

First, we read in the numbers, and convert them to a single list of int values:

    with open(INPUT_FILE, mode="rt") as f:
        containers = [int(x) for x in f.read().splitlines()]

Then:

• Create a list to hold all the valid combinations of containers, i.e. any combination of containers that exactly holds our target volume.
• Then, iterate through the range of the number of containers we can use, and for each, determine how many combinations of containers there are, using that number of containers. E.g. using the example data above:
  • With only 1 container, we can select: 20, 15, 10, 5, 5
  • With 2 containers, we can select
    (20, 15), (20, 10), (20, 5), (20, 5), (15, 10), (15, 5)..., etc.
  • But return only those combinations that add up to the target volume.
  • Add those valid combinations to the overall list.

The code looks like this:

    all_valid_combos = []  # all the container combos that add up to TARGET
    
    # Try any single container, then any two containers, then any three, etc
    for num_containers in range(1, len(containers)+1):
        valid_combos = [combo for combo in list(combinations(containers, num_containers))
                              if sum(combo) == TARGET]
        all_valid_combos.extend(valid_combos)

    # part 1
    print(f"Part 1: Valid combos that contain {TARGET}L={len(all_valid_combos)}")

Easy!

Part 2

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?

Well, this is very easy! We just need to do exactly the same as Part 1, but stop once we’ve got our first valid combinations. Why? Because at that point, we’ve already got the combinations using hte fewest number of containers!

    # part 2
    all_valid_combos = []  # all the container combos that add up to TARGET
    for num_containers in range(1, len(containers)+1):
        valid_combos = [combo for combo in list(combinations(containers, num_containers))
                              if sum(combo) == TARGET]
        all_valid_combos.extend(valid_combos)
        if valid_combos:
            break
    
    print(f"Part 2: Combinations with minimum number of containers={len(all_valid_combos)}")

Results

Here’s the complete code:

from pathlib import Path
from itertools import combinations
import time

SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")

TARGET = 150

def main():
    with open(INPUT_FILE, mode="rt") as f:
        containers = [int(x) for x in f.read().splitlines()]

    all_valid_combos = []  # all the container combos that add up to TARGET
    
    # Try any single container, then any two containers, then any three, etc
    for num_containers in range(1, len(containers)+1):
        valid_combos = [combo for combo in list(combinations(containers, num_containers))
                              if sum(combo) == TARGET]
        all_valid_combos.extend(valid_combos)

    # part 1
    print(f"Part 1: Valid combos that contain {TARGET}L={len(all_valid_combos)}")

    # part 2
    all_valid_combos = []  # all the container combos that add up to TARGET
    for num_containers in range(1, len(containers)+1):
        valid_combos = [combo for combo in list(combinations(containers, num_containers))
                              if sum(combo) == TARGET]
        all_valid_combos.extend(valid_combos)
        if valid_combos:
            break
    
    print(f"Part 2: Combinations with minimum number of containers={len(all_valid_combos)}")

if __name__ == "__main__":
    t1 = time.perf_counter()
    main()
    t2 = time.perf_counter()
    print(f"Execution time: {t2 - t1:0.4f} seconds")

And here’s the output:

Part 1: Valid combos that contain 150L=4372
Part 2: Combinations with minimum number of containers=4
Execution time: 0.1281 seconds

‹›