Advent of Code 2020 - Day 16

Just solved part 1. I find the code not elegant but it did give me a star.

https://github.com/code-shoily/advent_of_code/blob/master/lib/2020/day_16.ex

Takes ~9s for part two, can be optimized further I guess.
EDIT: fixed, now it takes 0.4s

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)

Here is my solution.

My solution.

Used a comprehension to generate a list of all valid fields for each index and then reducing that. Will try to revisit this part later though and see how it can be improved.

Me too ! we arrive pretty much at the same conclusion

My strategy is to find all possible field names for each column. If a column has only 1 candidate field, then that field name of that column is taken and set to that column. Then I look at the columns that have 2 candidate fields. Subtract the candidate fields by the already taken fields, and I get more fields set. Then I look at the columns with 3 candidate fields, and then those with 4 candidate fields, so on and so forth.

#!/usr/bin/env elixir

to_range = fn str ->
  str
  |> String.split("-")
  |> Enum.map(&String.to_integer/1)
  |> (fn[a, b]-> a..b end).()
end

parse_rule = fn line ->
  [field_name | ranges] = Regex.scan(~r/^([^:]+): (\d+-\d+) or (\d+-\d+)$/, line, capture: :all_but_first)
                          |> List.flatten()
  {field_name, Enum.map(ranges, to_range)}
end

rules = "day16-rules.txt"
        |> File.stream!()
        |> Enum.map(parse_rule)
        |> Map.new()

rule_values = Map.values(rules)

invalid? = &Enum.all?(rule_values, fn [rule1, rule2] -> &1 not in rule1 and &1 not in rule2 end)

transpose = fn matrix -> 
  matrix
  |> Enum.zip()
  |> Enum.map(&Tuple.to_list/1)
end

valid_tickets = "day16-nearby-tickets.txt"
                |> File.stream!()
                |> Stream.map(&String.trim/1)
                |> Stream.map(&String.split(&1, ","))
                |> Stream.map(&Enum.map(&1, fn s -> String.to_integer(s) end))
                |> Enum.reject(&Enum.any?(&1, invalid?))
                |> transpose.()

in_any_range? = fn value, ranges ->
  Enum.any?(ranges, & value in &1)
end

find_all_candidate_fields = fn values ->
  rules
  |> Enum.filter(fn{_field_name, ranges}-> 
    Enum.all?(values, fn v -> in_any_range?.(v, ranges) end)
  end)
  |> Enum.map(&elem(&1, 0))
  |> MapSet.new()
end

fields = valid_tickets
         |> Enum.map(find_all_candidate_fields)
         |> Enum.with_index()
         |> Enum.sort_by(&MapSet.size(elem(&1, 0)))
         |> (fn ls -> [{MapSet.new(), -1} | ls] end).()
         |> Enum.chunk_every(2, 1, :discard)
         |> Enum.reduce({[], MapSet.new()}, fn [{fs1, _i1}, {fs2, i2}], {acc, seen} ->
           seen = MapSet.union(seen, fs1)
           [f] = fs2 |> MapSet.difference(seen) |> MapSet.to_list()
           {[{f, i2} | acc], seen}
         end)
         |> elem(0)
         |> Enum.sort_by(&elem(&1, 1))
         |> Enum.map(&elem(&1, 0))

File.read!("day16-my-ticket.txt")
|> String.trim()
|> String.split(",")
|> Enum.map(&String.to_integer/1)
|> Enum.zip(possible_fields)
|> Enum.filter(fn {_value, field_name} -> String.starts_with?(field_name, "departure") end)
|> Enum.map(&elem(&1, 0))
|> Enum.reduce(&*/2)
|> IO.inspect()

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.

My code for today

Part1 / Part2

I really struggled with Part2

I first tried a brute force recursion approach which timed-out, then I trashed all my code and went for another approach which returns the proper result in 20ms.