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.