Was a bit worried that my answer was quite complex, with multiple maps, transposing, tracking seen values, and nlogn filtering, but it seems that’s what everyone else did too.

I need to focus on work for the next couple of weeks, so I’ll only be looking at the remaining problems on days off from now on.

Enum.zip to transpose. Wish I’d thought of that.

Also: I thought -- was much nicer than MapSet.difference. I was willing to accept a performance hit for the increased simplicity, but apparent it actually performs better since OTP 22:

As of Erlang/OTP 22, this operation is significantly faster even if both lists are very long, and using --/2 is usually faster and uses less memory than using the MapSet-based alternative mentioned above.

I’m kind of surprised that I can just ‘chain’ my valid tickets eventually into a nice map of keys to column indices (e.g. "row" => 1)…

Explanation:

1. Get valid tickets
2. Pivot them so that you get a map of column indices to all the values of that column
3. Map that to a tuple {col, matches} where matches is a list of possible keys
4. Sort by the count of matches (almost there)
5. Reduce to another map, this time keyed by the key with the column index as the value
6. Filter for map entries where the key starts with "departure"
7. Perform the final reduction by multiplication

    # snippet only
    {rules, own, nearby} = process(input)
    Enum.filter(nearby, &(elem(&1, 1) == []))
    |> Enum.map(fn {ticket, _} -> Map.new(Enum.with_index(ticket), fn {n, index} -> {index, [n]} end) end)
    |> Enum.reduce(&(Map.merge(&1, &2, fn _, v1, v2 -> v1 ++ v2 end)))
    |> Enum.map(
         fn {col, values} ->
           {col, Enum.map(Enum.filter(rules, fn {_, valid?} -> Enum.all?(values, valid?) end), &(elem(&1, 0)))}
         end
       )
    |> Enum.sort_by(&(length(elem(&1, 1))))
    |> Enum.reduce(Map.new(), fn {col, matches}, acc -> Map.put(acc, hd(matches -- Map.keys(acc)), col) end)
    |> Enum.filter(fn {key, _} -> String.starts_with?(key, "departure") end)
    |> Enum.reduce(1, fn {_, col}, acc -> Enum.at(own, col) * acc end)

I did something different today by using nimble_parsec to parse the input data. But otherwise especially part 2 feels like awkwardly procedural. I could make it work, but it’s just an unnerving amount of nested iterations over lists.