Day21.scala

package sungkmi.aoc2020.day21

case class Ingredient(name: String) extends AnyVal
case class Allergen(name: String) extends AnyVal
type Food = (Set[Ingredient], Set[Allergen])
type Pair = (Allergen, Ingredient)

def parseLine(line: String): Food =
  val Array(f, e) = line `split` " \\(contains "
  val ingredients = (f `split` " ").toSet.map(Ingredient(_))
  val allergens = (e.init `split` ", ").toSet.map(Allergen(_))
  (ingredients, allergens)

def parse(s: String): Seq[Food] = s.split("\n").map(parseLine).toSeq

def allergenIngrediantCandidates(foods: Seq[Food])(allergen: Allergen): Set[Ingredient] =
  val allergenFoodIngredients = for
    (ingredients, allergens) <- foods if allergens `contains` allergen
  yield ingredients
  allergenFoodIngredients.reduceLeft(_ `intersect` _)

def step(foods: Seq[Food]): (Seq[Food], Seq[Pair]) =
  val allergens = foods.foldLeft(Set.empty[Allergen])(_ ++ _._2)
  val determinedPairs: Seq[Pair] = for
    allergen <- allergens.toSeq
    ingrediantCandidates = allergenIngrediantCandidates(foods)(allergen)
    if ingrediantCandidates.size == 1
  yield allergen -> ingrediantCandidates.head
  val foods1 = determinedPairs.foldLeft(foods):
    case (foods, (allergen, ingredient)) => foods.map:
      (ingredients, allergens) => (ingredients - ingredient, allergens - allergen)
  (foods1, determinedPairs)

def solve1(s: String): Int =
  def loop(foods: Seq[Food]): Seq[Food] =
    val (foods1, dangerous1) = step(foods)
    if dangerous1.isEmpty then foods else loop(foods1)
  loop(parse(s)).map(_._1.size).sum

def solve2(s: String): String =
  def loop(foods: Seq[Food], acc: List[Pair]): List[Pair] =
    val (foods1, dangerous1) = step(foods)
    if dangerous1.isEmpty then acc else loop(foods1, dangerous1.toList ::: acc)
  loop(parse(s), Nil).sortBy(_._1.name).map(_._2.name).mkString(",")

@main def part1: Unit =
  val ans = solve1(input)
  println(ans)

@main def part2: Unit = 
  val ans = solve2(input)
  println(ans)

//lazy val input: String = """vzkbf 

Day21Test.scala

package sungkmi.aoc2020.day21

class Day21Test extends munit.FunSuite {

  val testInput = """mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
trh fvjkl sbzzf mxmxvkd (contains dairy)
sqjhc fvjkl (contains soy)
sqjhc mxmxvkd sbzzf (contains fish)"""

  val foods = Seq(
    Set("mxmxvkd", "kfcds", "sqjhc", "nhms") -> Set("dairy", "fish"),
    Set("trh", "fvjkl", "sbzzf", "mxmxvkd") -> Set("dairy"),
    Set("sqjhc", "fvjkl") -> Set("soy"),
    Set("sqjhc", "mxmxvkd", "sbzzf") -> Set("fish"),
  ).map:
    case (ingredients, allergens) =>
      ingredients.map(Ingredient(_)) -> allergens.map(Allergen(_))

  test("day21 parse") {
    assertEquals(parse(testInput), foods)
  }

  test("day21 allergenIngrediantCandidates") {
    assertEquals(
      allergenIngrediantCandidates(foods)(Allergen("dairy")),
      Set(Ingredient("mxmxvkd"))
    )
  }

  test("day21 solve1") {
    assertEquals(solve1(testInput), 5)
  }

  test("day21 solve2") {
    assertEquals(solve2(testInput), "mxmxvkd,sqjhc,fvjkl")
  }
}