Advent of Code 2020: Day 21

Part 1

You reach the train’s last stop and the closest you can get to your vacation island without getting wet. There aren’t even any boats here, but nothing can stop you now: you build a raft. You just need a few days' worth of food for your journey.

You don’t speak the local language, so you can’t read any ingredients lists. However, sometimes, allergens are listed in a language you do understand. You should be able to use this information to determine which ingredient contains which allergen and work out which foods are safe to take with you on your trip.

You start by compiling a list of foods (your puzzle input), one food per line. Each line includes that food’s ingredients list followed by some or all of the allergens the food contains.

Each allergen is found in exactly one ingredient. Each ingredient contains zero or one allergen. Allergens aren’t always marked; when they’re listed (as in (contains nuts, shellfish) after an ingredients list), the ingredient that contains each listed allergen will be somewhere in the corresponding ingredients list. However, even if an allergen isn’t listed, the ingredient that contains that allergen could still be present: maybe they forgot to label it, or maybe it was labeled in a language you don’t know.

For example, consider the following list of foods:

1
2
3
4

    mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
    trh fvjkl sbzzf mxmxvkd (contains dairy)
    sqjhc fvjkl (contains soy)
    sqjhc mxmxvkd sbzzf (contains fish)

Determine which ingredients cannot possibly contain any of the allergens in your list. How many times do any of those ingredients appear?

You can read the full text here. I love this puzzle.

I initially started to try and solve the whole puzzle immediately, but my code got quite complex and yucky. So as always do when code is not happening, I got up and took a short break. After coming back with a fresh mind I completely change strategy.

Consider the 2 lines of the example:

1
2

mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
trh fvjkl sbzzf mxmxvkd (contains dairy)

they both contain an ingredient with dairy, thus we know that dairy could be any of the ingredients that are in both lists. This is just an intersection. After processing the first line we know that:

1
2

dairy: mxmxvkd kfcds sqjhc nhms
fish: mxmxvkd kfcds sqjhc nhms

then for the second line we know that dairy is now the intersection of the current geuesses and the new clue,

1

dairy: intersect(mxmxvkd kfcds sqjhc nhms, trh fvjkl sbzzf mxmxvkd)

thus we have,

1
2

dairy: mxmxvkd
fish: mxmxvkd kfcds sqjhc nhms

We would now continue this for every line. Now, for each allergen we have a list of all the ingredients which could contain it. Great, but how we do write the code for this? Well the key thing we are doing is reading in each line of the data and storing it so we know the ingredients and potential allergens.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

std::vector<std::pair<std::set<std::string>, std::set<std::string>>> mylist;
std::fstream myfile("input", std::ios_base::in);
std::regex reg("([a-z]+)+");
std::string line;
while (std::getline(myfile, line)) {
    std::sregex_token_iterator it = {line.begin(), line.end(), reg};
    std::set<std::string> ingredients;
    std::set<std::string> allergens;
    while (it != std::sregex_token_iterator()) {
        if ((*it) == "contains") {
            it = std::next(it);
            break;
        }
        ingredients.insert(*it);
        it = std::next(it);
    }
    while (it != std::sregex_token_iterator()) {
        allergens.insert(*it);
        it = std::next(it);
    }
    mylist.push_back({ingredients, allergens});
}
myfile.close();

In the code above we open up a file, use regex to search for words (which don’t contain spaces or brackets), and then store each line of the input as pair of sets. The first set is the ingredients and the second set are the possible allergens. Cool. Now we need a way of taking sets and calculating insersections of the sets. For this, I wrapped the set_intersection function to make it more ergonomic for our use case,

1
2
3
4
5
6
7

template <typename T>
std::set<T> intersection(std::set<T> &s1, std::set<T> &s2) {
    std::set<T> res;
    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
                     std::inserter(res, res.begin()));
    return res;
}

Then we just loop through every set of ingredients in our input, take the intersection for each allergen as described.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// Store intersection of allergen triggers
std::map<std::string, std::set<std::string>> allergen_possibilities;
for (size_t i = 0; i < mylist.size(); i++) {
    std::set<std::string> &ingredients = mylist[i].first;
    std::set<std::string> &allergens = mylist[i].second;

    // Insert all the intersection of current ingredients, and the possible
    // allergen triggers
    for (auto &allergen : allergens)
        if (allergen_possibilities.find(allergen) !=
            allergen_possibilities.end())
            allergen_possibilities[allergen] =
                intersection(ingredients, allergen_possibilities[allergen]);
        else
            allergen_possibilities[allergen] = ingredients;
}

If this is the first time we have seen the allergen then we just store every ingredient in this row. After we’ve applied this filter we can loop every ingredient in the input again and coount how many are not possible candidates for any allergen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// Count ingredients which aren't allergen possibilities
for (size_t i = 0; i < mylist.size(); i++) {
    std::set<std::string> &ingredients = mylist[i].first;
    std::set<std::string> &allergens = mylist[i].second;

    // Check to see if each ingredient is an allergen or not, sum the
    // ingredients that are definitely not allergens
    for (auto &ingredient : ingredients) {
        bool found = false;
        for (auto &a_p : allergen_possibilities) {
            if (a_p.second.find(ingredient) != a_p.second.end())
                found = true;
        }
        if (found == false)
            ans1++;
    }
}

There we go, first ⭐!

Part 2

Now that you’ve isolated the inert ingredients, you should have enough information to figure out which ingredient contains which allergen.

In the above example:

1
2
3

    mxmxvkd contains dairy.
    sqjhc contains fish.
    fvjkl contains soy.

Arrange the ingredients alphabetically by their allergen and separate them by commas to produce your canonical dangerous ingredient list. (There should not be any spaces in your canonical dangerous ingredient list.) In the above example, this would be mxmxvkd,sqjhc,fvjkl.

Time to stock your raft with supplies. What is your canonical dangerous ingredient list?

You can read the full text here. So part 2 is fairly straight forward. Now that we have a short list of candidates for every allergen we just need to figure out which is which. For my input we can print out the possibilites for every allergen,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Possibilities
=============
dairy: rnbhjk, ttxvphb, vv,
eggs: nlxsmb,
fish: rnbhjk, ttxvphb,
nuts: bvnkk, jpvz, qmkz, ttxvphb, vv,
peanuts: nlxsmb, ttxvphb,
shellfish: jpvz, qmkz, trmzkcfg, ttxvphb,
soy: trmzkcfg, vv,
wheat: jpvz, ttxvphb,

We can then solve this trivially with pen and paper. The eggs has to be caused by “nlxsmb”, thus the peanuts must be “ttxvphb” and then the fish must be “rnbhjk” and so on. In fact, this is how I did solve it, but for the interested reader I’ve attached code below which solves it more generally,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Loop through and simulatenously solve for each allergen
bool solved = false;
while (!solved) {
    solved = true;
    for (auto &a_p : allergen_possibilities) {
        if (a_p.second.size() > 1) {
            solved = false;
        } else if (a_p.second.size() == 1) {
            for (auto &a_p2 : allergen_possibilities) {
                if (a_p.first == a_p2.first)
                    continue;

                std::set<std::string>::iterator it =
                    a_p2.second.find(*a_p.second.begin());

                if (it != a_p2.second.end()) {
                    a_p2.second.erase(it);
                }
            }
        }
    }
}

and there we go, both stars ⭐⭐!

Reflections

I really enjoyed todays puzzle, I thought it was a really good puzzle to solve. I think the code I’ve written is both very readable and quite concise. The algorithm is also quite efficient.

We start by looping through and reading in every value in the input. This is O(N)-time and space, where N is the number of lines in the input. We then loop through each line taking the intersection for each of the possible allergens. This step scales similarly in both time and space. I’m also assuming my map lookup is O(1), which is not currently true but can be achieved with an unordered_map.

The second step just involves looping over each of the allergens a few times, thus it just scales as O(M) where M is the number of allergens, which is very small. I particularly liked that I could solve part 2 on paper in less than 30 seconds!

Anyway, thanks for reading. I’m back up to date with Advent of Code puzzles and due to covid I’m not travelling for Christmas. Look forward to seeing you all tomorrow, hopefully we can have a couple of slightly easier puzzles!

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Comments