Finish first part of day 7

6 files changed, 136 insertions, 19 deletions

diff --git a/aoc-2020-gleam/src/aoc_2020_gleam.gleam b/aoc-2020-gleam/src/aoc_2020_gleam.gleam
index 5590629..a4f5902 100644
--- a/aoc-2020-gleam/src/aoc_2020_gleam.gleam
+++ b/aoc-2020-gleam/src/aoc_2020_gleam.gleam
@@ -6,6 +6,7 @@ import days/day03
 import days/day04
 import days/day05
 import days/day06
+import days/day07
 
 pub fn main() -> Nil {
   use day <- runner.with_day()
@@ -16,6 +17,7 @@ pub fn main() -> Nil {
     4 -> day04.run()
     5 -> day05.run()
     6 -> day06.run()
+    7 -> day07.run()
     _ -> io.println("Day not found!")
   }
 }
diff --git a/aoc-2020-gleam/src/days/day07.gleam b/aoc-2020-gleam/src/days/day07.gleam
new file mode 100644
index 0000000..eee817f
--- /dev/null
+++ b/aoc-2020-gleam/src/days/day07.gleam
@@ -0,0 +1,80 @@
+import gleam/io
+import gleam/list
+import gleam/function as fun
+import gleam/pair
+import gleam/iterator as iter
+import gleam/map.{Map}
+import ext/resultx as resx
+import ext/iteratorx as iterx
+import util/graph
+import util/input_util
+import util/parser as p
+
+const special_bag = "shiny gold"
+
+type BagEdge =
+  #(String, Int)
+
+type BagGraph =
+  Map(String, List(BagEdge))
+
+fn parse_graph(lines: List(String)) -> BagGraph {
+  let bag_type_parser =
+    [p.str1_until_ws(), p.ws_gc(), p.str1_until_ws()]
+    |> p.str_of_seq
+    |> p.labeled(with: "bag_type")
+
+  let line_parser =
+    bag_type_parser
+    |> p.then_skip(p.literal(" bags contain "))
+    |> p.then(p.or(
+      p.int()
+      |> p.then_skip(p.ws_gc())
+      |> p.then(bag_type_parser)
+      |> p.map(with: pair.swap)
+      |> p.then_skip(p.ws_gc())
+      |> p.then_skip(p.then(p.literal("bag"), p.opt(p.literal("s"))))
+      |> p.sep1(by: p.literal(", ")),
+      else: p.literal("no other bags")
+      |> p.map(fun.constant([])),
+    ))
+    |> p.then_skip(p.literal("."))
+
+  lines
+  |> list.map(with: fun.compose(
+    p.parse_entire(_, with: line_parser),
+    resx.force_unwrap,
+  ))
+  |> map.from_list
+}
+
+fn part1(lines: List(String)) -> Int {
+  let graph = parse_graph(lines)
+  let neighbours = fn(bag) {
+    graph
+    |> map.get(bag)
+    |> resx.force_unwrap
+    |> list.map(with: pair.first)
+    |> iter.from_list
+  }
+
+  graph
+  |> map.keys
+  |> iter.from_list
+  |> iter.filter(for: fn(bag) { bag != special_bag })
+  |> iterx.count(satisfying: fn(start) {
+    start
+    |> graph.dfs(with: neighbours)
+    |> iter.any(fn(bag) { bag == special_bag })
+  })
+}
+
+pub fn run() -> Nil {
+  let test = input_util.read_lines("test07")
+  assert 4 = part1(test)
+
+  let input = input_util.read_lines("day07")
+  io.debug(part1(input))
+
+  Nil
+}
diff --git a/aoc-2020-gleam/src/ext/iteratorx.gleam b/aoc-2020-gleam/src/ext/iteratorx.gleam
index 456c1d1..8e34351 100644
--- a/aoc-2020-gleam/src/ext/iteratorx.gleam
+++ b/aoc-2020-gleam/src/ext/iteratorx.gleam
@@ -3,8 +3,7 @@ import gleam/list
 
 pub fn length(iterator: Iterator(a)) -> Int {
   iterator
-  |> iter.to_list
-  |> list.length
+  |> iter.fold(from: 0, with: fn(c, _) { c + 1 })
 }
 
 pub fn count(iterator: Iterator(a), satisfying predicate: fn(a) -> Bool) -> Int {
diff --git a/aoc-2020-gleam/src/ext/listx.gleam b/aoc-2020-gleam/src/ext/listx.gleam
index d962515..bead987 100644
--- a/aoc-2020-gleam/src/ext/listx.gleam
+++ b/aoc-2020-gleam/src/ext/listx.gleam
@@ -1,7 +1,8 @@
-import gleam/list
+import gleam/iterator as iter
+import ext/iteratorx as iterx
 
 pub fn count(list: List(a), satisfying predicate: fn(a) -> Bool) -> Int {
   list
-  |> list.filter(for: predicate)
-  |> list.length
+  |> iter.from_list
+  |> iterx.count(satisfying: predicate)
 }
diff --git a/aoc-2020-gleam/src/util/graph.gleam b/aoc-2020-gleam/src/util/graph.gleam
new file mode 100644
index 0000000..d9aa5aa
--- /dev/null
+++ b/aoc-2020-gleam/src/util/graph.gleam
@@ -0,0 +1,35 @@
+import gleam/list
+import gleam/iterator.{Iterator} as iter
+import gleam/set.{Set}
+
+fn dfs_helper(
+  neighbours: fn(a) -> Iterator(a),
+  stack stack: List(a),
+  visited visited: Set(a),
+  acc acc: List(a),
+) -> List(a) {
+  case stack {
+    [node, ..stack] ->
+      dfs_helper(
+        neighbours,
+        stack: node
+        |> neighbours
+        |> iter.filter(for: fn(n) { !set.contains(visited, n) })
+        |> iter.to_list
+        |> list.append(stack),
+        visited: visited
+        |> set.insert(node),
+        acc: [node, ..acc],
+      )
+    [] -> list.reverse(acc)
+  }
+}
+
+pub fn dfs(from start: a, with neighbours: fn(a) -> Iterator(a)) -> Iterator(a) {
+  iter.from_list(dfs_helper(
+    neighbours,
+    stack: [start],
+    visited: set.new(),
+    acc: [],
+  ))
+}
diff --git a/aoc-2020-gleam/src/util/parser.gleam b/aoc-2020-gleam/src/util/parser.gleam
index 59c6f62..66c20e3 100644
--- a/aoc-2020-gleam/src/util/parser.gleam
+++ b/aoc-2020-gleam/src/util/parser.gleam
@@ -9,7 +9,7 @@ import gleam/option.{None, Option, Some}
 
 // Heavily inspired by https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/
 
-// TODO: - make distinction between atomic (int, string literal) and non-atomic (then, sequence)
+// TODO: - make distinction between atomic (int, string literal) and non-atomic (then, seq)
 //         parsers and only override error sources for atomic parsers
 //       - report where the error occured in the error struct
 
@@ -253,17 +253,17 @@ fn lift2(function: fn(a, b) -> c) -> fn(Parser(a), Parser(b)) -> Parser(c) {
   }
 }
 
-pub fn sequence(of parsers: List(Parser(a))) -> Parser(List(a)) {
+pub fn seq(of parsers: List(Parser(a))) -> Parser(List(a)) {
   let prepend_parser = lift2(fn(x, xs) { [x, ..xs] })
   case parsers {
     [] -> succeeding(with: [])
     [head, ..tail] ->
       tail
-      |> sequence
+      |> seq
       |> prepend_parser(head, _)
   }
   |> labeled(
-    with: "sequence(of: [" <> {
+    with: "seq(of: [" <> {
       parsers
       |> list.map(with: fn(p) { p.label })
       |> string.join(", ")
@@ -271,9 +271,9 @@ pub fn sequence(of parsers: List(Parser(a))) -> Parser(List(a)) {
   )
 }
 
-pub fn str_of_sequence(of parsers: List(Parser(String))) -> Parser(String) {
+pub fn str_of_seq(of parsers: List(Parser(String))) -> Parser(String) {
   parsers
-  |> sequence
+  |> seq
   |> map(with: string.concat)
 }
 
@@ -314,21 +314,21 @@ pub fn str_of_many1(of parser: Parser(String)) -> Parser(String) {
   |> map(with: string.concat)
 }
 
-pub fn sep0(parser: Parser(a), by separator: Parser(b)) -> Parser(List(a)) {
+pub fn sep1(parser: Parser(a), by separator: Parser(b)) -> Parser(List(a)) {
   parser
   |> then(many0(of: drop_then(separator, parser)))
   |> map2(with: fn(p, ps) { [p, ..ps] })
   |> labeled(
-    with: "sep0(" <> parser.label <> ", by: " <> separator.label <> ")",
+    with: "sep1(" <> parser.label <> ", by: " <> separator.label <> ")",
   )
 }
 
-pub fn sep1(parser: Parser(a), by separator: Parser(b)) -> Parser(List(a)) {
+pub fn sep0(parser: Parser(a), by separator: Parser(b)) -> Parser(List(a)) {
   parser
-  |> sep0(by: separator)
+  |> sep1(by: separator)
   |> or(else: succeeding(with: []))
   |> labeled(
-    with: "sep1(" <> parser.label <> ", by: " <> separator.label <> ")",
+    with: "sep0(" <> parser.label <> ", by: " <> separator.label <> ")",
   )
 }
 
@@ -353,14 +353,14 @@ pub fn literal(expected: String) -> Parser(String) {
   expected
   |> string.to_graphemes
   |> list.map(with: fn(eg) { gc_satisfying(fn(g) { g == eg }) })
-  |> str_of_sequence
+  |> str_of_seq
   |> labeled(with: q_d(expected))
 }
 
 pub fn str_of_len(parser: Parser(String), length: Int) -> Parser(String) {
   parser
   |> list.repeat(times: length)
-  |> str_of_sequence
+  |> str_of_seq
   |> labeled(
     with: "str_of_len(" <> parser.label <> "," <> int.to_string(length) <> ")",
   )
@@ -373,7 +373,7 @@ pub fn any_str_of_len(length: Int) -> Parser(String) {
 pub fn repeat(parser: Parser(a), times times: Int) -> Parser(List(a)) {
   parser
   |> list.repeat(times: times)
-  |> sequence
+  |> seq
   |> labeled(
     with: parser.label <> " |> repeat(times: " <> int.to_string(times) <> ")",
   )