This topic is about Day 21 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
Today was quick and easy, thanks to MapSet
defmodule Aoe.Y20.Day21 do
alias Aoe.Input, warn: false
@type input_path :: binary
@type file :: input_path | %Aoe.Input.FakeFile{}
@type part :: :part_one | :part_two
@type input :: binary | File.Stream.t()
@type problem :: any
@spec read_file!(file, part) :: input
def read_file!(file, _part) do
Input.stream_file_lines(file, trim: true)
end
@spec parse_input!(input, part) :: problem
def parse_input!(input, _part) do
input
|> Stream.map(&parse_line/1)
end
defp parse_line(line) do
[ingredients, allergens] = String.split(line, " (contains ")
ingredients =
ingredients
|> String.split(" ")
allergens =
allergens
|> String.replace(")", "")
|> String.split(", ")
{ingredients, allergens}
end
defp initial_data(problem) do
allergens2containers =
problem
|> Enum.reduce(%{}, fn {ingredients, allergens}, acc ->
Enum.reduce(allergens, acc, fn alg, acc ->
ingredients_set = MapSet.new(ingredients)
Map.update(acc, alg, ingredients_set, &MapSet.intersection(&1, ingredients_set))
end)
end)
possible_containers =
allergens2containers
|> Enum.reduce(MapSet.new(), fn {_alg, ingrs}, acc ->
MapSet.union(acc, ingrs)
end)
all_ingredients =
problem
|> Enum.reduce(MapSet.new(), fn {ingredients, _}, acc ->
MapSet.union(acc, MapSet.new(ingredients))
end)
no_allergens = MapSet.difference(all_ingredients, possible_containers)
{allergens2containers, no_allergens}
end
def part_one(problem) do
{allergens2containers, no_allergens} = initial_data(problem)
count_occurences =
problem
|> Enum.reduce(0, fn {ingredients, _}, acc ->
Enum.reduce(ingredients, acc, fn ingr, acc ->
if MapSet.member?(no_allergens, ingr) do
acc + 1
else
acc
end
end)
end)
end
def part_two(problem) do
{allergens2containers, no_allergens} = initial_data(problem)
allergens2containers = remove_safes(MapSet.to_list(no_allergens), allergens2containers)
match_to_ingrs(allergens2containers, [])
end
defp match_to_ingrs(allergens2containers, acc) do
case Enum.find(allergens2containers, fn {alg, iset} -> MapSet.size(iset) == 1 end) do
{alg, iset} ->
[ingr] = MapSet.to_list(iset)
acc = [{alg, ingr} | acc]
allergens2containers =
allergens2containers
|> remove_for_all(ingr)
|> Map.delete(alg)
match_to_ingrs(allergens2containers, acc)
nil ->
acc
|> Enum.sort()
|> Keyword.values()
|> Enum.join(",")
end
end
defp remove_safes([safe | ingrs], allergens2containers) do
remove_safes(ingrs, remove_for_all(allergens2containers, allergens2containers))
end
defp remove_safes([], allergens2containers) do
allergens2containers
end
defp remove_for_all(allergens2containers, ingr) do
Enum.map(allergens2containers, fn {alg, iset} -> {alg, MapSet.delete(iset, ingr)} end)
|> Map.new()
end
end
Yep, mine is a bit verbose maybe but it works so 
1 Like
After the slaughter that is day 20 (which I did solve, but with a sprawling 163 sloc solution 
), this was a good detox, and I got to even reuse day 16’s logic a bit too…
I ‘accidentally’ created the relevant map for day 2 while solving for day 1, and the day 16 reuse is for the part where we have a map of values with increasing lengths, so we just need to sort by that and start picking out the correct value for the key.
defmodule AdventOfCode.Day21 do
@moduledoc "Day 21"
defmodule Food do
defstruct ingredients: MapSet.new(), allergens: MapSet.new()
end
defp parse(food) do
to_set = &(MapSet.new(String.split(&1, &2)))
[_, ingredients, allergens] = Regex.run(~r/^(.*) \(contains (.*)\)$/, food)
%Food{ingredients: to_set.(ingredients, " "), allergens: to_set.(allergens, ", ")}
end
defp process(input) do
all_food = Enum.map(input, &parse/1)
by_allergen = Map.new(
Enum.reduce(all_food, MapSet.new(), &(MapSet.union(&1.allergens, &2))),
fn allergen ->
case Enum.filter(all_food, &(allergen in &1.allergens)) do
[] -> {allergen, []}
x -> {allergen, Enum.reduce(tl(x), hd(x).ingredients, &(MapSet.intersection(&1.ingredients, &2)))}
end
end
)
{all_food, by_allergen}
end
def part1(input) do
{all_food, by_allergen} = process(input)
bad = MapSet.new(Enum.flat_map(by_allergen, &(elem(&1, 1))))
Enum.sum(Enum.map(all_food, fn food -> Enum.count(Enum.filter(food.ingredients, &(!(&1 in bad)))) end))
end
def part2(input) do
{_, by_allergen} = process(input)
Enum.reduce(
Enum.sort_by(by_allergen, &(Enum.count(elem(&1, 1)))),
Map.new(),
fn {allergen, ingredients}, acc -> Map.put(acc, hd(MapSet.to_list(ingredients) -- Map.keys(acc)), allergen) end
)
|> Enum.sort_by(&(elem(&1, 1)))
|> Enum.map(&(elem(&1, 0)))
|> Enum.join(",")
end
end
2 Likes
This would have been easy, got the algorithm right faster than other days. But, I made a small mistake, I used Map.new on a list of {allergen, items} where I should not have, there were duplicate allergen and the Map conversion kept on showing me a few ingredients less. I did the error in processing the input, not in the actual algorithms 
defmodule AdventOfCode.Y2020.Day21 do
use AdventOfCode.Helpers.InputReader, year: 2020, day: 21
def run_1 do
foods = process(input!())
allergens = allergens(foods)
length(Enum.reject(ingredients(foods), &(&1 in allergens)))
end
def run_2, do: input!() |> process() |> build() |> evolve() |> sort()
def process(input), do: Enum.map(String.split(input, "\n"), &parse/1)
defp ingredients(foods), do: Enum.flat_map(foods, &elem(&1, 1))
defp sort(allergens), do: Enum.map_join(allergens, ",", &hd(MapSet.to_list(elem(&1, 1))))
def parse(%{"items" => items, "allergens" => allergens}),
do: {String.split(allergens, ", "), String.split(items, " ")}
@regex ~r/^(?<items>.+) \(contains (?<allergens>.+)\)$/
def parse(line), do: parse(Regex.named_captures(@regex, line))
defp build(foods) do
Enum.reduce(foods, %{}, fn {allergens, items}, acc ->
items = MapSet.new(items)
Enum.reduce(allergens, acc, fn allergen, acc ->
Map.update(acc, allergen, [items], &[items | &1])
end)
end)
|> Enum.map(fn {k, v} -> {k, intersections(v)} end)
|> Enum.into(%{})
end
defp allergens(foods), do: build(foods) |> Map.values() |> unions()
defp intersections(items), do: Enum.reduce(items, &MapSet.intersection/2)
defp unions(items), do: Enum.reduce(items, &MapSet.union/2)
defp evolve(allergen), do: evolve(allergen, %{})
defp evolve(allergen, result) when map_size(allergen) == map_size(result), do: result
defp evolve(allergen, result) do
result =
Map.merge(result, Map.new(Enum.filter(allergen, fn {_, v} -> Enum.count(v) == 1 end)))
found = unions(Map.values(result))
allergen
|> Enum.map(fn {k, v} -> {k, (Enum.count(v) == 1 && v) || MapSet.difference(v, found)} end)
|> Enum.into(%{})
|> evolve(result)
end
end
What a difference a day makes - also went with MapSet - think there are probably ways to optimize parts of this, but after yesterday Im happy to have something that came together nice and quick. Even got the rare feeling of pretty much having solved part 2 because of the way I implemented part 1.
I did find it novel to get to use ~w for parsing the list ingredient list in my parser - don’t think I would ever really use it, but it was kind of fun
input
|> String.split("\n", trim: true)
|> Enum.map(fn line ->
[words, alergens] = String.split(line, ["(contains ", ")"], trim: true)
{~w/#{words}/, String.split(alergens, ", ")}
end)
Oh, man, that was refreshingly easy. Days 19 and 20 definitely took a toll so this was sanity restoring.
defmodule Day21 do
def part_1 do
food = load()
allergens = food |> Enum.map(&(elem(&1, 1))) |> Enum.reduce(&MapSet.union/2)
mapping = allergens
|> Enum.map(&(find_options(&1, food)))
|> find_words(%{})
words = Map.values(mapping)
food
|> Enum.flat_map(fn {words, _} -> words end)
|> Enum.count(&(&1 not in words))
end
def part_2 do
food = load()
allergens = food |> Enum.map(&(elem(&1, 1))) |> Enum.reduce(&MapSet.union/2)
allergens
|> Enum.map(&(find_options(&1, food)))
|> find_words(%{})
|> Enum.sort(fn {a1, _}, {a2, _} -> a1 < a2 end)
|> Enum.map(&(elem(&1, 1)))
|> Enum.join(",")
end
def find_words([], mapping), do: mapping
def find_words(options=[{allergen, opts}|rest], mapping) do
if Enum.count(opts) > 1 do
options |> Enum.sort(&sorter/2) |> find_words(mapping)
else
[word] = Enum.take(opts, 1)
rest = Enum.map(rest, fn {a, opts} -> {a, MapSet.delete(opts, word)} end)
mapping = Map.put(mapping, allergen, word)
find_words(rest, mapping)
end
end
def sorter({_, o1}, {_, o2}), do: Enum.count(o1) < Enum.count(o2)
def find_options(allergen, food) do
words = food |> Enum.map(&(elem(&1, 0))) |> Enum.reduce(&MapSet.union/2)
options = Enum.reduce(food, words, fn
{words, allergens}, options ->
if MapSet.member?(allergens, allergen) do
MapSet.intersection(words, options)
else
options
end
end)
{allergen, options}
end
def load, do: File.read!("day-21.input") |> parse()
def parse(lines) do
lines
|> String.split("\n")
|> Enum.map(&parse_ingredients/1)
end
def parse_ingredients(line) do
{unknown, allergens} = line
|> String.replace([",", "(", ")"], "")
|> String.split(" ", trim: true)
|> Enum.split_while(&(&1 != "contains"))
allergens = allergens |> List.delete("contains") |> MapSet.new()
{MapSet.new(unknown), allergens}
end
end
