DEV Community

loading...

Advent of Code: 2020 Day 06

Christopher Nilsson
Full-stack enthusiast working currently on next.js/React/Typescript/Node.
・4 min read

⚠️ SPOILER ALERT ⚠️
This is a post with my solutions and learning from the puzzle. Don't continue reading if you haven't tried the puzzle on your own yet.

If you want to do the puzzle, visit adventofcode.com/2020/day/6.

My programming language of choice is python and all examples below are in python.

TOC

Key learning

  • Sets and dictionaries

This puzzle teaches us how to counting unique elements in lists.

Puzzle

The puzzle is about groups of persons answering questions and the goal is to count the results.

The questions are named a-z. Only questions answered "yes" to are present in the input. The questions that one person answered are in one line. The groups of persons are separated by an empty line. Example input:

abc

a
b
c

ab
ac

a
a
a
a

b
Enter fullscreen mode Exit fullscreen mode

Part 1

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

Parse input-data:

If we read the file as a whole without stripping away all the new-line characters (\n) we can quickly group the groups by splitting on double new-line.

f = open('06.input', 'r')
data = f.read()
groups = data.strip().split('\n\n')
Enter fullscreen mode Exit fullscreen mode

Solution:

Using a set as data structure is the simplest way to solve this puzzle. The built-in set in python will handle duplicates for us.

def part1(groups):
    total = 0
    for group in groups:
        # 1. Remove all new-line characters
        # 2. Extract unique letters by creating a set
        # 3. Count size of set
        total += len(set(group.replace('\n', '')))
    return total
Enter fullscreen mode Exit fullscreen mode

Part 2

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

In this puzzle a set won't do anymore as we need to keep track of occurrences for each letter.

Solution:

Using a dictionary here is more valuable as we can use the key-value store to keep track of occurence per letter.

def part2(groups):
    total = 0
    for group in groups:
        # Use dictionary to count occurrences of letters
        occurrences = {}
        for letter in group:
            if letter not in occurrences:
                occurrences[letter] = 0
            occurrences[letter] +=1

        # By splitting on new-line we get each persons answers.
        person_count = len(group.split('\n'))

        # Filter out letters that occur once per persons in group
        answered_by_all = [x == person_count for x in occurrences.values()]
        total += sum(answered_by_all)
    return total
Enter fullscreen mode Exit fullscreen mode

Alternative solution

Python is all about making it easy for the developer. It exists already a library called Counter helping us with counting. Using it would make our code cleaner and would look like this:

from collections import Counter
def part2count(groups):
    total = 0
    for g in groups:
        # Use counter to count occurrences of letters
        letter_counter = Counter(g)

        # By splitting on new-line we get each persons answers.
        person_count = len(group.split('\n'))

        # Filter out letters that occur once per persons in group
        answered_by_all = [x == person_count for x in occurrences.values()]
        total += sum(answered_by_all)
    return total
Enter fullscreen mode Exit fullscreen mode

Read more about Counter here: https://docs.python.org/3/library/collections.html

Set operations

These puzzles are essentially doing unions and intersections for each group. Using set operations it could look like this:

groups = open('06.input', 'r').read().strip().split('\n\n')

def part1set(groups):
    sets = [map(set, group.splitlines()) for group in groups]
    unions = [set.union(*s) for s in sets]
    return sum(map(len, unions))
print part1set(groups)

def part2set(groups):
    sets = [map(set, group.splitlines()) for group in groups]
    intersections = [set.intersection(*s) for s in sets]
    return sum(map(len, intersections))
print part2set(groups)
Enter fullscreen mode Exit fullscreen mode

Functional style

These function are easy to write in a more functional style. My opinion is that it is less verbose, but a tad more complex to read.

def part1func(groups):
    return sum([
        len(set(group.replace('\n','')))
        for group
        in groups
    ])

def part2func(groups):
    return sum([
        len([x for x in Counter(group).values() if x == len(group.split('\n'))])
        for group
        in groups
    ])
Enter fullscreen mode Exit fullscreen mode

Python tricks

Instead of filtering on a boolean comparison and check the length, we can just
map the element to the boolean and sum them. The sum will be treat the booleans
as 1 if True or 0 if False. See example below:

answered_by_all = [
  x
  for x
  in occurrences.values()
  if x == person_count
]
total += len(answered_by_all)

# Same as above
answered_by_all = [
  x == person_count
  for x
  in letter_counter.values()
]
total += sum(answered_by_all)
Enter fullscreen mode Exit fullscreen mode

Deconstructing parameters

In the set function we do a set.union(*arr). What it does is that it spreads
the arrays elements as parameters. Example:

def my_function(a,b,c):
  return a * b * c

arr = [1,2,3]
res = my_function(*arr)
# Will output res = 6.
Enter fullscreen mode Exit fullscreen mode

Thanks for reading!

I hope these solutions were helpful for you.

Complete code can be found at: github.com/cNille/AdventOfCode/blob/master/2020/06.py

Discussion (0)