Advent of Code 2015 Day 15
Part 1
 Continuing the combo
 101, 4 times?
 Using
regex
to extract the amounts  Animating and writing a working algorithm
Continuing the combo
This year has featured several combinationthemed 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 highestscoring 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, bruteforce 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 numbercoerced 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 headscratching troubleshooting, I finally figured it out.
And it generated the correct answer!
My algorithm in pseudocode:
For each 100teaspoon recipe as a combination of four numbers
Accumulate a number that represents the highest one among all those encountered, starting at 0
Create a 4element 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 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 100teaspoon recipe as a combination of four numbers
Accumulate a number that represents the highest one among all those encountered, starting at 0
Create a 5element 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 combinationgeneration and array manipulation.
Top comments (0)