# Advent of Code 2020 - Day 16

This topic is about Day 16 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:

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:

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)
``````
1 Like

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.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))

|> 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
[labelranges, myticket, nearbytickets] =
|> 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

Didnāt take the time to clean this up since I wanted breakfast, but it came out okay.

Day16

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.

Day 16

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?ā ?