Advent of Code 2020 Day 16

Part 1

As a colleague commented yesterday, one feature you really want in a language for solving AoC problems (or Kattis, etc) is rich string handling. Parsing the input is really part 0 of almost every problem. Sometimes it’s the hardest part - consider my Common Lisp solution for Day 14, where nearly half the code is dedicated to parsing input, including a (poor) split function. Julia rates pretty well here - strings are easily manipulated, and it has a decent library of string functions, including regular expressions. But I digress…

Today’s input is fairly complex, with several types of data represented, so I’m going to spend a bit of time developing some data structures to represent it: An enum to track state as we read through the input:

@enum InputState ticket_rules blank_line your_ticket nearby_ticket

An immutable struct to hold each rule, which I’m going to have represent a single range, i.e. class: 1-3 or 5-7 will become two rules class: 1-3 and class: 5-7 (I’ll probably regret this later):

struct Rule
    field::AbstractString
    range::AbstractRange{Int}
end

And a mutable struct to contain all the input data:

Ticket = Vector{Int}

mutable struct Input
    rules::Vector{Rule}
    ticket::Ticket
    others::Vector{Ticket}
end

Part 1 is pretty simple once the input is parsed:

    invalid = Ticket()
    for tx in inp.others
        inv = filter(x->!any([(x in y.range) for y in inp.rules]), tx)
        invalid = [invalid; inv]
    end

Part 2

I’ll start (after filtering out bad records) with a function that builds a list of which fields’ rules each field in the other tickets are within:

    for tx in inp.others
        fields = [map(x->x.field, filter(x->(f in x.range), inp.rules)) for f in tx]
        @debug "possible fields" tx fields
    end

This immediately gives me some bad, but expected, news: this will not be simply finding the one possible field that all the tickets match; instead some deductive reasoning is required:

┌ Debug: possible fields
│   tx =
│    3-element Array{Int64,1}:
│      3
│      9
│     18
│   fields =
│    3-element Array{Array{SubString{String},1},1}:
│     ["row", "seat"]
│     ["class", "row", "seat"]
│     ["class", "row", "seat"]
└ @ Main ~/p/aoc20/day16.jl:124
┌ Debug: possible fields
│   tx =
│    3-element Array{Int64,1}:
│     15
│      1
│      5
│   fields =
│    3-element Array{Array{SubString{String},1},1}:
│     ["class", "row"]
│     ["class", "row", "seat"]
│     ["class", "row", "seat"]
└ @ Main ~/p/aoc20/day16.jl:124
┌ Debug: possible fields
│   tx =
│    3-element Array{Int64,1}:
│      5
│     14
│      9
│   fields =
│    3-element Array{Array{SubString{String},1},1}:
│     ["class", "row", "seat"]
│     ["class", "row"]
│     ["class", "row", "seat"]
└ @ Main ~/p/aoc20/day16.jl:124

We can arrive at the solution via the following:

1. The second ticket shows that the first field cannot be “seat,” and the third ticket shows that the second field cannot be “seat” either, so the third field must be “seat.”
2. Removing “seat” from the other fields, we see that only option left for the first field in the first ticket is “row.”
3. Therefore “class” must be the second field.

So we can generalize these into three rules:

1. If we’ve eliminated all but one possibility for a location, assign that field to that location and remove it from all other locations.
2. If there’s only one location that has a field among its possibilities, assign that field to that location and remove the other possibiities.
3. If there’s only one location left unknown, assign the remaining unassigned field to that location.

We need to repeatedly apply these two rules, removing “known” fields as they are discovered, until all fields are known. To do this I’m going to use Sets for each field, initially filling then with all fields then intersecting them with the possible fields from applying the rules to each ticket.

allfields = Set(map(x->x.field, inp.rules))
pos = [copy(allfields) for _ in inp.ticket]
known = ["" for _ in inp.ticket]

First I’ll remove from the possibilites for each location any fields whose rules are broken by the known values in that location (or, more accurately, keep fields that are within the rules):

for tx in inp.others
    for i in 1:length(tx)
        pos[i] = pos[i] ∩ Set(map(x->x.field, filter(x->(tx[i] in x.range), inp.rules)))
    end
end

Then we look for any locations that only have one possibility, and remove that possibility from all locations:

for i in 1:length(pos)
    if length(pos[i])==1
        known[i] = first(pos[i])
        for j in 1:length(pos)
            setdiff!(pos[j],pos[i])
        end
    end
end

Then any field that is only possible in one location, and clear out the other possibilities in that location:

for f in allfields
    if count(x->(f in x), pos) == 1
        i = findfirst(x->(f in x), pos)
        known[i] = f
        pos[i] = Set()
    end
end

And finally check if there’s only one location left unknown:

if count(isempty, known) == 1
    last = first(setdiff(allfields, Set(filter(!isempty, known))))
    known[findfirst(isempty, known)] = last
end

Well, this gets us through the test case, but not the problem! I only get five fields output, and looking at the debug output see that one field got assigned to two locations:

["wagon", "route", "arrival platform", "departure track", "departure time", "row", 
"arrival location", "seat", "train", "arrival track", "type", "zone", 
"departure station", "class", "departure location", "departure date", 
"arrival station", "arrival station", "duration", "price"]

How did that happen? Looking through the debug logs, I see that first “arrival station” was assigned to location 17 since it was the only possibility there, yet it remained in other locations - so setdiff!(pos[j],pos[i]) must not be working as I expected. Aha, pos[i] is a Set (albeit with only one element), while I just want the field name, which is known[i].