Solution to Advent of Code 2020 Day 21

AOC_2020-21.js

const { parseInputFile } = require('../utils/parser');

const INPUT_FILE = 'day21-input.txt';

/**
 * @typedef {object} Food
 * @property {string[]} ingredients
 * @property {string[]} allergens
 */

 /** @type {Food[]} */
const foods = parseInputFile(INPUT_FILE, /^([\w ]+) \(contains ([\w ,]+)\)$/gm)
    .map(([, ingredientList, allergenList]) => ({
        ingredients: ingredientList.split(' '),
        allergens: allergenList.split(', ')
    }));

/** @type {Map<string, Set<string>>} */
const possibleIngredientAllergens = new Map();
/** @type {Map<string, Set<string>>} */
const possibleAllergenIngredients = new Map();
/** @type {Map<string, Food[]} */
const allergenFoods = new Map();

for (const food of foods) {
    for (const ingredient of food.ingredients) {
        let ingredientAllergenSet = possibleIngredientAllergens.get(ingredient);
        if (!ingredientAllergenSet) {
            ingredientAllergenSet = new Set();
            possibleIngredientAllergens.set(ingredient, ingredientAllergenSet);
        }

        for (const allergen of food.allergens) {
            
            let allergenIngredientSet = possibleAllergenIngredients.get(allergen);
            if (!allergenIngredientSet) {
                allergenIngredientSet = new Set();
                possibleAllergenIngredients.set(allergen, allergenIngredientSet);
            }

            ingredientAllergenSet.add(allergen);
            allergenIngredientSet.add(ingredient);
            
        }
    }
    for (const allergen of food.allergens) {
        let allergenFoodList = allergenFoods.get(allergen);
        if (!allergenFoodList) {
            allergenFoodList = [];
            allergenFoods.set(allergen, allergenFoodList);
        } 
        
        allergenFoodList.push(food);
    }
}

// trim impossible allergen<->ingredient mappings
for (const [ ingred, possibleAllergens ] of possibleIngredientAllergens) {
    // test each ingred -> allergen map
    for (const allergen of possibleAllergens) {
        // check that this ingredient exists in all other foods with this allergen.
        if (!allergenFoods.get(allergen).every(food => food.ingredients.includes(ingred))) {
            // if not, then remove the mapping
            possibleAllergenIngredients.get(allergen).delete(ingred);
            possibleIngredientAllergens.get(ingred).delete(allergen);
        }
    }
}


// Part 1
const safeIngredients = Array.from(possibleIngredientAllergens.entries()).filter(([, allergens]) => allergens.size === 0).map(([ingredient]) => ingredient);
const part1SafeIngredCount = safeIngredients
    .map(safeIngred => foods.filter(f => f.ingredients.includes(safeIngred)).length)
    .reduce((sum, count) => sum + count, 0);
console.log(`Part 1: Safe ingredients are used ${ part1SafeIngredCount } times.`);

/** @type {Map<string, string>} */
const translatedAllergens = new Map();
const remainingAllergens = new Set(Array.from(possibleAllergenIngredients.keys()));

while (remainingAllergens.size > 0) {
    // test each allergent
    for (const allergen of remainingAllergens) {

        // get possible ingredients for this allergen
        const possibleIngredients = possibleAllergenIngredients.get(allergen);

        // try to solve
        if (possibleIngredients.size === 1) {
            const allergenIngredient = Array.from(possibleIngredients)[0];

            // save the translation
            translatedAllergens.set(allergen, allergenIngredient);

            // remove from remaining
            remainingAllergens.delete(allergen);

            // remove from other ingredient's pools
            for (const otherAllergenName of possibleIngredientAllergens.get(allergenIngredient)) {
                const otherAllergen = possibleAllergenIngredients.get(otherAllergenName);
                otherAllergen.delete(allergenIngredient);
            }

            // remove other allergens from this ingredient's pool
            possibleIngredientAllergens.set(allergenIngredient, new Set(allergen));
        }
    }
}

// Part 2
const dangerousIngredientList = Array.from(translatedAllergens)
    .sort((a1, a2) => a1[0].localeCompare(a2[0]))
    .map(a => a[1])
    .join(',');
console.log(`Part 2: The dangerous ingredient list is "${ dangerousIngredientList }".`);