From f3d0899dbfd0aa3e6aebf5d19ec89d58ead418b2 Mon Sep 17 00:00:00 2001
From: Tom van der Lee <t0m.vd.l33@gmail.com>
Date: Mon, 19 Dec 2022 09:30:43 +0100
Subject: Day 18

---
 aoc/mixins.py | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

(limited to 'aoc/mixins.py')

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
-- 
cgit v1.2.3