Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Advent of Code 2015 - Day 15

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:

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):

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):
``````

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)
""" 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()))

# Part 1
``````

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))
``````

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)
""" 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:

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

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()))

# Part 1

# Part 2

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):

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
``````