Solve day 19

5 files changed, 131 insertions, 6 deletions

diff --git a/aoc-2020-gleam/src/days/day04.gleam b/aoc-2020-gleam/src/days/day04.gleam
index e5d5d21..dfeba0f 100644
--- a/aoc-2020-gleam/src/days/day04.gleam
+++ b/aoc-2020-gleam/src/days/day04.gleam
@@ -38,7 +38,7 @@ fn parse_passports(from text: String) -> List(Passport) {
     |> p.labeled(with: "passport")
   let input_parser =
     passport_parser
-    |> p.sep1(by: p.literal("\n\n"))
+    |> p.sep1(by: p.nlnl())
     |> p.skip_ws
     |> p.labeled(with: "input")
 
diff --git a/aoc-2020-gleam/src/days/day06.gleam b/aoc-2020-gleam/src/days/day06.gleam
index ee01071..1e2853b 100644
--- a/aoc-2020-gleam/src/days/day06.gleam
+++ b/aoc-2020-gleam/src/days/day06.gleam
@@ -37,7 +37,7 @@ fn parse_input(text: String) -> Input {
 
   let input_parser =
     group_parser
-    |> p.sep1(by: p.literal("\n\n"))
+    |> p.sep1(by: p.nlnl())
     |> p.skip_ws
     |> p.labeled(with: "input")
 
diff --git a/aoc-2020-gleam/src/days/day16.gleam b/aoc-2020-gleam/src/days/day16.gleam
index 73a1a30..d978ac7 100644
--- a/aoc-2020-gleam/src/days/day16.gleam
+++ b/aoc-2020-gleam/src/days/day16.gleam
@@ -54,12 +54,16 @@ fn parse_notes(input: String) -> Notes {
 
   let notes_parser =
     field_parser
-    |> p.sep1(by: p.literal("\n"))
+    |> p.sep1(by: p.nl())
     |> p.map(with: map.from_list)
-    |> p.skip(p.literal("\n\nyour ticket:\n"))
+    |> p.skip(p.nlnl())
+    |> p.skip(p.literal("your ticket:"))
+    |> p.skip(p.nl())
     |> p.then(ticket_parser)
-    |> p.skip(p.literal("\n\nnearby tickets:\n"))
-    |> p.then_3rd(p.sep1(ticket_parser, by: p.literal("\n")))
+    |> p.skip(p.nlnl())
+    |> p.skip(p.literal("nearby tickets:"))
+    |> p.skip(p.nl())
+    |> p.then_3rd(p.sep1(ticket_parser, by: p.nl()))
     |> p.skip_ws()
     |> p.map3(with: Notes)
     |> p.labeled(with: "notes")
diff --git a/aoc-2020-gleam/src/days/day19.gleam b/aoc-2020-gleam/src/days/day19.gleam
new file mode 100644
index 0000000..bfee1e8
--- /dev/null
+++ b/aoc-2020-gleam/src/days/day19.gleam
@@ -0,0 +1,111 @@
+import gleam/io
+import gleam/list
+import gleam/bool
+import gleam/string as str
+import gleam/map.{Map}
+import ext/listx
+import ext/resultx as resx
+import util/input_util
+import util/parser as p
+
+type Rule {
+  Literal(String)
+  Reference(List(List(Int)))
+}
+
+type Ruleset =
+  Map(Int, Rule)
+
+fn parse_input(input: String) -> #(Ruleset, List(String)) {
+  let rule_parser =
+    p.int()
+    |> p.skip(p.literal(": "))
+    |> p.then(
+      p.literal("\"")
+      |> p.proceed(with: p.any_gc())
+      |> p.skip(p.literal("\""))
+      |> p.map(with: Literal)
+      |> p.or(
+        else: p.int()
+        |> p.sep1(by: p.literal(" "))
+        |> p.sep1(by: p.literal(" | "))
+        |> p.map(with: Reference),
+      ),
+    )
+    |> p.labeled(with: "rule")
+
+  let input_parser =
+    rule_parser
+    |> p.sep1(by: p.nl())
+    |> p.map(with: map.from_list)
+    |> p.skip(p.nlnl())
+    |> p.then(
+      p.str1_until_ws()
+      |> p.sep1(by: p.nl()),
+    )
+    |> p.skip_ws()
+
+  input
+  |> p.parse_entire(with: input_parser)
+  |> resx.assert_unwrap
+}
+
+fn matches(
+  gc_queue: List(String),
+  rule_queue: List(Int),
+  ruleset: Ruleset,
+) -> Bool {
+  case #(gc_queue, rule_queue) {
+    #([gc, ..rest], [rule_id, ..rule_queue]) -> {
+      let assert Ok(rule) = map.get(ruleset, rule_id)
+      case rule {
+        Literal(expected) -> {
+          use <- bool.guard(when: gc != expected, return: False)
+          matches(rest, rule_queue, ruleset)
+        }
+        Reference(alternatives) ->
+          alternatives
+          |> list.any(satisfying: fn(expanded) {
+            matches(gc_queue, list.append(expanded, rule_queue), ruleset)
+          })
+      }
+    }
+    #([], []) -> True
+    _ -> False
+  }
+}
+
+fn solve(for messages: List(String), under ruleset: Ruleset) -> Int {
+  messages
+  |> listx.count(satisfying: fn(message) {
+    matches(str.to_graphemes(message), [0], ruleset)
+  })
+}
+
+fn part1(input: String) -> Int {
+  let #(ruleset, messages) = parse_input(input)
+
+  solve(for: messages, under: ruleset)
+}
+
+fn part2(input: String) -> Int {
+  let #(ruleset, messages) = parse_input(input)
+  let ruleset =
+    ruleset
+    |> map.insert(for: 8, insert: Reference([[42], [42, 8]]))
+    |> map.insert(for: 11, insert: Reference([[42, 31], [42, 11, 31]]))
+
+  solve(for: messages, under: ruleset)
+}
+
+pub fn main() -> Nil {
+  let test = input_util.read_text("test19")
+  let assert 3 = part1(test)
+  let assert 12 = part2(test)
+
+  let input = input_util.read_text("day19")
+  io.debug(part1(input))
+  io.debug(part2(input))
+
+  Nil
+}
diff --git a/aoc-2020-gleam/src/util/parser.gleam b/aoc-2020-gleam/src/util/parser.gleam
index f143c92..1d4bba9 100644
--- a/aoc-2020-gleam/src/util/parser.gleam
+++ b/aoc-2020-gleam/src/util/parser.gleam
@@ -127,6 +127,16 @@ pub fn ws1() -> Parser(String) {
   str_of_many1(of: ws_gc())
 }
 
+pub fn nl() -> Parser(String) {
+  gc_in("\n")
+  |> labeled(with: "nl")
+}
+
+pub fn nlnl() -> Parser(String) {
+  literal("\n\n")
+  |> labeled(with: "nlnl")
+}
+
 pub fn str0_until_ws() -> Parser(String) {
   str_of_many0(of: non_ws_gc())
 }