Categories
Programming What I’m Up To

My solution to Advent of Code 2020’s Day 6 challenge, in Python

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 6 of Advent of Code, titled Custom Customs.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 6 challenge.

The Day 6 challenge, part one

The challenge

Here’s the text from part one of the challenge:

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. All you need to do is identify the questions for which anyone in your group answers “yes”. Since your group is just you, this doesn’t take very long.

However, 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. For example:

In this group, there are 6 questions to which anyone answered “yes”: abcxy, and z. (Duplicate answers to the same question don’t count extra; each question counts at most once.)

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:

This list represents answers from five groups:

  • The first group contains one person who answered “yes” to 3 questions: ab, and c.
  • The second group contains three people; combined, they answered “yes” to 3 questions: ab, and c.
  • The third group contains two people; combined, they answered “yes” to 3 questions: ab, and c.
  • The fourth group contains four people; combined, they answered “yes” to only 1 question, a.
  • The last group contains one person who answered “yes” to only 1 question, b.

In this example, the sum of these counts is 3 + 3 + 3 + 1 + 1 = 11.

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

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into a Jupyter Notebook running a Python kernel.

This involves pasting it into a triple-quoted string and assigning it to the variable raw_input, and then splitting it using two newline characters in a row as a delimiter, producing a list named split_input:

Each item in the split_input list represents the collected answers for a group. If a group has more than one person in it, a newline character separates each person’s answers.

In the sample of split_input shown below:

  • The first line shows the answers for the first group, which is made up of two people.
  • The fifth line shows the answers for the fifth group, which is made up of five people. All of them answered yes to only one question: Question v.

Finally, I split each item in split_items, using the newline character as the separator:

The result was a list that I named groups, where:

  • Each item in groups represents a group of passengers
  • Each group is a list, where each item in the list represents the answers for one passenger in that group.

Here’s a sample of groups:

With the input data massaged into something that could easily be processed in Python, it was time to get to work.

Strategy

The goal was to get the total of all the “yes” answers for all the groups, keeping in mind that if any person in the group answers “yes” to a given question, the group is considered to have answered “yes” to that question.

Consider a group of three people. If:

  • the first person in the group answered “yes” to questions a, b, and c,
  • the second person in the group answered “yes” to questions d, e, and f,
  • and the third person in the group answered “yes” to questions g, h, and i…

…the the group is considered to have answered yes to questions a though i.

To put it mathematically, a group’s answers was the union of the answers of everyone in the group.

With that in mind, I wrote this function:

This function takes advantage of the fact that while Python’s union() is a set method, it can take one or more non-set arguments, as long as it can convert the arguments into a set.

For example, this code:

results in this set:

I rearranged the set so that its items would appear in alphabetical order so that it would be easier to read. This is fine, because with sets, there is no order.

Now that I had count_union_group_answers(), I could apply it to groups

…and get the answer for part one: 6504.

The Day 6 challenge, part two

The challenge

Here’s the text of part two:

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”!

Using the same example as above:

This list represents answers from five groups:

  • In the first group, everyone (all 1 person) answered “yes” to 3 questions: ab, and c.
  • In the second group, there is no question to which everyone answered “yes”.
  • In the third group, everyone answered yes to only 1 question, a. Since some people did not answer “yes” to b or c, they don’t count.
  • In the fourth group, everyone answered yes to only 1 question, a.
  • In the fifth group, everyone (all 1 person) answered “yes” to 1 question, b.

In this example, the sum of these counts is 3 + 0 + 1 + 1 + 1 = 6.

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

Strategy

This time, the goal was to get the total of all the “yes” answers for all the groups, keeping in mind that the group is only considered to have answered “yes” to a given question if every person in the group answered “yes” to that question.

Consider a group of three people. If:

  • the first person in the group answered “yes” to questions a, b, and c,
  • the second person in the group answered “yes” to questions a, e, and f,
  • and the third person in the group answered “yes” to questions a, h, and i…

…the the group is considered to have answered yes to question a, and nothing else.

To put it mathematically, a group’s answers was the intersection of the answers of everyone in the group.

All I had to do was tweak the count_union_group_answers() function from part one to find the intersection of group members’ answers…

…and then apply count_intersection_group_answers() to groups

This gave me the answer for part two: 3351.

Recommended reading

Solutions for other days in Advent of Code 2020

One reply on “My solution to Advent of Code 2020’s Day 6 challenge, in Python”

Will post here too — did mine in bash:

rm xx*; cat advent6-input.txt | tr “\n” “{” | sed ‘s/{{/}/g’ | sed ‘s/./&\n/g’ | grep -v ‘{‘ | csplit -s -n 4 –suppress-matched – ‘/}/’ ‘{*}’; for i in xx*; do cat $i | tr -s “\n” | sort -u | wc -l ; done | (sed ‘s/$/+/’ | tr -d “\n”; echo 0) | bc

or better formatted with explanation and comments:

general strategy is to get every group into a file with one line per letter as it occurs in the group. this is the meat of the input reformatting code with the tr’s sed’s and grep’s, mostly converting newlines to detect start/end of group (double newline only), then splitting them into seperate files per group with csplit(1).
simple then to just sort the group uniquely and count the unique items per group, add them all up.

rm xx*;
cat advent6-input.txt |
tr “\n” “{” | #newlines to {
sed ‘s/{{/}/g’ | #double newline is end of group, to }
sed ‘s/./&\n/g’ | # newline after every character
grep -v ‘{‘ | # del original input single newlines
csplit -s -n 4 –suppress-matched – ‘/}/’ ‘{*} # split on } into sep files

for i in xx*; do # for every xx0* file created by csplit
cat $i | # every file to stdout
tr -s “\n” | # compress newlines
sort -u | # sort to unique items only
wc -l ; # count # of lines which is # of uniques
done | # output all counts to add them all up
(sed ‘s/$/+/’ | # put + on EOL for bc to add
tr -d “\n”; # delete newlines for bc input
echo 0) | bc # put a 0 on end (so ends in +0) and add!

Leave a Reply

Your email address will not be published. Required fields are marked *