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.
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) - 1) visited = set()
However, it would fail anything beyond the first test because the nodes stored in the
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) - 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] col2 = col + actions[i] #pdb.set_trace() if row2 >= 0 and row2 < len(maze) and col2 >= 0 and col2 < len(maze): 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) - 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])