Day 18

1 files changed, 20 insertions, 0 deletions

diff --git a/aoc/mixins.py b/aoc/mixins.py
index faeb3eb..5986b6e 100644
--- a/aoc/mixins.py
+++ b/aoc/mixins.py
@@ -55,3 +55,23 @@ class AStarMixin(Generic[Node]):
 
                     if neighbour not in open_nodes:
                         open_nodes.add(neighbour)
+
+
+class BreathFirstSearchMixin(Generic[Node]):
+    @staticmethod
+    def bfs(
+        start: Node, neighbours: Callable[[Node], Iterator[Node]]
+    ) -> Iterator[Node]:
+        queue = [start]
+        searched = set()
+
+        while len(queue):
+            item = queue.pop(0)
+
+            for neighbour in neighbours(item):
+                if neighbour not in searched and neighbour not in set(queue):
+                    queue.append(neighbour)
+
+            searched.add(item)
+
+            yield item