Science for Hungry People

Advent of Code 2015 Day 15

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:

• 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

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
      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() and reduce() methods!

This puzzle offered some more great practice in combination-generation and array manipulation.