Advent of Code 2020: Day 6

, 5 min read
advent of code 2020

Part 1

As your flight approaches the regional airport where you’ll switch to a much larger plane, customs declaration forms are distributed to the passengers.

The form asks a series of 26 yes-or-no questions marked a through z. The person sitting next to you seems to be experiencing a language barrier and asks if you can help. For each of the people in their group, you write down the questions for which they answer “yes”, one per line.

Another group asks for your help, then another, and eventually you’ve collected answers from every group on the plane (your puzzle input). Each group’s answers are separated by a blank line, and within each group, each person’s answers are on a single line. For example:

abc

a b c

For each group, count the number of questions to which anyone answered “yes”. What is the sum of those counts?

You can read the full text here. For this puzzle we need to read our input file which represents the questions that each person, in each group said “yes”. The response of each person is on a new line, and each group is separated by a blank line.

This input format is quite easy to go through. So what next? Well, within a group we need to find all of the answers that any of the group member said “yes”. Normally for problems like this I would use a set to store all the unique answers. However, the input data in this problem is always a-z. Thus, if we convert these char’s to integers we just have 26 unique values. Thus, we can use a standard array to store whether or not a letter was present, e.g.,

1
 present[int(line[i]) - 97]++;

where we subtract 97 as int(a) == 97, int(b) == 98, …, therefore this maps our input into integers in the range [0-25].

We can then put all of this together with the following code,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
 std::array<char, 26> present;
 present.fill(0);
 while (std::getline(myfile, line)) {
     if (line == "") {
         // Anyone answered yes
         for (long unsigned int i = 0; i < 26; i++)
             if (present[i] > 0)
                 ans1++;
         // Reset counter
         present.fill(0);
     } else {
         // Store responses
         for (long unsigned int i = 0; i < line.size(); i++)
             present[int(line[i]) - 97]++;
     }
 }

In the code above we are looping through the file and compiling the results of each group into an array, present.

When we reach a blank line, we know we have finished with that group. We then loop through and find all questions which at least one person in the group answered “yes”. We sum all of these, and there we have it, the first ⭐!

The full code can be found on github

Part 2

As you finish the last group’s customs declaration, you notice that you misread one word in the instructions:

You don’t need to identify the questions to which anyone answered “yes”; you need to identify the questions to which everyone answered “yes”!

You can read the full text here.

Part 2 follows on very quickly. Except, instead of finding elements in the array where at least one person said “yes”, we need to find the answers to which everyone said “yes”. We just need to modify the code to track how many people are in the group and add an extra check when the group is complete.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
std::array<char, 26> present;
present.fill(0);
int num_people = 0;
while (std::getline(myfile, line)) {
    if (line == "") {
        ...
        // All answered yes
        for (long unsigned int i = 0; i < 26; i++)
            if (present[i] == num_people)
                ans2++;
        // Reset counters
        present.fill(0);
        num_people = 0;
    } else {
        // Store responses
        num_people++;
        for (long unsigned int i = 0; i < line.size(); i++)
            present[int(line[i]) - 97]++;
    }
}

Now that we have tracked how many people are in the group, we just need to change our if from anything greater than 0, to be equal to the number of people in the group. That’s it, we have identified how many questions that every person in each group said “yes” to. That’s the double ⭐⭐!

The full code can be found on github

Reflections

I don’t think there is much further optimisation I can make for puzzle today. We read in the data, process and discard. Then we loop through the present array in a single pass to identify the union and the intersection for answers in our group.

This solution will be O(N)-time and O(1)-space where N is the number of groups that we need to process.

For a more complicated range of inputs I would have used an unordered_map to do the exact same process but taking advantage of the STL’s hashing function. This would scale in a very similar way.

I hope to see you all tomorrow where as well as solving the puzzle, I’ll also produce a short write-up summarising the first week. Thanks for reading!

. . . .

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