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