Solve 2020 day 21 part 2

sim642 · sim642 · commit c142072abfff · 2020-12-21T08:38:53.000+02:00
diff --git a/src/main/scala/eu/sim642/adventofcode2020/Day21.scala b/src/main/scala/eu/sim642/adventofcode2020/Day21.scala
@@ -1,5 +1,7 @@
 package eu.sim642.adventofcode2020
 
+import eu.sim642.adventofcodelib.IteratorImplicits._
+
 object Day21 {
 
   case class Food(ingredients: Set[String], allergens: Set[String])
@@ -26,6 +28,36 @@ object Day21 {
       .sum
   }
 
+  def solveAllergenIngredients(foods: Seq[Food]): Map[String, String] = {
+
+    def helper(allergenIngredients: Map[String, Set[String]]): Iterator[Map[String, String]] = {
+      if (allergenIngredients.isEmpty)
+        Iterator(Map.empty)
+      else {
+        val (allergen, ingredients) = allergenIngredients.head
+        val newAllergenIngredients = allergenIngredients - allergen
+        for {
+          ingredient <- ingredients.iterator
+          newAllergenIngredients2 = newAllergenIngredients.view.mapValues(_ - ingredient).toMap
+          rest <- helper(newAllergenIngredients2)
+        } yield rest + (allergen -> ingredient)
+      }
+    }
+
+    val allergenIngredients = findAllergenIngredients(foods)
+    helper(allergenIngredients).head
+  }
+
+  def canonicalBadIngredients(foods: Seq[Food]): String = {
+    val allergenIngredients = solveAllergenIngredients(foods)
+
+    allergenIngredients
+      .toSeq
+      .sortBy(_._1)
+      .map(_._2)
+      .mkString(",")
+  }
+
 
   private val foodRegex = """(.*) \(contains (.*)\)""".r
 
@@ -43,5 +75,6 @@ object Day21 {
 
   def main(args: Array[String]): Unit = {
     println(countGoodIngredients(parseFoods(input)))
+    println(canonicalBadIngredients(parseFoods(input)))
   }
 }
diff --git a/src/test/scala/eu/sim642/adventofcode2020/Day21Test.scala b/src/test/scala/eu/sim642/adventofcode2020/Day21Test.scala
@@ -18,4 +18,12 @@ class Day21Test extends AnyFunSuite {
   test("Part 1 input answer") {
     assert(countGoodIngredients(parseFoods(input)) == 2170)
   }
+
+  test("Part 2 examples") {
+    assert(canonicalBadIngredients(parseFoods(exampleInput)) == "mxmxvkd,sqjhc,fvjkl")
+  }
+
+  test("Part 2 input answer") {
+    assert(canonicalBadIngredients(parseFoods(input)) == "nfnfk,nbgklf,clvr,fttbhdr,qjxxpr,hdsm,sjhds,xchzh")
+  }
 }

Original file line number	Diff line number	Diff line change
`@@ -18,4 +18,12 @@ class Day21Test extends AnyFunSuite {`
`18`	`18`	`test("Part 1 input answer") {`
`19`	`19`	`assert(countGoodIngredients(parseFoods(input)) == 2170)`
`20`	`20`	`}`
	`21`	`+`
	`22`	`+ test("Part 2 examples") {`
	`23`	`+ assert(canonicalBadIngredients(parseFoods(exampleInput)) == "mxmxvkd,sqjhc,fvjkl")`
	`24`	`+ }`
	`25`	`+`
	`26`	`+ test("Part 2 input answer") {`
	`27`	`+ assert(canonicalBadIngredients(parseFoods(input)) == "nfnfk,nbgklf,clvr,fttbhdr,qjxxpr,hdsm,sjhds,xchzh")`
	`28`	`+ }`
`21`	`29`	`}`