Python - Depth First labyrinth solver

Question

I have a homework in python, where i am supposed to make a "robot" get from the start to the finish, and return the path to the goal. I have the robot searching, but i want the list to just show the path from start to finish. Right now the pathList returns all visited squares.. and also, when it comes to the goal it doesn't stop, just continue with the other nodes. What am i missing?

def find(labyrinth, robotPos, pathList = []):

    frontier = adjacent_passages(labyrinth, robotPos)   
    pathList.append(robotPos)

    if len(frontier) == 1:
        print("Corner")
        return []

    for i in range(0, len(frontier)):
        if frontier[i] == goal:
            pathList.append(frontier[i])
            return pathList

    for i in range(0, len(frontier)):
        if frontier[i] not in pathList:
            pathList.append(frontier[i])
            if (find(labyrinth, frontier[i], pathList) == []):
                pathList.pop()

    return pathList

I think you need more `print` statements in your code. How do you know that your code is ever reaching the stop condition? — Joel Cornett, Nov 24 '12 at 02:18

score 2 · Answer 1 · edited May 23 '17 at 10:24

2

I don't know if this is the answer to your problem, but the first thing I notice is you shouldn't be using a list as a default function parameter (pathList = []).

See "Least Astonishment" and the Mutable Default Argument

edited May 23 '17 at 10:24

Community

1
1

answered Nov 24 '12 at 02:16

Chris Martin

30,334
10
78
137

score 2 · Answer 2 · answered Nov 24 '12 at 02:21

You're appending robotPos to pathList without removing it even if the search fails, that's why the list contains all visited positions. I'd suggest to avoid list mutations (append/pop) altogether and instead pass a new value as an argument to the next iteration:

if (find(labyrinth, frontier[i], pathList + [frontier[i]]) == [])...

Other possible simplifications are:

drop robotPos. Let the current position be the last item of the path argument
use one loop instead of two
in loops, use for x in stuff instead of for i in range(0, len(stuff))

Something like

def find(path):

    if path[-1] == goal:
        return path

    for new_position in adjacent_positions(path[-1]):
        if new_position not in path:
            found_path = find(path + [new_position])
            if found_path:
                return found_path

    return None

`return None` is unneccessary as `None` is returned by default. — l4mpi, Nov 24 '12 at 08:29

Python - Depth First labyrinth solver

2 Answers2