Advent of Code: Day 15

Source

Part 1: Input is a list of ingredients of the form:

Frosting: capacity 4, durability -2, flavor 0, texture 0, calories 5
Candy: capacity 0, durability 5, flavor -1, texture 0, calories 8

A recipe score is a product of the positive quantity scores (ignoring calories), where each quantity score is the product of the quantity and that product for each product.

For example, 4 Frosting and 2 Candy above, would have a score of of -2 * 4 + 5 * 2 = 2 for durability and 0 * 4 + -1 * 2 = -2 (and thus ignored as we only accept positive scores) for a total thus far of 2.

The code is getting a bit longer, but a brute force solution still works great:

try:
    TOTAL_QUANTITY = int(sys.argv[1])
except:
    print('Usage: cat input.txt | ./part-1.py [TOTAL_QUANTITY]')
    sys.exit(0)

ingredients = collections.defaultdict(lambda : collections.defaultdict(lambda : 0))
properties = set()

for line in sys.stdin:
    item, pairs = line.split(':')
    for pair in pairs.split(','):
        property, amount = pair.strip().split(' ')
        ingredients[item.lower()][property] = int(amount)
        properties.add(property)

items = list(sorted(ingredients.keys()))
properties.remove('calories')

def calculate_score(quantities):
    score = 1

    for property in properties:
        property_score = sum(
            quantities[item] * ingredients[item][property]
            for item in quantities
        )

        if property_score > 0:
            score *= property_score

    return score

def splits(amount, count):
    if count <= 1:
        yield [amount]
    else:
        for i in range(amount + 1):
            for subsplit in splits(amount - i, count - 1):
                yield [i] + subsplit

best_score = 0
best_quantities = None

for split in splits(TOTAL_QUANTITY, len(items)):
    quantities = dict(zip(items, split))
    score = calculate_score(quantities)

    if score > best_score:
        best_score = score
        best_quantities = quantities

print(best_score)
print(best_quantities)]

Essentially, there are four parts. First, we load all of the ingredients and their scores into memory. Then, calculate_score will take the logic described in the problem and return a score for any given quantities. Third, splits is a generator that will return all possible ways to divide amount items into count buckets:

print(list(splits(5, 3)))
[[0, 0, 5],
 [0, 1, 4],
 [0, 2, 3],
 [0, 3, 2],
 [0, 4, 1],
 [0, 5, 0],
 [1, 0, 4],
 [1, 1, 3],
 [1, 2, 2],
 [1, 3, 1],
 [1, 4, 0],
 [2, 0, 3],
 [2, 1, 2],
 [2, 2, 1],
 [2, 3, 0],
 [3, 0, 2],
 [3, 1, 1],
 [3, 2, 0],
 [4, 0, 1],
 [4, 1, 0],
 [5, 0, 0]]

Finally, we use all of those pieces to iterate over all of the possible scores. dict(zip(items, split)) is a quick way to take two lists (of keys and values) and combine them into a dictionary.

I also tried to work out a solution using a genetic algorithm: part-1-genetic.py. It does work (in that it finds a pretty good solution), but the solution isn’t optimal and it takes just as long as just brute forcing the problem. It’s interesting though.

Part 2: Do the same thing, only throw out any solutions that do not have a sum calorie count of exactly 500.

The tweak for this part is actually fairly elegant:

def calculate_score(quantities):
    ...

    calorie_count = sum(
        quantities[item] * ingredients[item]['calories']
        for item in quantities
    )
    if calorie_count != TOTAL_CALORIES:
        return float("-inf")

    ...

Since we’re looking for the largest score, returning a score that is infinitely low will skip over any invalid solutions. Other than that (and a new try block at the top), everything remains the same.

This was an interesting problem. Not quite as elegant a solution as I’d like, but it’s still well within my self imposed (originally from Project Euler) 1 minute limit.

comments powered by Disqus