4
\$\begingroup\$

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])
\$\endgroup\$
1
\$\begingroup\$

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())
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.