Advent of Code 2020: Day 19

, 8 min read
advent of code 2020

Part 1

You land in an airport surrounded by dense forest. As you walk to your high-speed train, the Elves at the Mythical Information Bureau contact you again. They think their satellite has collected an image of a sea monster! Unfortunately, the connection to the satellite is having problems, and many of the messages sent back from the satellite have been corrupted.

They sent you a list of the rules valid messages should obey and a list of received messages they’ve collected so far (your puzzle input).

The rules for valid messages (the top part of your puzzle input) are numbered and build upon each other. For example:

1
2
3
4
0: 1 2
1: "a"
2: 1 3 | 3 1
3: "b"

Some rules, like 3: “b”, simply match a single character (in this case, b).

The remaining rules list the sub-rules that must be followed; for example, the rule 0: 1 2 means that to match rule 0, the text being checked must match rule 1, and the text after the part that matched rule 1 must then match rule 2.

Some of the rules have multiple lists of sub-rules separated by a pipe (|). This means that at least one list of sub-rules must match. (The ones that match might be different each time the rule is encountered.) For example, the rule 2: 1 3 | 3 1 means that to match rule 2, the text being checked must match rule 1 followed by rule 3 or it must match rule 3 followed by rule 1.

The received messages (the bottom part of your puzzle input) need to be checked against the rules so you can determine which are valid and which are corrupted. Including the rules and the messages together, this might look like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"

ababbb
bababa
abbbab
aaabbb
aaaabbb

How many messages completely match rule 0?

You can read the full text here. Oooh! Well, this is interesting. Unfortunately, the write up to this puzzle is delayed, due to Christmas festivities. As such, I am aware that many people solved this puzzle using pure regex. However, I did not!

These xmas lists are confusing
These xmas lists are confusing

The first thing we need to do is write a parser. We need to read the rules and store them in memory. The rules are made up of two types. The first type I call a base pattern, e.g.,

1
2
4: "a"
5: "b"

and we have extended patterns:

1
2: 4 4 | 5 5

which means the possible patterns for rule 2 are,

1
2
a a
b b

as the “|” means “or”. Thus, for general patterns, we must keep reducing until we reach a base pattern. For this solution, I wrote a really flimsy parser using standard string manipulation. This parse produces two map’s of the form, “key:rule”. For non-base rules which can contain “|” (“or”), we have a list of rules.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
while(std::getline(myfile, line)){
    int key = 0;
    int quote = 0, index = 0, last = 0;
    std::string pattern = "";
    if (line == "")
        break;
    std::vector<std::list<int>> all_indexes;
    std::list<int> indexes;
    for(size_t i=0; i<line.size(); i++){
        int ascii = int(line[i]);
        if (line[i] == ':')
            key = std::stoi(line.substr(0, i));
        else if (line[i] == ' '){
            if ((index > 0) && (last ==  -1))
                indexes.push_back(std::stoi(line.substr(index+1, i-index-1)));
            index = i;
        }
        ...
    }
}

I skipped some of the code, but you get the idea. Now we have all the processed, we need to write a function which can take a message in and perform a depth-first search which attempts to match it.

So how do we do that? Well we loop through our rule and check if the value predicted by our rule is in the message. If our rule is not a base pattern then we must recurse down the rule until we reach a base pattern. We achieve this with the following code,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool check(std::string &s, std::list<int> &sequence){
    if ((s == "") || (sequence.size() == 0)){
        if ((s == "") && (sequence.size() == 0))
            return true;
        else
            return false;
    }
    std::unordered_map<int, char>::iterator it1 = base_patterns.find(sequence.front());
    if (it1 != base_patterns.end()){
        sequence.pop_front();
        if ((*it1).second == s[0]){
            std::string new_s = s.substr(1, s.size()-1);
            return check(new_s, sequence);
        }
        else
            return false;
    }
    else {
        std::unordered_map<int, std::vector<std::list<int>>>::iterator it2 = patterns.find(sequence.front());
        sequence.pop_front();
        for (auto t : (*it2).second){
            t.insert(t.end(), sequence.begin(), sequence.end());
            bool success = check(s, t);
            if (success)
                return true;
        }
        return false;
    }
}

We will ignore the first part for now part and go straight to discussing the first if statement. We check if the current rule is a base rule. If it is, then it is either an “a” or a “b”. If the first value of the current message is equal to it, then we remove the first value and move onto the next rule in the sequence.

However, if this is not a base rule, we replace the rule with the rules it is made up of. If it is made up of multiple rules with an “or” then we recursively try every possible combination. We return true whenever we find a solution. We don’t necessarily have to try every possible path!

Finally, the first part of this function is our end situation. If the message is now empty, or the possible sequence reached the end, then we are done. If the message is empty, and the sequence is complete, then this is a valid solution, but if either of these is false, this message is not valid. We can also exit if the current sequence is longer than the message we are trying to match, as we know this can never work.

1
2
if (sequence.size() > s.size())
    return false;

Now we just loop over and apply this depth first search to all of our messages,

1
2
3
4
5
// Part 1
for(auto t : targets){
    std::list<int> sequence = {0};
    ans1 += int(check(t, sequence));
}

Just sum all the valid messages and that’s the first ⭐!

The full code can be found on github

Part 2

As you look over the list of messages, you realize your matching rules aren’t quite right. To fix them, completely replace rules 8: 42 and 11: 42 31 with the following:

1
2
8: 42 | 42 8
11: 42 31 | 42 11 31

This small change has a big impact: now, the rules do contain loops, and the list of messages they could hypothetically match is infinite. You’ll need to determine how these changes affect which messages are valid.

Fortunately, many of the rules are unaffected by this change; it might help to start by looking at which rules always match the same set of values and how those rules (especially rules 42 and 31) are used by the new versions of rules 8 and 11.

After updating rules 8 and 11, how many messages completely match rule 0?

You can read the full text here.

For us, this is a simple change. As we perform a depth-first search in part 1 we just change the rules as described and try again. As our function checks if the string is empty, but the sequence is still continuing, and exits, we are not really affected by recursion.

1
2
3
4
5
6
7
8
9
// Make recursive
patterns[8] = {{42}, {42, 8}};
patterns[11] = {{42, 31}, {42, 11, 31}};

// Part 2
for(auto t : targets){
    std::list<int> sequence = {0};
    ans2 += int(check(t, sequence));
}

Well, that was straightforward, our code dealt with this really easily. Both stars- ⭐⭐!

The full code can be found on github

Reflections

I think today’s code is fairly readable, and the algorithm is straightforward. However, it is far from optimal. Namely, for each rule there could be 2 possible paths because of the or. Thus, we could try 2^N variations before we validate, or invalidate a message, where N is the length of the message.

Fortunately, the messages are quite short, so N is typically small. We are also helped by the fact that we are able to validate a lot of messages before try every possible sequence. As such, while the algorithm scales quite poorly, the time to solution is not too long. In summary our algorithm scales as O(2^N)-time and roughly, O(N)-space where N is the mean length of the messages we are testing. I’m also assuming my map lookup is O(1), which is not currently true but can be achieved with an unordered_map.

There is an alternative algorithm, the CYK which can solve this problem in O(N^3)-time (I believe). However, I haven’t read about much about this. That’s a task for a future day.

Thanks for reading, sorry for the delay. See you all soon.

. . . .

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