Advent of Code 2020 - Day 21

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

https://github.com/papey/aoc/commit/a730fc00747f565bb7d622a5c54f1cc11b7a5701

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

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)

https://github.com/camilleryr/advent20/blob/main/lib/day_21.ex

Here is my solution.

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

Ended up doing this one as well, so much for taking a break

My solution