This topic is about Day 16 of the Advent of Code 2020 .
Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276
The join code is:
39276-eeb74f9a
Just solved part 1. I find the code not elegant but it did give me a star.
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:
- Get valid tickets
- Pivot them so that you get a map of column indices to all the values of that column
- Map that to a tuple
{col, matches}wherematchesis a list of possible keys - Sort by the count of
matches(almost there) - Reduce to another map, this time keyed by the key with the column index as the value
- Filter for map entries where the key starts with
"departure" - 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)
1 Like
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.
3 Likes
Enum.zip to transpose. Wish Iād thought of that.
3 Likes
My code for today 
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.
I only made this code longer because I had not the leisure to make it shorter. cough
defmodule Day16 do
def readinput() do
[labelranges, myticket, nearbytickets] =
File.read!("16.input.txt")
|> String.split("\n\n")
|> Enum.map(&String.split(&1, "\n", trim: true))
# my ticket and nearby ticket sections starts with a header string
# use tl() to skip that
[
ranges(labelranges),
ticketsplit(List.last(myticket)),
Enum.map(tl(nearbytickets), &ticketsplit/1)
]
end
@doc """
Takes a list of strings like
["class: 1-3 or 5-7", "row: 6-11 or 33-44", "seat: 13-40 or 45-50"]
and returns a dictionary of string keys, list of ranges values
%{
"class" => [1..3, 5..7],
"row" => [6..11, 33..44],
"seat" => [13..40, 45..50]
},
"""
def ranges(labels) do
labels
|> Enum.map(fn rule ->
[label, r1start, r1end, r2start, r2end] =
Regex.run(~r/(.*): (\d+)-(\d+) or (\d+)-(\d+)/, rule, capture: :all_but_first)
{label,
[
String.to_integer(r1start)..String.to_integer(r1end),
String.to_integer(r2start)..String.to_integer(r2end)
]}
end)
|> Map.new()
end
@doc """
Splits a comma-separated list of numbers as a string and
returns a list of numbers.
"""
def ticketsplit(ticket) do
String.split(ticket, ",")
|> Enum.map(&String.to_integer/1)
end
def part1([rangemap, _, nearbytickets] \\ readinput()) do
allranges = Map.values(rangemap) |> List.flatten()
Enum.flat_map(nearbytickets, fn ticket ->
Enum.reject(ticket, fn field ->
Enum.any?(allranges, fn range ->
field in range
end)
end)
end)
|> Enum.sum()
end
################ part 2 ################
def part2([rangemap, myticket, nearbytickets] \\ readinput()) do
allranges = Map.values(rangemap) |> List.flatten()
validtickets =
Enum.filter(nearbytickets, fn ticket ->
length(ticket) ==
Enum.filter(ticket, fn field ->
Enum.any?(allranges, fn range ->
field in range
end)
end)
|> Enum.count()
end)
|> Enum.map(&fieldtolabel(&1, rangemap))
numtickets = length(validtickets)
# labels starting with "departure"
departuresidx =
process(validtickets, numtickets)
|> Enum.reduce([], fn {idx, label}, acc ->
if String.starts_with?(label, "departure"), do: [idx | acc], else: acc
end)
# finally, calculate the product of the departure fields in my ticket
myticket
|> Enum.with_index()
|> Enum.reduce(1, fn {val, idx}, acc ->
if idx in departuresidx, do: acc * val, else: acc
end)
end
@doc """
Take a list of tickets and return a list of matching labels against
each ticket item. Find the matching labels by checking every item in
each ticket with the label ranges.
"""
def fieldtolabel(ticket, rangemap, result \\ [])
def fieldtolabel([], _, result), do: Enum.reverse(result)
def fieldtolabel([t | ticket], rangemap, result) do
labels =
Enum.filter(rangemap, fn {_label, [r1, r2]} ->
t in r1 or t in r2
end)
|> Enum.map(fn {k, _v} -> k end)
fieldtolabel(ticket, rangemap, [labels | result])
end
@doc """
Take something like
[
[["row", "seat"], ["class", "row", "seat"], ["class", "row", "seat"]],
[["class", "row"], ["class", "row", "seat"], ["class", "row", "seat"]],
[["class", "row", "seat"], ["class", "row"], ["class", "row", "seat"]]
]
and rotate it so the first column becomes the first row, etc. Then, flatten the
list:
[["row", "seat"], ["class", "row"], ["class", "row", "seat"]]
[["class", "row", "seat"], ["class", "row", "seat"], ["class", "row"]]
[["class", "row", "seat"], ["class", "row", "seat"], ["class", "row", "seat"]]
=>
["row", "seat", "class", "row", "class", "row", "seat"]
["class", "row", "seat", "class", "row", "seat", "class", "row"]
["class", "row", "seat", "class", "row", "seat", "class", "row", "seat"]
Calculate the frequency of each item in each row, and filter out all
items that do not show up in all of the original table's columns.
We are left with the common fields.
[["row"], ["class", "row"], ["class", "row", "seat"]]
"""
def process(validtickets, numtickets) do
bycolumn =
for c <- 0..(length(List.first(validtickets)) - 1) do
for r <- 0..(numtickets - 1) do
Enum.at(validtickets, r) |> Enum.at(c)
end
|> List.flatten()
|> Enum.frequencies()
|> Enum.filter(fn {_k, v} -> v == numtickets end)
|> Enum.map(fn {k, _v} -> k end)
end
|> Enum.with_index()
# take something like [{["seat"], 0}]
# and convert it to %{0 => "seat"}
# "seat" is the common field in the first item of each row of validtickets
colmap =
bycolumn
|> Enum.filter(fn {ks, _c} -> length(ks) == 1 end)
|> Enum.reduce(%{}, fn {k, c}, acc -> Map.put(acc, c, List.first(k)) end)
loop(colmap, bycolumn)
end
@doc """
Loop until each column in bycolumn has one label
"""
def loop(colmap, bycolumn) do
if Enum.all?(bycolumn, fn {ks, _c} -> length(ks) == 1 end) do
colmap
else
bycolumn =
Enum.map(bycolumn, fn {ks, c} ->
if length(ks) == 1 do
{ks, c}
else
{MapSet.new(ks)
|> MapSet.difference(MapSet.new(Map.values(colmap)))
|> MapSet.to_list(), c}
end
end)
colmap =
bycolumn
|> Enum.filter(fn {ks, _c} -> length(ks) == 1 end)
|> Enum.reduce(%{}, fn {k, c}, acc -> Map.put(acc, c, List.first(k)) end)
loop(colmap, bycolumn)
end
end
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.
1 Like
So much iterationā¦
Today I didnāt have much time to work on this so my solution isnāt very refined (please nobody look at my parsing function); however it gets the job done reasonably fast.
defmodule AdventOfCode.Day16 do
def part1(input) do
{fields, _my_ticket, tickets} = parse_input(input)
Enum.reduce(tickets, 0, fn ticket, total ->
ticket
|> Enum.map(fn ticket_field ->
case Enum.find(fields, fn {_, r1, r2} -> ticket_field in r1 or ticket_field in r2 end) do
nil -> ticket_field
_range -> 0
end
end)
|> Enum.sum()
|> Kernel.+(total)
end)
end
def part2(input) do
{fields, my_ticket, tickets} = parse_input(input)
# this mega-pipe should be split in different functions for better testability...
# find the valid tickets
Enum.reduce([my_ticket | tickets], [], fn ticket, valid_tickets ->
ticket
|> Enum.map(fn ticket_field ->
case Enum.find(fields, fn {_, r1, r2} -> ticket_field in r1 or ticket_field in r2 end) do
nil -> false
_range -> true
end
end)
|> Enum.all?(& &1)
|> if(do: [ticket | valid_tickets], else: valid_tickets)
end)
# zip all the valid tickets into columns
|> Enum.zip()
|> Enum.map(&Tuple.to_list/1)
|> Enum.with_index()
|> Enum.map(fn {col, col_i} ->
plaus =
Enum.reduce(fields, [], fn {label, r1, r2}, plausible ->
if Enum.all?(col, fn f -> f in r1 or f in r2 end),
do: [label | plausible],
else: plausible
end)
{plaus, col_i}
end)
# find the correct field for each column
|> Enum.sort(fn {p1, _}, {p2, _} -> length(p1) < length(p2) end)
|> Enum.reduce(%{}, fn {plaus, i}, assigned ->
Enum.reduce_while(plaus, assigned, fn p, ass ->
if Map.has_key?(ass, p), do: {:cont, ass}, else: {:halt, Map.put(ass, p, i)}
end)
end)
|> Enum.filter(fn {k, _v} -> String.starts_with?(k, "departure") end)
|> Enum.map(fn {_k, v} -> Enum.at(my_ticket, v) end)
|> Enum.reduce(&Kernel.*/2)
end
def parse_input(input) do
# this parser function is disgusting, maybe refactor with nimbleparsec
[fields, my_ticket, tickets] = String.split(input, "\n\n", trim: true)
fields =
fields
|> String.split("\n", trim: true)
|> Enum.map(fn line ->
[label, ranges] = String.split(line, ": ")
[r1, r2] = String.split(ranges, " or ")
[r1a, r1b] = String.split(r1, "-")
[r2a, r2b] = String.split(r2, "-")
{label, String.to_integer(r1a)..String.to_integer(r1b),
String.to_integer(r2a)..String.to_integer(r2b)}
end)
[_, my_ticket] = String.split(my_ticket, "\n", trim: true)
my_ticket = my_ticket |> String.split(",") |> Enum.map(&String.to_integer/1)
[_ | tickets] = String.split(tickets, "\n", trim: true)
tickets =
tickets |> Enum.map(fn t -> t |> String.split(",") |> Enum.map(&String.to_integer/1) end)
{fields, my_ticket, tickets}
end
end
My solution uses MapSets of all possible values for each field, and MapSet.member? to test validity. Maybe not the most efficient way, but it still runs very fast. With ticket indexes 0 to 19, I used a Reduce to check each index and save the results, then another Reduce on my ticket to get the product of the appropriate indexes.
Refactored my answer to remove almost all usages of Map and MapSet in favour of lists. I also stole @Aetherusā Enum.zip idea for transpose. Much happier with it now. Here it is without the input parsing:
def run do
{rules, my_ticket, tickets} = File.read!("input") |> parse_input()
tickets
|> Enum.filter(&valid?(&1, rules))
|> transpose_tickets()
|> valid_fields_for_columns(rules)
|> reduce_to_column_by_field_name()
|> Stream.filter(&match?({"departure" <> _, _idx}, &1))
|> Stream.map(fn {_name, idx} -> my_ticket[idx] end)
|> Enum.reduce(&Kernel.*/2)
|> IO.puts()
end
def valid?(ticket, rules) do
Enum.all?(ticket, fn field ->
Enum.any?(rules, fn {_name, {range1, range2}} -> field in range1 || field in range2 end)
end)
end
def transpose_tickets(tickets) do
tickets |> Enum.zip() |> Enum.map(&Tuple.to_list/1) |> Enum.with_index()
end
# Compare each column against the rules to determine the list of fields each column satisfies
def valid_fields_for_columns(transposed_tickets, rules) do
for {column, idx} <- transposed_tickets, do: {idx, valid_fields_for(column, rules)}
end
# Reduce the list of valid fields by elimination.
# The number of valid fields for each column is unique, which doesn't seem like a coincidence.
# Start with the column that only has one possible valid field, mark the field as seen.
# Continue to the column with two valid fields, subtract the seen field, mark remaining field as seen.
# Repeat for all columns.
def reduce_to_column_by_field_name(valid_fields_by_column) do
valid_fields_by_column
|> Enum.sort_by(fn {_k, v} -> length(v) end)
|> Enum.map_reduce([], fn {col, fields}, seen ->
[field] = fields -- seen
{{field, col}, [field | seen]}
end)
|> elem(0)
end
def valid_fields_for(column, rules) do
Enum.filter(rules, fn {_field, {range1, range2}} ->
Enum.all?(column, fn val -> val in range1 || val in range2 end)
end)
|> Enum.map(&elem(&1, 0))
end
Happy to be stolen from 
Iām not very happy with my solution either. I found that Enum.chunk_every(2, 1, :discard) is useless in my solution.
What is the benefit of using Lists over Map/Set? Is āinā faster than āmember?ā ?
