Advent of Code 2020 - Day 16

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

In this puzzle we have a bunch of items, each represented as a sequence of numbers. There are some fields, with constraints on the values that they can take, and we need to eventually identify which filed corresponds to each position in the sequence.

The input is not difficult to parse, but it needs to be done in stages:

1. The field rules, first splitting field from the ranges, then interpreting the ranges. One field per line, until a blank line is reached
2. The item we will use to validate (your ticket, per the problem description), a sequence of comma-separated ints.
3. The rest of items to be used for deducing the positions of the fields, a sequence like that in (2) per line.

Part 1

To begin with, we need to identify items with values that do not match any of the fields. We will create a valid_fields function that, given a number, returns the sets for which it is valid. We do this in validity, using the parsed filed rules from the input. validity returns the valid_fileds function.

The function itself is quite simple: take the number, and check for each field rule if it is within the corresponding interval(s); if so, that field goes into the returned set, otherwise it doesn't. This is readily expressed as a set comprehension, using any to iterate over potentially multiple intervals.

We can identify the invalid values, as they result in the empty set when run through this function.

Part 2

Now it's time to actually find out the positions of the fields. We will apply a form of constraint propagation, or elimination. We start with a set of feasible fields for each position, which includes all fields, then eliminate the possibilities that are not valid for some ticket.

For each item, we take the value in each position, and remove form the feasible fields for that position the fields for which the value is not valid, or conversely, we keep the intersection of feasible and valid. We need to be careful to check that the set of valid fields is not empty (we know there are invalid tickets from part 1), or alternatively we can eliminate the invalid tickets in a preprocessing pass.

We now have all the information contained in the items themselves encoded in the feasible sets. To finish, we need to apply and propagate a new constraint, one that is somewhat implicit: there is a one-to-one relationship between positions and fields.

In practice, we will keep track of all the positions that have been determined, i.e. they have a single field that is possible for them. We iterate over the positions, and add it to the determined set if there is a single feasible field or remove the determined fields from the feasible ones. We do this until all positions are determined.

Once we know which field is which, we can answer the question of multiplying the values in 'my ticket' for specific fields (those starting with 'departure').