# Looping through multiple breadth first search test cases

I'm a new and self-taught Python programmer. I've been working my way through the Google FooBar challenges and wrote the following for the prepare_the_bunnies_escape challenge. I submitted the code and it passed all tests, but I had to do a poor workaround that I'd like to fix.

The gist of the challenge is to find the shortest path through a maze only using moves along cardinal directions. An added twist is that you can remove up to one barrier along the path.

tl;dr

When I call answer() and create a new instance of the Frontier class, why aren't the nodes and node_set attributes reset to empty? (full code at bottom)

I came up with a number of test cases, put them into a list, and fed that into my search function:

tests = [test1(), test2(), test3(), test4(), test5()]
for t in tests:


Originally, my search function created a new frontier class like so:

def answer(maze):
frontier = Frontier()
start = Node((0, 0))
goal = (len(maze) - 1, len(maze[0]) - 1)
visited = set()


However, it would fail anything beyond the first test because the nodes stored in the frontier.nodes and frontier.node_set attributes from the first test would persist through the later tests. I tried searching for information on how class instances store variable information but I don't think I was searching for the right terms as I kept coming up empty.

My workaround was to do the below, but this seems like a really bad way to solve the problem.

def answer(maze):
frontier = Frontier()
frontier.nodes = collections.deque([]) # cleared out the deque
frontier.node_set = set()   # cleared out the set
start = Node((0, 0))
goal = (len(maze) - 1, len(maze[0]) - 1)
visited = set()


Full code here:

import collections
import pdb

actions = [[-1, 0],  # Up
[1, 0],   # Down
[0, 1],   # Left
[0, -1]]  # Right

class Node(object):
def __init__(self, loc, depth = 0, bar_removed = False):
self.loc = loc
self.depth = depth
self.bar_removed = bar_removed
self.children = None

def __id(self):
return (self.loc, self.depth, self.bar_removed)

def __repr__(self):
return str(self.__id())

def __eq__(self, other):
return self.__id() == other.__id()

def __hash__(self):
return hash(self.__id())

class Frontier(object):
def __init__(self, nodes = collections.deque([]), node_set = set()):
self.nodes = nodes
self.node_set = node_set

def get_children(self, maze, node):
valid_moves = []
row, col = node.loc
for i in range(len(actions)):
row2 = row + actions[i][0]
col2 = col + actions[i][1]
#pdb.set_trace()
if row2 >= 0 and row2 < len(maze) and col2 >= 0 and col2 < len(maze[0]):
if maze[row2][col2] == 0:
child = Node((row2, col2), node.depth+1, node.bar_removed)
valid_moves.append(child)
elif maze[row2][col2] == 1 and not node.bar_removed:
child = Node((row2, col2), node.depth+1, True)
valid_moves.append(child)
return valid_moves

self.nodes.append(node)
node.children = self.get_children(maze, node)

def __repr__(self):
return self.nodes

frontier = Frontier()
frontier.nodes = collections.deque([])
frontier.node_set = set()
start = Node((0, 0))
goal = (len(maze) - 1, len(maze[0]) - 1)
visited = set()

while frontier.nodes:
state = frontier.nodes.popleft()
#pdb.set_trace()
if state.loc == goal:
return state.depth + 1
else:
for i in range(len(state.children)):
if not state.children[i].loc in visited and not state.children[i] in frontier.node_set:


You did not leave any mazes to run the code against, so I will keep it brief will just a couple of comments.

### Pep8:

Python has a strong idea of how the code should be styled, and it is expressed in pep8.

I suggest you get a style/lint checker. I use the pycharm ide which will show you style and compile issues right in the editor.

### Mutable Default Arguments:

Python's default arguments are only evaluated once. What this means, is that if you have a default argument that is mutable, and that mutable object is modified, then that modified argument will be used the next that a default argument is needed.

So this:

class Frontier(object):
def __init__(self, nodes = collections.deque([]), node_set = set()):
self.nodes = nodes
self.node_set = node_set


adds a set() as self.node_set. Any changes to self.node_set will persist to the next time the default argument is used. The moral to the story is that mutable default arguments are almost always a bad idea. Better would be something like:

class Frontier(object):
def __init__(self, nodes=None, node_set=None):
self.nodes = nodes or collections.deque([])
self.node_set = node_set or set()


Alternatively this:

frontier = Frontier()
frontier.nodes = collections.deque([])
frontier.node_set = set()


Could be:

frontier = Frontier(nodes=collections.deque([]), node_set=set())