AoC '20: Twenty Questions

AoC '20: Twenty Questions

We sit back on our flight, enjoying a smooth ride through the winter sky. As we approach the next airport on our itinerary, one of the attendants begins handing out customs declaration forms. Each form has a series of questions, quite helpfully labelled alphabetically. The instructions explain that we need only identify those queries to which a member of our group would answer in the positive. Since the group is just us, it'll be a doddle.

Our sheet filled in, and seat upright ready to land, our neighbour to the south taps us on the shoulder. They appear to be experiencing some difficulty completing the form.

Day 6: Custom Customs

One passenger helped becomes another, and another until, eventually, we've managed to gather answers from every group on board. Our list looks similar to the following example.

abc

a
b
c

ab
ac

a
a
a
a

b

A blank line separates each group of answers, and each person answers on a new line. The first group contains one person who responded to questions a, b and c. The second group includes three people, each answering one of a, b and c. The third example comprises two passengers, answering a and one each of b and c. If we were to sum the counts of all unique, positive answers, we would compute 3 + 3 + 3 + 1 + 1 equals 11. We transform the list of responses into an array of groups of answers, where each group is a 'subsequence' of the initial collection. Each set of answers is a simple string.

Part 1

To help the attendants along, we should take a moment to find the sum of all unique, positive answers in each group. In solving yesterdays puzzle, we briefly discussed set theory, the branch of mathematical logic concerned with collections of arbitrary-but-unique objects. Specifically, we made use of the concept of relative complement, or set difference, to identify the vacant seat that the airline had assigned to us. We'll use another idea, intersection, later on, but for now, we need only exploit the uniqueness.

forms.compactMap { form in Set(form.joined()).count }.reduce(0, +)

Since we're only concerned with anyone having answered a question positively, we can take the set of all responses in a group. Doing so removes all duplicates, and we can reduce the count that remains into a rolling total.

On our flight, therefore, the cumulative responses by passengers totalled 6686.

Part 2

Triumphant and satisfied, we hand the completed documents to the attendant. Unfortunately, as it would happen, we weren't supposed to record the total number of questions that anyone in a group answered. Instead, the attendant informs us, they need the total number of questions that everyone in a group answered. Rats.

No problem our intrepid vacationer, though. Let's start again, using our solution to part one as the starting point.

forms.compactMap { form in /* ... */ }.reduce(0, +)

Like before, we're reducing the contents of an array of integers into a single, running total. We want to know which questions received answers from everybody in each group. To achieve this, we'll use the intersection of sets.

The intersection of two sets.

In the above Venn diagram, there are two sets A and B. In the centre of this diagram sits the intersection, A ∩ B, of these sets. Set intersection, as demonstrated above, enables us to determine which elements exist in both A and B. The same process works if we have many more sets, such as in our problem. How do we implement this in swift, then? It's remarkably straightforward.

form in form.reduce(Set(form.joined())) { result, element in
    result.intersection(Set(element))
}.count

The first step is to create a set of all responses in form. We can then use the reduce function to intersect the sets of each answer with the overarching set. Each time we do so, the number of items in the collection result will decrease by the number of things not also found in the set element.

The expanded variant of part one's solution yields a satisfactory answer. The count of cumulative responses, wherein all passengers in a group answered, is 3476.

Complete Code

Please give my github a look for todays solution!

Show Comments