Looping through multiple breadth first search test cases

Question

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])

Stephen Rauch · Accepted Answer · 2017-06-06 02:02:33Z

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())

Stack Exchange Network

Looping through multiple breadth first search test cases

1 Answer 1

Pep8:

Mutable Default Arguments:

You must log in to answer this question.

Hot Network Questions

Looping through multiple breadth first search test cases

1 Answer 1

Pep8:

Mutable Default Arguments:

You must log in to answer this question.

Related

Hot Network Questions