My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1def bfs(start, graph):
2 from collections import deque
3
4 max_depth = 0
5 depths = {}
6 horizon = deque([(start, 0)]) # node, depth
7 seen = {start: None}
8
9 # TODO
10 def is_goal(node):
11 return graph.get(node) == 'G'
12
13 def gen_neighbours(node):
14 for n in node.neighbours_4():
15 if graph.get(n, ' ') != ' ':
16 yield n
17
18
19 while horizon:
20 node, depth = horizon.popleft() # pop() for DFS
21 depths[node] = depth
22
23 if depth > max_depth:
24 max_depth = depth
25 print "BFS @ {}; depth={}, horizon={}, seen={}".format(node, depth, len(horizon), len(seen))
26
27 for new in gen_neighbours(node):
28 if new in seen:
29 continue
30
31 seen[new] = node
32 horizon.append((new, depth + 1))
33
34 if is_goal(new):
35 print "FOUND GOAL", new, depth + 1
36 path = []
37 curr = new
38 while curr is not None:
39 path.append(curr)
40 curr = seen[curr]
41 for p in reversed(path):
42 print p
43 pass
44 print "FOUND GOAL", new, depth + 1
45 return depth + 1
46
47 print "FLOOD FILL COMPLETE, max_depth={}, seen={}".format(max_depth, len(seen))
48 return depths
49
50start = Point(0, 0)
51bfs(start, board)