Advent of Code 2015 Day 15
Part 1
- Continuing the combo
- 101, 4 times?
- Using
regexto extract the amounts - Animating and writing a working algorithm
Continuing the combo
This year has featured several combination-themed puzzles:
- Day 24: It Hangs in the Balance
- Day 22: Wizard Simulator 20XX
- Day 21: RPG Simulator 20XX
- Day 17: No Such Thing as Too Much
I sense today's isn't the last one I will encounter, either.
101, 4 times?
- To find the highest-scoring cookie, I probably need to find the scores of all possible cookies, then determine the highest score.
- My input features four ingredients
- The recipe must have 100 teaspoons of any combination of ingredients
Possible combinations include:
Ingr. 1 2 3 4
100 0 0 0
0 25 26 49
1 1 1 97
5 95 2 3
My naive, brute-force approach is to use four nested loops to build up a list of arrays containing four numbers that sum to 100:
Set combos to an empty list
For a from 0 up to and including 100
For b from 0 up to and including 100
For c from 0 up to and including 100
For d from 0 up to and including 100
If a + b + c + d equals 100
Add [a, b, c, d] to combos
- That loop will run 101 * 101 * 101 * 101 times
- That's over 10M times
- But computers are fast
- So it only takes a second
- And generates a list of about 175K combinations
Using regex to extract the amounts
From this input:
Butterscotch: capacity -1, durability -2, flavor 6, texture 3, calories 8
Cinnamon: capacity 2, durability 3, flavor -2, texture -1, calories 3
I need these lists:
[-1, -2, 6, 3]
[ 2, 3, -2, -1]
That requires a simple regular expression:
/-*\d+/g
-
-*matches 0 or more dashes -
\d+matches 1 or more digits
In JavaScript, going from string to list of numbers looks like this:
[...ingredient.matchAll(/-*\d+/g)].map(i => +i[0])
-
ingredient.matchAll(/-*\d+/g)creates an iterable list filled with each match's details -
[...]spreads each list item into an array or arrays -
.map(i => +i[0])changes each list item array into the number-coerced value of it's first item - the matching substring
Animating and writing a working algorithm
- This temporarily 'broke my brain' for some reason
- I struggled to reason about whether to start from the combination array or the ingredient list
- And when to account for negative values
After some head-scratching troubleshooting, I finally figured it out.
And it generated the correct answer!
My algorithm in pseudocode:
For each 100-teaspoon recipe as a combination of four numbers
Accumulate a number that represents the highest one among all those encountered, starting at 0
Create a 4-element array
For each item in that array
Start with a copy of the amounts of each ingredient
Keep only the amount from each ingredient in the same position as the current iteration of this loop
Multiply the amount by the number of teaspoons in the same position
Add each item together to get a sum
Multiply each amount together, replacing any negative amounts with 0
Compare the resulting product with the current highest number
Return the highest number
My algorithm, animated:
My algorithm in JavaScript:
100_Teaspoon_Recipes.reduce(
(highest, recipe) => Math.max(
highest,
new Array(4)
.fill(null)
.map(
(_, index) =>
ingredients
.map(el => el[index])
.map((el, index) => el * recipe[index])
.reduce((sum, num) => sum + num)
)
.reduce(
(product, num) => product *= num < 0 ? 0 : num
, 1)
), 0)
- 3
map()s - 3
reduce()ers - Wow!
I'm excited to see whether - and how - Part 2 leverages the negative amounts and the calories!
Part 2
- Bring on the calories!
- Updating my algorithm
Bring on the calories!
- Same task, but only considering a subset of the recipes from before: the ones that have 500 calories
- This should only require a few small adjustments to my algorithm
Updating my algorithm
- I need to include the calories in my equations, so the array needs to have 5 slots instead of 4
- Before comparing the highest score with the current score, I need to check if the number in the last slot after all the calculations is 500
- If it is, then I can proceed with the multiplication step
- If not, then I should consider the score 0 to ensure no risk of updating the highest score
My algorithm in pseudocode:
For each 100-teaspoon recipe as a combination of four numbers
Accumulate a number that represents the highest one among all those encountered, starting at 0
Create a 5-element array
For each item in that array
Start with a copy of the amounts of each ingredient
Keep only the amount from each ingredient in the same position as the current iteration of this loop
Multiply the amount by the number of teaspoons in the same position
Add each item together to get a sum
If the last item in the array equals 500
Remove the last item, as it's not needed to calculate the score
Multiply each amount together, replacing any negative amounts with 0
Compare the resulting product - or 0, if there were not 500 calories - with the current highest number
Return the highest number
My algorithm in JavaScript:
combos.reduce(
(highest, recipe) => {
let totals = new Array(5)
.fill(null)
.map(
(_, index) =>
ingredients
.map(el => el[index])
.map((el, index) => el * recipe[index])
.reduce((sum, num) => sum + num)
)
let score = 0
if (totals[4] == 500) {
score = totals.slice(0,4).reduce(
(product, num) => product *= num < 0 ? 0 : num
, 1)
}
return Math.max(highest, score)
}, 0
)
It generated the correct answer!
I did it!!
- I solved both parts!
- After getting stumped about my planned approach!
- Using a handful of
map()andreduce()methods!
This puzzle offered some more great practice in combination-generation and array manipulation.
Top comments (0)