AoC 2020 D16: Ticket Translation

Python | Problem statement | Source code | Tags: Constraint satisfaction

← Previous Back to AoC Index Next →

Part 1

Part 1 is straightforward: collect a list of ranges, then for each number in each nearby ticket, check if it falls into any of the ranges.

Part 2

We have a list of sets of values, and we want to find an assignment of the fields such that each set only contains values from the field's range. The first step is to check which fields are possible for each set. For each set, we iterate through all fields and check if all values in the set fall into the range.

candidate_fields = {i: set(rules.keys()) for i in range(len(valid_tickets[0]))}
for ticket in valid_tickets:
    for i, value in enumerate(ticket):
        impossible_fields = set(
            field
            for field in candidate_fields[i]
            if all(
                value < min_val or value > max_val
                for min_val, max_val in rules[field]
            )
        )
        candidate_fields[i] -= impossible_fields
python

Like in any constraint satisfaction problem, once we have the initial candidates, we can propagate constraints. We start with the narrowest constraints, satisfy them, and remove that possibility from all other sets. We repeat this until all sets are satisfied.

If we print candidate_fields, it looks like this:

{
    14: {'type'},
    12: {'type', 'class'},
    15: {'type', 'arrival location', 'class'},
    0: {'type', 'zone', 'arrival location', 'class'},
    11: {'arrival station', 'type', 'zone', 'arrival location', 'class'},
    ...
}
py

It turns out that this problem is very nice: it doesn't even need backtracking. Each step is always deterministic because there's always a constraint with only one possibility. So the field assignments can be found with a simple loop, by sorting the candidate sets by size and removing already-assigned fields from subsequent sets.

figured_out = set[str]()
for i, s in sorted(candidate_fields.items(), key=lambda x: len(x[1])):
    s.difference_update(figured_out)
    assert len(s) == 1
    figured_out = s.union(figured_out)
fields: list[str] = []
for s in candidate_fields.values():
    fields.append(s.pop())
python

← Previous Back to AoC Index Next →