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:
print answer(t)
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
def add_node(self, maze, node):
self.nodes.append(node)
self.node_set.add(node)
node.children = self.get_children(maze, node)
def __repr__(self):
return self.nodes
def answer(maze):
frontier = Frontier()
frontier.nodes = collections.deque([])
frontier.node_set = set()
start = Node((0, 0))
goal = (len(maze) - 1, len(maze[0]) - 1)
visited = set()
frontier.add_node(maze, start)
while frontier.nodes:
state = frontier.nodes.popleft()
#pdb.set_trace()
visited.add(state)
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:
frontier.add_node(maze, state.children[i])
1 Answer 1
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())