## DEV Community # Science for Hungry People

## Part 1

1. Continuing the combo
2. 101, 4 times?
3. Using `regex` to extract the amounts
4. Animating and writing a working algorithm

### Continuing the combo

This year has featured several combination-themed puzzles:

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)
``````
• `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)` 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
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

1. Bring on the calories!
2. 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
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 == 500) {
score = totals.slice(0,4).reduce(
(product, num) => product *= num < 0 ? 0 : num
, 1)
}
return Math.max(highest, score)
}, 0
)
``````

• Using a handful of `map()` and `reduce()` methods!