Finish all days from 2020 🎆

3 files changed, 201 insertions, 12 deletions

diff --git a/aoc-2020-gleam/src/days/day21.gleam b/aoc-2020-gleam/src/days/day21.gleam
new file mode 100644
index 0000000..a398fb5
--- /dev/null
+++ b/aoc-2020-gleam/src/days/day21.gleam
@@ -0,0 +1,149 @@
+import gleam/io
+import gleam/int
+import gleam/list
+import gleam/pair
+import gleam/string as str
+import gleam/set.{type Set}
+import gleam/dict.{type Dict}
+import ext/setx
+import ext/boolx
+import ext/resultx as resx
+import util/input_util
+import util/parser as p
+
+type Ingredient =
+  String
+
+type Allergen =
+  String
+
+type Food {
+  Food(ingredients: Set(Ingredient), some_allergens: Set(Allergen))
+}
+
+type Candidates =
+  Dict(Allergen, Set(Ingredient))
+
+fn parse_food(text: String) -> Food {
+  let food_parser =
+    p.alpha1()
+    |> p.sep1(by: p.ws_gc())
+    |> p.map(with: set.from_list)
+    |> p.skip(p.literal(" (contains "))
+    |> p.then(
+      p.alpha1()
+      |> p.sep1(by: p.literal(", "))
+      |> p.map(with: set.from_list),
+    )
+    |> p.skip(p.literal(")"))
+    |> p.map2(with: Food)
+
+  text
+  |> p.parse_entire(with: food_parser)
+  |> resx.assert_unwrap
+}
+
+fn allergen_candidates(foods: List(Food)) -> Candidates {
+  foods
+  |> list.map(fn(f) { f.some_allergens })
+  |> setx.arbitrary_union
+  |> set.to_list
+  |> list.map(with: fn(allergen) {
+    #(
+      allergen,
+      foods
+      |> list.filter(keeping: fn(f) {
+        set.contains(in: f.some_allergens, this: allergen)
+      })
+      |> list.map(with: fn(f) { f.ingredients })
+      |> setx.arbitrary_intersection,
+    )
+  })
+  |> dict.from_list
+}
+
+fn stabilize(candidates: Candidates) -> Dict(Allergen, Ingredient) {
+  let is_stable = fn(s) { set.size(s) == 1 }
+
+  use <- boolx.guard_lazy(
+    when: candidates
+    |> dict.values
+    |> list.all(satisfying: is_stable),
+    return: fn() {
+      candidates
+      |> dict.map_values(with: fn(_, ingredients) {
+        let assert [ingredient] = set.to_list(ingredients)
+        ingredient
+      })
+    },
+  )
+
+  let stable_set =
+    candidates
+    |> dict.to_list
+    |> list.filter_map(with: fn(entry) {
+      let #(_, ingredients) = entry
+      case set.to_list(ingredients) {
+        [stable] -> Ok(stable)
+        _ -> Error(Nil)
+      }
+    })
+    |> set.from_list
+
+  candidates
+  |> dict.map_values(with: fn(_, ingredients) {
+    case is_stable(ingredients) {
+      True -> ingredients
+      False -> setx.subtract(from: ingredients, given: stable_set)
+    }
+  })
+  |> stabilize
+}
+
+fn part1(lines: List(String)) -> Int {
+  let foods = list.map(lines, with: parse_food)
+
+  let all_ingredients =
+    foods
+    |> list.map(fn(f) { f.ingredients })
+    |> setx.arbitrary_union
+
+  let candidates = allergen_candidates(foods)
+
+  let suspicious_ingredients =
+    candidates
+    |> dict.values
+    |> setx.arbitrary_union
+
+  let safe_ingredients =
+    setx.subtract(from: all_ingredients, given: suspicious_ingredients)
+
+  foods
+  |> list.map(with: fn(f) {
+    setx.count(f.ingredients, satisfying: set.contains(safe_ingredients, _))
+  })
+  |> int.sum
+}
+
+fn part2(lines: List(String)) -> String {
+  lines
+  |> list.map(with: parse_food)
+  |> allergen_candidates
+  |> stabilize
+  |> dict.to_list
+  |> list.sort(by: fn(a, b) { str.compare(pair.first(a), pair.first(b)) })
+  |> list.map(with: pair.second)
+  |> str.join(",")
+}
+
+pub fn main() -> Nil {
+  let testing = input_util.read_lines("test21")
+  let assert 5 = part1(testing)
+  let assert "mxmxvkd,sqjhc,fvjkl" = part2(testing)
+
+  let input = input_util.read_lines("day21")
+  io.debug(part1(input))
+  io.println(part2(input))
+
+  Nil
+}
diff --git a/aoc-2020-gleam/src/ext/setx.gleam b/aoc-2020-gleam/src/ext/setx.gleam
index 4a9c0c1..f2c67e8 100644
--- a/aoc-2020-gleam/src/ext/setx.gleam
+++ b/aoc-2020-gleam/src/ext/setx.gleam
@@ -1,6 +1,7 @@
 import gleam/list
 import gleam/set.{type Set}
 import gleam/iterator as iter
+import ext/resultx as resx
 import ext/iteratorx as iterx
 
 pub fn count(s: Set(a), satisfying predicate: fn(a) -> Bool) -> Int {
@@ -17,11 +18,21 @@ pub fn map(s: Set(a), with fun: fn(a) -> b) -> Set(b) {
   |> set.from_list
 }
 
+pub fn arbitrary_union(of sets: List(Set(a))) -> Set(a) {
+  list.fold(over: sets, from: set.new(), with: set.union)
+}
+
+pub fn arbitrary_intersection(of sets: List(Set(a))) -> Set(a) {
+  sets
+  |> list.reduce(with: set.intersection)
+  |> resx.assert_unwrap
+}
+
 pub fn flat_map(s: Set(a), with fun: fn(a) -> Set(b)) -> Set(b) {
   s
   |> set.to_list
   |> list.map(with: fun)
-  |> list.fold(from: set.new(), with: set.union)
+  |> arbitrary_union
 }
 
 pub fn toggle(in s: Set(a), this value: a) -> Set(a) {
@@ -31,3 +42,7 @@ pub fn toggle(in s: Set(a), this value: a) -> Set(a) {
     False -> set.insert(into: _, this: value)
   }
 }
+
+pub fn subtract(from a: Set(a), given b: Set(a)) -> Set(a) {
+  set.drop(a, set.to_list(b))
+}
diff --git a/aoc-2020-gleam/src/util/parser.gleam b/aoc-2020-gleam/src/util/parser.gleam
index 3b2e20e..539380b 100644
--- a/aoc-2020-gleam/src/util/parser.gleam
+++ b/aoc-2020-gleam/src/util/parser.gleam
@@ -5,7 +5,7 @@ import gleam/bool
 import gleam/string as str
 import gleam/result as res
 import gleam/function as fun
-import gleam/option.{None, type Option, Some}
+import gleam/option.{type Option, None, Some}
 
 // Heavily inspired by https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/
 
@@ -19,6 +19,8 @@ const unknown = "UNKNOWN"
 
 const whitespace_range = " \t\n"
 
+const alpha_range = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
+
 fn q_s(string: String) -> String {
   "'" <> string <> "'"
 }
@@ -119,6 +121,20 @@ pub fn non_ws_gc() -> Parser(String) {
   |> labeled(with: "non_ws_gc")
 }
 
+pub fn alpha_gc() -> Parser(String) {
+  // gc_satisfying(rule: str.con)
+  gc_in(range: alpha_range)
+  |> labeled(with: "alpha_gc")
+}
+
+pub fn alpha0() -> Parser(String) {
+  str_of_many0(of: alpha_gc())
+}
+
+pub fn alpha1() -> Parser(String) {
+  str_of_many1(of: alpha_gc())
+}
+
 pub fn ws0() -> Parser(String) {
   str_of_many0(of: ws_gc())
 }
@@ -209,11 +225,13 @@ pub fn any(of parsers: List(Parser(a))) -> Parser(a) {
   |> list.reduce(with: or)
   |> res.unwrap(or: failing(with: InvalidParser))
   |> labeled(
-    "any(of: [" <> {
+    "any(of: ["
+    <> {
       parsers
       |> list.map(with: fn(p) { p.label })
       |> str.join(with: ", ")
-    } <> "])",
+    }
+    <> "])",
   )
 }
 
@@ -278,11 +296,13 @@ pub fn seq(of parsers: List(Parser(a))) -> Parser(List(a)) {
       |> prepend_parser(head, _)
   }
   |> labeled(
-    with: "seq(of: [" <> {
+    with: "seq(of: ["
+    <> {
       parsers
       |> list.map(with: fn(p) { p.label })
       |> str.join(", ")
-    } <> "])",
+    }
+    <> "])",
   )
 }
 
@@ -332,8 +352,7 @@ pub fn sep1(parser: Parser(a), by separator: Parser(b)) -> Parser(List(a)) {
   parser
   |> then(many0(of: proceed(separator, parser)))
   |> map2(with: fn(p, ps) { [p, ..ps] })
-  |> labeled(
-    with: "sep1(" <> parser.label <> ", by: " <> separator.label <> ")",
+  |> labeled(with: "sep1(" <> parser.label <> ", by: " <> separator.label <> ")",
   )
 }
 
@@ -341,8 +360,7 @@ pub fn sep0(parser: Parser(a), by separator: Parser(b)) -> Parser(List(a)) {
   parser
   |> sep1(by: separator)
   |> or(otherwise: succeeding(with: []))
-  |> labeled(
-    with: "sep0(" <> parser.label <> ", by: " <> separator.label <> ")",
+  |> labeled(with: "sep0(" <> parser.label <> ", by: " <> separator.label <> ")",
   )
 }
 
@@ -376,7 +394,11 @@ pub fn str_of_len(parser: Parser(String), length: Int) -> Parser(String) {
   |> list.repeat(times: length)
   |> str_of_seq
   |> labeled(
-    with: "str_of_len(" <> parser.label <> "," <> int.to_string(length) <> ")",
+    with: "str_of_len("
+    <> parser.label
+    <> ","
+    <> int.to_string(length)
+    <> ")",
   )
 }
 
@@ -389,7 +411,10 @@ pub fn repeat(parser: Parser(a), times times: Int) -> Parser(List(a)) {
   |> list.repeat(times: times)
   |> seq
   |> labeled(
-    with: parser.label <> " |> repeat(times: " <> int.to_string(times) <> ")",
+    with: parser.label
+    <> " |> repeat(times: "
+    <> int.to_string(times)
+    <> ")",
   )
 }