Advent of Code 2020 - Day 21, in Kotlin - Allergen Assessment • Todd Ginsberg

Today’s puzzle is a nice showcase for Kotlin’s set operations. Operations such as subtract (remove one set from another), intersect (keep only those elements in common), or union (make a new set containing both sets), are good things to know. Set theory is everywhere in computer programming, and it is helpful to know the basics.

If you’d rather just view code, the GitHub Repository is here .

Problem Input

Like most days, we will read our input in as a List<String> and parse it before moving on to Part 1.

When we parse our data we are going to eventually end up with a Map<Set<String>, Set<String>>, where the key is a set of ingredients and the value is a set of allergies. I’m not super fond of making a Set<String> a key into a map, but it works fine. This would not work if two recipes had the same ingredient lists, however.

private fun parseInput(input: List<String>): Map<Set<String>, Set<String>> =
    input.map { line ->
        val ingredients = line.substringBefore(" (").split(" ").toSet()
        val allergies = line.substringAfter("(contains ").substringBefore(")").split(", ").toSet()
        ingredients to allergies
    }.toMap()

For every row in our input, we pick apart the line and break out our ingredients and allergies. We use a combination of stringBefore, stringAfter, and split to make this happen.

We can define a food map to store this in our Day21 class.

class Day21(input: List<String>) {

    private val food: Map<Set<String>, Set<String>> = parseInput(input)
    private val allIngredients: Set<String> = food.keys.flatten().toSet()
    private val allAllergies: Set<String> = food.values.flatten().toSet()

}

Since it is handy, we will also define an allIngredients set, and an allAllergies set by flattening all of the sets of keys and values in our food map.

⭐ Day 21, Part 1

The puzzle text can be found here.

Before we start writing code, let’s talk about our strategy. A “safe ingredient” is one that we know does not cause any allergic reactions. How do we get to that point? For every allergy, we look through our foods mapping, looking for any mapping that contains that allergy. If we found one, we take the ingredients mentioned in that recipe. Because we’ll probably have a few sets of ingredients, we only want the ingredients that are common to all recipes we find. To do this, we reduce our findings by successively calling intersect between the set of ingredients we’ve already found and each new finding. Eventually, this will whittle down a lot of ingredients to just a few. This is the set of problematic ingredients. To get the fully safe set of ingredients, we subtract the problematic ingredients from the full set of allIngredients.

private fun safeIngredients(): Set<String> =
    allIngredients subtract allAllergies.flatMap { allergy ->
        food
            .filter { allergy in it.value }
            .map { it.key }
            .reduce { carry, ingredients -> ingredients intersect carry }
    }.toSet()

And now that we know what the safe ingredients are, we can use that to solve Part 1.

fun solvePart1(): Int {
    val safeIngredients = safeIngredients()
    return food.keys.sumOf { recipe ->
        recipe.count { it in safeIngredients }
    }
}

For every set of ingredients in our food map (the keys), we count up how many of those ingredients are safe. Add all of those numbers together, and that’s our answer to part 1!

Star earned! Onward!

⭐ Day 21, Part 2

The puzzle text can be found here.

In order to answer part 2, we will need to create a map whose key is an allergy, and whose value is the set of all ingredients from all recipes that mention that allergy, minus any safe ingredients we’ve already discovered in part 1.

private fun ingredientsByAllergy(): MutableMap<String, MutableSet<String>> {
    val safeIngredients = safeIngredients()

    return allAllergies.map { allergy ->
        allergy to food.entries
            .filter { allergy in it.value }
            .map { it.key - safeIngredients }
            .reduce { a, b -> a intersect b }
            .toMutableSet()
    }.toMap().toMutableMap()
}

The trick with making the value (the set of ingredients) is that we want only the ingredients that are common to all recipes mentioning that allergy. This is why we do a reduce here. This should give us the fewest ingredients to search through for any given allergy.

We make everything here mutable because for the next part we’ll be reducing this map to a set of 1:1 mappings between ingredients and allergies.

This solution reminds me a lot of 2020, Day 16, Part 2 where we iteratively build one map from another.

fun solvePart2(): String {
    val ingredientsByAllergy = ingredientsByAllergy()
    val found: MutableMap<String, String> = mutableMapOf()

    while (ingredientsByAllergy.isNotEmpty()) {
        val singles = ingredientsByAllergy
            .filter { it.value.size == 1 }
            .map { it.key to it.value.first() }
            .toMap()
        found.putAll(singles)
        singles.keys.forEach { ingredientsByAllergy.remove(it) }
        ingredientsByAllergy.values.forEach { it.removeAll(singles.values) }
    }

    return found.entries.sortedBy { it.key }.joinToString(",") { it.value }
}

Once we have our ingredientsByAllergy, we declare a found map in order to store our results in. Then we start looping through the ingredientsByAllergy map until it is empty. For every loop through it, we are looking for allergies that have a single ingredient. If that is the case, we know they are a pair. We add the pairs to our found map and remove the ingredient from the ingredientsByAllergy map so we don’t consider it again. We also remove the allergy from our pair from all mappings because we’ve already assigned that allergy to an ingredient. Every time through the loop there should be at least one pair that has a single cause.

To answer the question, we sort the entries we found by their key (the allergy), and join their values (the ingredient) into a string.

Star earned!

See you tomorrow.

⭐ Day 21, Part 1

⭐ Day 21, Part 2

Further Reading