Advent of Code 2015 - Day 15 - Science for Hungry People

On the fifteen day of Advent of Code 2015 we are tasked with finding the right balance of ingredients to make the perfect milk-dunking cookie recipe.

Part 1

We are provided with a listing of the four available ingredients, along with five properties for each. These properties are capacity, durability, flavor, texture and calories. Our resultung recipe leaves room for exactly 100 teaspoons of ingredients.

For part one we are asked to find the ingredient mixture that has the highest total cookie score. The total score of a cookie can be found by adding up each of the properties (negative totals become 0) and then multiplying together everything except calories.

We start by parsing the ingredients into a form we can work with going forward.

type Property = number;
type Ingredient = Property[];

const parseIngredients = (input: string): Ingredient[] =>
  input.split('\n').map(line => line.match(/(-?\d+)/g).map(toInt));

For this exercise we are not too bothered with the names of the ingredients and properties, and as such we can simply store all the given properties values. From here, we are required to iterate over all the possible combinations of teaspoon quantities per ingredient that sum up to the 100 teaspoons available. Initially, I solved this with a hardcoded triple for-loop 😬, but upon reflection I have decided to generalise the solution to cater for any arity of ingredients.

type Quantity = number;
type Mixture = Quantity[];

function* mixtures(
  teaspoons: Quantity,
  ingredients: number
): Generator<Mixture> {
  if (ingredients < 2) {
    return yield [teaspoons];
  }

  for (let quantity = 0; quantity <= teaspoons; quantity++) {
    for (const mixture of mixtures(
      teaspoons - quantity,
      ingredients - 1
    )) {
      yield [quantity, ...mixture];
    }
  }
}

The above implementation harnesses a Generator to recursively combine all the quantities of each ingredient that could be possible. For comparison, I also decided to implement a solution which uses plain ol’ arrays like so.

const mixtures = (
  teaspoons: Quantity,
  ingredients: number
): Mixture[] => {
  if (ingredients < 2) return [[teaspoons]];

  return [...Array(teaspoons + 1).keys()].reduce(
    (mixes, quantity) =>
      mixes.concat(
        mixtures(
          teaspoons - quantity,
          ingredients - 1
        ).map(mixture => [quantity, ...mixture])
      ),
    []
  );
};

With the ability to now iterate over all the possible quantities of ingredients we can now codify how to calculate the score of a given cookie.

const calcCookieScore = (
  ingredients: Ingredient[],
  mixture: Mixture
): { score: number; calories: number } => {
  const properties = transpose(ingredients).map(property =>
    Math.max(
      zip(property, mixture).reduce((sum, [p, m]) => sum + p * m, 0),
      0
    )
  );
  const calories = properties.pop();

  return { score: properties.reduce(product), calories };
};

Providing the ingredients and desired mixture we first transpose the ingredients array (matrix) into rows of all the properties values. The function in question has been implemented like so.

const transpose = <T>(a: T[][]) =>
  a[0].map((_, c: number) => a.map((r: T[]) => r[c]));

We then zip these properties with the desired mixture and apply the formula for calculating the score. Finally, we pop the calories off the bottom and return the score (product of all the properties individual scores, excluding calories) and the calories themselves.

With these building blocks in-place we can then calculate all the possible scores and return the highest to answer part one 🌟.

const RECIPE_TEASPOONS = 100;

const part1 = (input: string): number => {
  const ingredients = parseIngredients(input);

  const scores = [
    ...mixtures(RECIPE_TEASPOONS, ingredients.length),
  ].map(mixture => calcCookieScore(ingredients, mixture).score);

  return max(scores);
};

Note: due to the size of the scores array that is produced we are again required to use the max function produced in a previous days solution over Math.max.

Part 2

For part two we are asked to determine what mixture produces the highest cookie score again, expect this time the mixtures calories should equal to 500. In a similar manor to part one we can calculate all the possible cookie scores, however, now we only return this score if the calories are equal to 500. We can then locate the highest scored cookie from this partial listing to answer part two 🌟.

const part2 = (input: string): number => {
  const ingredients = parseIngredients(input);

  const scores = [
    ...mixtures(RECIPE_TEASPOONS, ingredients.length),
  ].map(mixture => {
    const { score, calories } = calcCookieScore(ingredients, mixture);
    return calories === 500 ? score : 0;
  });

  return max(scores);
};