Path Finder 1 (Code Wars 16)

Variation on island finding. Which is to say, more depth-first-search. Embarrassingly, I forgot some the base case!

def neighbors(maze, i, j):
    toTry = []
    if i > 0:
        toTry.append((i-1, j))
    if j > 0:
        toTry.append((i, j-1))
    if i + 1 < len(maze):
        toTry.append((i+1, j))
    if j + 1 < len(maze[i]):
        toTry.append((i, j+1))
    final = [(a, b) for (a, b) in toTry if maze[a][b] == '.']
    return final
def path_finder(maze):
    maze = maze.split()
    for row in maze:
        assert(len(row) == len(maze))
    seen = set([])
    toVisit = [(0,0)]
    seen.add((0, 0))
    target = (len(maze)-1, len(maze)-1)
    while toVisit:
        i, j = toVisit.pop()
        for (a, b) in neighbors(maze, i, j):
            if (a, b) in seen:
                continue
            seen.add((a, b))
            toVisit.append((a, b))
    return target in seen

Leave a Reply