Advent Of Code 2020 – Day 6 – Custom Customs

This problem was a bit hard to understand at first because the information is not directly given, you have to derive it from the given input.

The story goes like this, your aeroplane has reached a regional office where you will switch to a much larger plane, custom declaration forms are distributed to passengers.

The form asks a series of yes-or-no questions marked from a-z. And here’s your task – you need to identify questions for which anyone in your group answers “yes”. However, you don’t just have to answer this for your group (because that would be easy), you have to answer this for all the groups sitting there. Your input is basically their yes answer to any of the questions in the single line. For example –

abcx
abcy
abcz

Here’s each line consists of the question number (a-z) for which anyone in the group have answered “yes”.

So, in the example above there are 6 questions to which anyone answered yes: a, b, c, x, y, z. Duplicate answers to the same questions do not count.

I’ll copy paste one more example from the Advent of Code Website.

So, for each group, count the number of questions for anyone answered “yes”.

What is the sum of those counts?

Part One – Count the number of questions for anyone answered YES

The first part of the problem is understanding the format in which we get the input and parse it accordingly. So, as you can see from the above example every group is separated by a new line. So, as we encounter the empty line we would know that all the people of that group have answered the question and then we will count the total questions which were answered YES.

(In the original question I solved it using c++, but in the blog, I will use python to explain the solution because it feels more readable for someone who is new to the programming. So if you are looking for the solution in c++ language, do comment below and I will provide the code there)

Below code makes use of the fileinput python module that could read the file from the path passed to the script as a parameter. To execute below code use: python3 day6.py <input_file_path>.

   1 import fileinput
   2
   3 lines = [line.strip() for line in fileinput.input()]
   4
   5 # since we are relying on the empty line
   6 # to identify the group of people
   7 # empty line at the end is required to count
   8 # the last group
   9 lines.append('')
  10
  11 # we need all the unique answers
  12 # set is the right data structure to keep 
  13 # track of the distinct objects
  14 yes_questions = set()
  15 sum = 0
  16 for line in lines:
  17     if not line:
  18         # if we encounter an empty line
  19         # count the total questions answered YES
  20         # and reset the set
  21         sum += len(yes_questions)
  22         yes_questions.clear()
  23     else:
  24         for q in line:
  25             yes_questions.add(q)
  26
  27 print(sum)
 

Viola!!!

That’s all for part one. The problem seemed difficult but it was actually easy once you understand what is asked for. So, all the logic goes in the line 17-22.

Try running the solution for you given set of input.

So, let’s see what is asked in the part two of the problem.

Part Two – Count the questions for which everyone answered YES

Turns out we misread the instruction. We were suppose to count all questions for which EVERYONE in the group answered YES. So, let’s see how can we build our current solution to solve the second part.

While solving the second part in I realized something that the solution is purely mathematical. And python is a great language to express mathematical expressions via code. So, if you observe closely, what the problem actually asks is the intersection between each line of the input. So, the problem can actually be solved by doing it the following way:

    for line in lines:  
       if not line:
           sum += len(all_yes)
           all_yes = None
       else:
           if all_yes is None:
               all_yes = set(line)
           else:
               all_yes = all_yes & set(line)

Let’s take the given example to understand it better.

abc

a
b
c

ab
ac

a
a
a
a

b

Dry Run Of The Above Code

line	all_yes (SET = starts with None)	SUM
abc	{a,b,c}	0
”	RESET	0 + 3 = 3
a	{a}	3
b	{a} & {b} = {}	3
c	{} & {c} = {}	3
”	RESET	3 + 0 = 3
ab	{a,b}	3
ac	{a,b} & {a,c} = {a}	3
”	RESET	3 + 1 = 4
a	{a}	4
a	{a} & {a} = {a}	4
a	{a} & {a} = {a}	4
a	{a} & {a} = {a}	4
”	RESET	4 + 1 = 5
b	{b}	5
”	RESET	5 + 1 = 6

So at the end we get 6 which is the correct answer for the example problem.

Let me give you the complete code for the second part.

   1 import fileinput
   2
   3 lines = [line.strip() for line in fileinput.input()]
   4
   5 # since we are relying on the empty line
   6 # to identify the group of people
   7 # empty line at the end is required to count
   8 # the last group
   9 lines.append('')
  10
  14 yes_questions = set()
  15 all_yes = None
  16 sum = 0
  17 for line in lines:
  18     if not line:
  19         # if we encounter an empty line
  20         # count the number of question 
             # to which everyone answered YES
  22         sum += len(all_yes)
  23         all_yes = None
  24     else:
  25         if all_yes is None:
  26             all_yes = set(line)
  27         else:
  28             all_yes = all_yes & set(line)
  29
  30 print(sum)

I hope this problem was fun to solve. If you are following along then do subscribe to solve Advent of Code questions with me.

Do let me know if there is anything else that you would like to read about?