Finish first part of day 7

1 files changed, 35 insertions, 0 deletions

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: [],
+  ))
+}