Advent of Code 2015 - Day 15

Useful Links

Concepts and Packages Demonstrated

dataclass comprehension dictionary comprehension permutations combinations defaultdict zip Lambda function filter

Problem Intro
Part 1
Part 2
Results

Problem Intro

We need to perfect the milk-dunking cookie recipe by finding the right balance of ingredients. We must combine ingredients such that we use exactly 100 teaspoons of ingredients.

Our puzzle input is the list of ingredients. It looks something like this:

Butterscotch: capacity -1, durability -2, flavor 6, texture 3, calories 8
Cinnamon: capacity 2, durability 3, flavor -2, texture -1, calories 3

Each ingredient is made up of five properties and their associated property scores. There are five properties, and these are: capacity, durability, flavor, texture, and calories. The total score for a given cookie recipe depends on the quantities of each ingredient in the recipe.

To determine the score of a cookie recipe, we first need to calculate the total score of each of the properties:

Score of each property = qty_ingr1 * ingr1_property_score
                         + qty_ingr2 * ingr2_property_score
                         + qty_ingr3 * ingr3_property_score ... 

(Or 0 if property score is -ve.)

Then, the overall cookie score is given by the product of the scores of each of the properties. I.e.

Cookie recipe score = property_1_score * property_2_score * property_3_score * property_4_score

Part 1

Ignoring the calorie property, what is the total score of the highest-scoring cookie you can make?

I found this one quite difficult! I solved it quite a few ways. What I document here is not quite the fastest solution, but it is possibly the easiest to understand. It also demonstrates a LOT of Python functionality.

First, I define a class that represents any given ingredient:

@dataclass
class Ingredient:
    """ Every ingredient has a name, and a set of five properties:
        capacity, durability, flavour, texture, calories. """
    CALORIES = "calories"
    
    name: str
    properties: dict

    def __post_init__(self) -> None:
        """ We pop 'calories' and store as a separate property.
        Note that the dataclass automatically calls __post_init__() after __init__(), 
        if the method is defined. """
        self.calories = self.properties.pop(Ingredient.CALORIES)

Here I’ve defined the class as a dataclass. This way, we save ourselves from having to write a bunch of boilerplate code. One interesting thing to say about this particular class:

When we create an instance of this class, we pass in the five property values that make up this ingredient.
But since we will need to treat the calories property slightly differently from the other properties, I’ve stored calories as a separate property in this class.
I’ve done this by initialising the self.calories value in a __post_init__() method. The only thing you need to know is that if you create a dataclass that contains a __post_init__() method, then this method is automatically executed immediately after executing the __init__() method. Thus, this is a good way of setting additional properties after initialisation.

Now I’ll create a function to read in the ingredients:

def process_ingredients(data: list) -> list[Ingredient]:
    ingr_list = []
    for line in data:
        name, properties = line.split(":")
        properties = [x.strip().split(" ") for x in properties.split(",")]
        props_dict = {prop[0]:int(prop[1]) for prop in properties}
        ingr_list.append(Ingredient(name, props_dict))

    return ingr_list

How this works:

The list of ingredients is passed to our function as a list of str elements.
A typical line might look like this:
Butterscotch: capacity -1, durability -2, flavor 6, texture 3, calories 8
For each line, we first split at the :, giving us the name as one value, and all the properties as the second value.
The, for each property, we use list comprehension to split() at the ,, then further split() at the space between each property and its value. The result is a list made up of pairs of items, where each pair is the property and its value. I.e.
[['capacity', '-1'], ['durability', '-2'], ['flavor', '6'], ['texture', '3'], ['calories', '8']]
Then I use dictionary comprehension to turn each pair (as a list) into the key:value of a dictionary. I.e.
{'capacity': -1, 'durability': -2, 'flavor': 6, 'texture': 3, 'calories': 8}

We then create an Ingredient object from the name and props_dict.

The code to read in our data and convert to ingredients therefore looks like this:

    with open(INPUT_FILE, mode="rt") as f:
        data = f.read().splitlines()

    ingr_list = process_ingredients(data)

If we print out the ingredients at this point, it looks something like this:

Ingredient(name='Sprinkles', properties={'capacity': 5, 'durability': -1, 'flavor': 0, 'texture': 0})
Ingredient(name='PeanutButter', properties={'capacity': -1, 'durability': 3, 'flavor': 0, 'texture': 0})  
Ingredient(name='Frosting', properties={'capacity': 0, 'durability': -1, 'flavor': 4, 'texture': 0})      
Ingredient(name='Sugar', properties={'capacity': -1, 'durability': 0, 'flavor': 0, 'texture': 2})

Okay, good. There’s only four different ingredients.

So, the hard part… We need to come up with every permutation of mixing these ingredients, that add up to 100 spoonfuls of the ingredients. I.e. permutations that look something like this…

Permutation	Sprinkles	Peanut Butter	Frosting	Sugar
1	100	0	0	0
2	99	0	0	1
3	99	0	1	0
4	99	1	0	0
5	98	0	1	1
6	98	1	0	1
7	98	1	1	0
8	98	0	0	2
9	98	0	2	0
10	98	2	0	0

You can see how this is going to get very large!

How do we get all the possible permutations? This is how I’ve done it…

def find_permutations(target: int, terms: int) -> set[tuple]: 
    """ Return all permutations of terms that sum to the target number.
    We need to include repeats. E.g. (10, 10, 40, 40) would be valid.
    Use combinations_with_replacement. E.g. if target = 6 and terms = 2, the results would be:
    (0, 6), (1, 5), (2, 4), (3, 3).
    However, order is important since (0, 6) is different properties to (6, 0).
    So we need to determine the permutations for each combo.

    Returns: Set containing tuples of valid term permutations """
    
    combos = [combo for combo in combinations_with_replacement(range(target), terms) if sum(combo) == target]
    perms_of_combos = set() # use a set to filter out duplicates
    for combo in combos:
        for perm in permutations(combo):
            perms_of_combos.add(perm) 
    
    return perms_of_combos

In the actual solution, our target is 100, and we have 4 different terms, i.e. four different ingredients to mix. But to explain the code above, let’s imagine that we have a target of 6 spoonfuls, and only 3 ingredients.

So I start by getting all the combinations of ingredients that add up to target amount.

What if we did this?

combos = [combo for combo in combinations(range(target), terms) if sum(combo) == target]

With target == 6 and terms == 3, this would create a combos list that looks like this:

[(0, 1, 5), (0, 2, 4), (1, 2, 3)]

You can see that each tuple adds up to 6. But we’re missing a load! What happened to the tuples below, for example?

(4, 1, 1)
(3, 3, 0)
(2, 2, 2)

The reason is that the itertools.combinations() method excludes repeating numbers. But in our solution, it is valid to repeat the numbers in our tuples. Why? Because it’s perfectly valid to have the same amount of more than one ingredient in our recipe.

So, instead of using combinations(), we need to use combinations_with_replacement(). I.e.

combos = [combo for combo in combinations_with_replacement(range(target), terms) if sum(combo) == target]

With target == 6 and terms == 3, our new combos list looks like this:

[(0, 1, 5), (0, 2, 4), (0, 3, 3), (1, 1, 4), (1, 2, 3), (2, 2, 2)]

That’s better! However, recall that combinations ignore order. These are considered to be the same:

(0, 1, 5)
(0, 5, 1)
(1, 0, 5)
(1, 5, 0)
(5, 1, 0)
(5, 0, 1)

But in our recipes, the order is important. So, we need to convert our combinations to permutations. I do this by determining all the permutations for each combination.

perms_of_combos = set() # use a set to filter out duplicates
for combo in combos:
    for perm in permutations(combo):
        perms_of_combos.add(perm) 

Note that we store all these permutations in a set. This is so that we avoid duplicates like…

(2, 2, 2), (2, 2, 2), (2, 2, 2), (2, 2, 2), (2, 2, 2), (2, 2, 2)

I.e. there are six different ways we could arrange (2, 2, 2), if we treated each 2 as a unique thing.

So, after filtering our the duplicates, our simpified example ends up with a set of permutations that looks like this:

{(2, 3, 1), (2, 2, 2), (2, 1, 3), (5, 0, 1), (0, 3, 3), 
 (3, 2, 1), (3, 1, 2), (0, 2, 4), (3, 0, 3), (1, 5, 0), 
 (2, 0, 4), (0, 1, 5), (4, 2, 0), (1, 4, 1), (1, 3, 2), 
 (4, 1, 1), (4, 0, 2), (1, 2, 3), (3, 3, 0), (2, 4, 0), 
 (5, 1, 0), (0, 4, 2), (1, 1, 4), (0, 5, 1), (1, 0, 5)}

With a target of 6 spoonfuls, and 3 different ingredients, we can see that we have 25 different ways of arranging the ingredients. When we do the same with 100 spoonfuls and 4 different ingredients - as required by our problem - we end up with 176847 different permutations!!

Great, so now we’ve got 176847 different cookie recipes. Next, I define a Cookie class to store each of these ingredient permutations, the score of the cookie, and the total calories of the cookie. Once again, I’m using a dataclass:

@dataclass(frozen=True)
class Cookie:
    """ A cookie is made up of 4 ingredients with quantities (a, b, c, d)
    and it has a score and calorie value """
    ingredients: tuple  # Ingredient amounts, e.g. (28, 35, 18, 19)
    score: int   
    calories: int

    def __str__(self) -> str:
        return f"{str(self.ingredients)}, cals={self.calories}, score={self.score}"

At this point, we’ve done most of the hard work!

Now we just need to calculate the score for each recipe:

    for perm in perms:   # e.g. with 2 ingredients, a perm might be (44, 56)
        prop_scores = defaultdict(int)
        calories = 0
        for qty, ingr in zip(perm, ingr_list):
            for prop, value in ingr.properties.items():
                prop_scores[prop] += qty * value

            calories += qty * ingr.calories

        # If any properties have negative value, set it to 0.
        for prop, value in prop_scores.items():
            if value < 0:
                prop_scores[prop] = 0
    
        total_score = prod(list(prop_scores.values()))
        cookies.append(Cookie(perm, total_score, calories))

    # Part 1
    best_cookie = max(cookies, key=lambda x: x.score)
    print(f"Best cookie: {best_cookie}")

What’s going on here?

We iterate over each reciple permutation. In each case, the permutation will be a tuple of the four ingredient amounts.
For each permutation:
- We start with a defaultdict, so that we can keep adding property scores, but without having to initialise the first time we come across a property.
- We zip together the four quantities with the four ingredients.
- Then, for each property that makes up these ingredients, we can calculate the property score, given the amount of each ingredient.
- Once I have all the property scores, I use the very convenient math.prod() function to find the product of an arbitrary number of values. (Another way to do this would be to use reduce().)
- While we’re here, we calculate the calories for the recipe.
- We now have everything we need to create a Cookie object: the four ingredient amounts, the ‘score’, and the ‘calorie’ count.

Finally, we calculate the best cookie by determining which cookie has the highest score. I do this by using a lambda which retrieves the score property of the cookie, and uses this as the attribute that the max() function uses.

DONE!

Part 2

What is the total score of the highest-scoring cookie you can make with a calorie total of 500?

Fortunately, we’ve already done all the hard work to solve this part. We only need to add this code:

    fixed_cal_cookies = list(filter(lambda x: x.calories == CAL_TARGET, cookies))
    best_fixed_cal_cookie = max(fixed_cal_cookies, key=lambda x: x.score)
    print(f"Best {CAL_TARGET} calorie cookie: {best_fixed_cal_cookie}")

Here I’m using filter to reduce our original list of cookies to only those cookies that match a condition specified by a lambda: i.e. cookies with 500 calories. Once we’ve filtered the cookies, we just run the same max() that we did before.

EASY!

Results

The final code looks like this:

from dataclasses import dataclass
from pathlib import Path
import time
from itertools import permutations, combinations_with_replacement
from math import prod
from collections import defaultdict

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

CAL_TARGET = 500
INGREDIENT_QTY = 100

@dataclass
class Ingredient:
    """ Every ingredient has a name, and a set of five properties:
        capacity, durability, flavour, texture, calories. """
    CALORIES = "calories"
    
    name: str
    properties: dict

    def __post_init__(self) -> None:
        """ We pop 'calories' and store as a separate property.
        Note that the dataclass automatically calls __post_init__() after __init__(), 
        if the method is defined. """
        self.calories = self.properties.pop(Ingredient.CALORIES)
        
@dataclass(frozen=True)
class Cookie:
    """ A cookie is made up of 4 ingredients with quantities (a, b, c, d)
    and it has a score and calorie value """
    ingredients: tuple  # Ingredient amounts, e.g. (28, 35, 18, 19)
    score: int   
    calories: int

    def __str__(self) -> str:
        return f"{str(self.ingredients)}, cals={self.calories}, score={self.score}"

def main():
    with open(INPUT_FILE, mode="rt") as f:
        data = f.read().splitlines()

    ingr_list = process_ingredients(data)
    for ingr in ingr_list:
        print(ingr)

    cookies: list[Cookie] = []
    perms = find_permutations(INGREDIENT_QTY, len(ingr_list))

    print(f"A total of {len(perms)} cookie recipes to process...")
    for perm in perms:   # e.g. with 2 ingredients, a perm might be (44, 56)
        prop_scores = defaultdict(int)
        calories = 0
        for qty, ingr in zip(perm, ingr_list):
            for prop, value in ingr.properties.items():
                prop_scores[prop] += qty * value

            calories += qty * ingr.calories

        # If any properties have negative value, set it to 0.
        for prop, value in prop_scores.items():
            if value < 0:
                prop_scores[prop] = 0
    
        total_score = prod(list(prop_scores.values()))
        cookies.append(Cookie(perm, total_score, calories))

    # Part 1
    best_cookie = max(cookies, key=lambda x: x.score)
    print(f"Best cookie: {best_cookie}")

    # Part 2
    fixed_cal_cookies = list(filter(lambda x: x.calories == CAL_TARGET, cookies))
    best_fixed_cal_cookie = max(fixed_cal_cookies, key=lambda x: x.score)
    print(f"Best {CAL_TARGET} calorie cookie: {best_fixed_cal_cookie}")

def find_permutations(target: int, terms: int) -> set[tuple]: 
    """ Return all permutations of terms that sum to the target number.
    We need to include repeats. E.g. (10, 10, 40, 40) would be valid.
    Use combinations_with_replacement. E.g. if target = 6 and terms = 2, the results would be:
    (0, 6), (1, 5), (2, 4), (3, 3).
    However, order is important since (0, 6) is different properties to (6, 0).
    So we need to determine the permutations for each combo.

    Returns: Set containing tuples of valid term permutations """
    
    combos = [combo for combo in combinations_with_replacement(range(target), terms) if sum(combo) == target]
    perms_of_combos = set() # use a set to filter out duplicates
    for combo in combos:
        for perm in permutations(combo):
            perms_of_combos.add(perm) 
    
    return perms_of_combos

def process_ingredients(data: list) -> list[Ingredient]:
    ingr_list = []
    for line in data:
        name, properties = line.split(":")
        properties = [x.strip().split(" ") for x in properties.split(",")]
        props_dict = {prop[0]:int(prop[1]) for prop in properties}
        ingr_list.append(Ingredient(name, props_dict))

    return ingr_list

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

Output:

Ingredient(name='Sprinkles', properties={'capacity': 5, 'durability': -1, 'flavor': 0, 'texture': 0})
Ingredient(name='PeanutButter', properties={'capacity': -1, 'durability': 3, 'flavor': 0, 'texture': 0})  
Ingredient(name='Frosting', properties={'capacity': 0, 'durability': -1, 'flavor': 4, 'texture': 0})      
Ingredient(name='Sugar', properties={'capacity': -1, 'durability': 0, 'flavor': 0, 'texture': 2})
A total of 176847 cookie recipes to process...
Best cookie: (28, 35, 18, 19), cals=435, score=13882464
Best 500 calorie cookie: (27, 27, 15, 31), cals=500, score=11171160
Execution time: 1.1639 seconds

‹›

Learning Python with Advent of Code Walkthroughs