Advent of Code 2020: Day 7

, 9 min read
advent of code 2020

Part 1

You land at the regional airport in time for your next flight. In fact, it looks like you’ll even have time to grab some food: all flights are currently delayed due to issues in luggage processing. Due to recent aviation regulations, many rules (your puzzle input) are being enforced about bags and their contents; bags must be color-coded and must contain specific quantities of other colour-coded bags. Apparently, nobody responsible for these regulations considered how long they would take to enforce!

For example, consider the following rules:

light red bags contain 1 bright white bag, 2 muted yellow bags. dark orange bags contain 3 bright white bags, 4 muted yellow bags. bright white bags contain 1 shiny gold bag. muted yellow bags contain 2 shiny gold bags, 9 faded blue bags. shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags. dark olive bags contain 3 faded blue bags, 4 dotted black bags. vibrant plum bags contain 5 faded blue bags, 6 dotted black bags. faded blue bags contain no other bags. dotted black bags contain no other bags.

You have a shiny gold bag. If you wanted to carry it in at least one other bag, how many different bag colours would be valid for the outermost bag? (In other words: how many colours can, eventually, contain at least one shiny gold bag?)

So, in the example above, the number of bag colours that can eventually contain at least one shiny gold bag is 4.

How many bag colours can eventually contain at least one shiny gold bag? (The list of rules is quite long; make sure you get all of it.)

You can read the full text here. It’s one of those days where processing the input is hard. Fortunately, I took some time on day 2 to learn a bit of regex. Consider the follwing line in the input, light red bags contain 1 bright white bag, 2 muted yellow bags.

My first step is to break the line at “bags contain”, so we have the two strings, light red 1 bright white bag, 2 muted yellow bags.

Now, the first string is done. We have the colour of the outermost bag on this input line. Next, we need to loop through the second line and extract the numbers and colours. Namely, we want to process the second line into something like the following: light red 1, bright white 2, muted yellow

This format would allow us to fill a container of rules. This container would contain the numbers and types of bags that a given bag could contain. For the example above, we would like: rules[“light red”] = [ (“bright white”, 1), (“muted yellow”, 2), ]

Now, how do we achieve this data processing in C++? The first part of our code looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    std::map<std::string, std::vector<std::pair<std::string, int>>> rules;
    std::fstream myfile("input", std::ios_base::in);
    std::string line;
    std::smatch pieces_match;
    while (std::getline(myfile, line)) {
        // First I match the outer bag and what it contains
        std::regex pieces_regex("(.*) bags contain (.*)");
        std::regex_search(line, pieces_match, pieces_regex);
        // Outer bag is easy to process
        std::string container = pieces_match[1];
        // Then we need to process all the bags it contains
        std::string contains = pieces_match[2];
    }

This gets us to part 1. We used regex to split our string at “bags contain”, and thus we have the container bag, alongside a string of unprocessed bags which are contained.

Now, we are going to use regex again to process the second line,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
        std::string contains = pieces_match[2];
        std::regex reg("(\\d+) ([a-z\\s]+) bag");
        std::sregex_token_iterator it = {contains.begin(), contains.end(), reg, {1, 2}};
        while (it != std::sregex_token_iterator()) {
            int num = std::stoi(*it);
            it = std::next(it);
            std::string type = *it;
            it = std::next(it);
            rules[container].push_back({type, num});
        }

We achieve this by looking for patterns of the form "(\d+) ([a-z\s]+) bag". This pattern is a number, followed by a space and then the description of the bag, which is a string of a-z characters and spaces. All of this is followed by the word bag(s). We loop through the contained bags and search for this pattern. When we find the pattern, we create a map of strings which stores a vector of all the contained bag descriptions, and their count. For this we’re using a map with strings as the key, and a vector of pair<string, int>’s as the value.

Great! We have ingested the input, and now we have a map of rules which stores all of the bags which can be stored within other bags. But how do we solve the puzzle?

We need to loop through every unique bag which we have seen, and then loop through all of the bags they can contain, and all of the bags that those bags can contain, recursively, until we reach the bottom. Or, we reach the “shiny gold” bag. If we encounter the “shiny gold” bag, then we are done, as we know that the current outer bag is a solution, and we increment our counter. I generally try to avoid recursion, so for this problem, we’re using a list:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    // Part 1: how many different colour outer bags, contain a shiny gold bag?
    for(std::string ob : bags){
	// We don't want the gold bag alone, so skip
        if (ob == "shiny gold")
            continue;
        std::list<std::string> possible_bags = {ob};
        while (possible_bags.size() > 0){
            std::string b = possible_bags.front();
            // We found gold bag, lets move on
            if (b == "shiny gold"){
                ans1++;
                break;
            }
            // Add extra bags to check
            for(auto kv : rules[b]){
                possible_bags.push_back(kv.first);
            }
            possible_bags.pop_front();
        }
    }

In the code above we are using a list to keep track of all the contained bags we must check in our breadth-first search. We keep looping over all of the contained bags, popping them off our list and appending their contained bags to the end of our list. There we have it, the first ⭐!

The full code can be found on github

Part 2

It’s getting pretty expensive to fly these days - not because of ticket prices, but because of the ridiculous number of bags you need to buy!

Consider again your shiny gold bag and the rules from the above example: faded blue bags contain 0 other bags. dotted black bags contain 0 other bags. vibrant plum bags contain 11 other bags: 5 faded blue bags and 6 dotted black bags. dark olive bags contain 7 other bags: 3 faded blue bags and 4 dotted black bags.

So, a single shiny gold bag must contain 1 dark olive bag (and the 7 bags within it) plus 2 vibrant plum bags (and the 11 bags within each of those):

1 + 17 + 2 + 211 = 32 bags!

How many individual bags are required inside your single shiny gold bag?

You can read the full text here. I’m very glad we processed the numbers in part 1, because we need them here.

For this puzzle, we need to start with the “shiny gold” bag and loop through all of the bags it contains and count how many bags in total. However, if the “shiny gold” bag contains “10 blue” bags and each “blue bag” contains “3 red” bags then our “shiny gold” bag includes 10 * 3 = 30 bags. Thus, we need to keep track of how deep we are through the process to ensure we add the correct amount of bags. However, the code is actually similar to part 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    // Part 2: how many bags in a shiny gold bag?
    std::list<std::pair<std::string, int>> possible_bags;
    possible_bags.push_back({"shiny gold", 1});
    while (possible_bags.size() > 0){
        std::pair<std::string, int> b = possible_bags.front();
        ans2 += b.second;
        // Add extra bags to check
        for(auto kv : rules[b.first]){
            possible_bags.push_back({kv.first, kv.second*b.second});
        }
        possible_bags.pop_front();
    }
    ans2--;

In the code above, we start with the 1 “shiny gold” bag and loop through all of the bags it contains. We append these bags onto the end of our list, but we set the number of them to be our current number of bags multiplied by how many we contain. We now just loop until there are no further bags.

Final point: the puzzle asks how many bags are IN the “shiny gold” bag, but our code also counted the “shiny gold” bag so we must subtract 1 from our answer to get the correct answer.

That’s both ⭐⭐!

The full code can be found on github

Reflections

We processed the input line by line, where each line gives information about a single bag. I don’t think it’s possible to solve this puzzle without processing and storing information about each bag. In the worst-case each bag could contain N-1 bags, where N is the total number of bags. Thus, after processing the input we have a solution which is O(N *N) in both space and time.

For part 1, we then perform a breadth-first search. This is a double loop, where for each outer bag we loop through all of the bags it contains, recursively. Given, the current puzzle constraints this will also be O(N *N) time and O(N) space. Part 2 starts with a single bag and loops down recursively, so this is just O(N) time and space.

It is also worth point out that our input is quite sparse. Most of the bags contain M bags where M is a lot smaller than N, and approximately constant. In this case, the time and space complexity predictions presented here are pessimistic cases, and will reduce to O(N) in most cases.

I’m assuming the map lookup is O(1), which is not currently true but can be achieved with an unordered_map.

. . . .

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

Back to my advent calendar

Comments

Back to all posts