"Open Labyrinth" Review

Hi, CiO friends!

Today, let's try to find a path between two points in the maze. We will take a closer look at the "Open Labyrinth" mission. In this mission you are given the map of a maze, and your task is to find a path from one corner to another. The maze can be represented as a graph where empty cells are nodes and adjacent cells are connected. Because we don't need find the shortest path, we can use various graph-traversal algorithms. So let's see what algorithms the CheckiO community came up with.

"So, the Labyrinth is a piece of cake, is it? Well, let's see how you deal with this little slice..."

Breadth(Depth)-First Search

Breadth-first_search and Depth-first_search are similar to each other. DFS visits the child nodes before visiting the sibling nodes; that is, it traverses the depth of any particular path before exploring its breadth. BFS visits the parent nodes before visiting the child nodes. A stack is used for DFS and a queue for BFS. So you can easily "switch" DFS to BFS.

@spoty's solution "BFS + deque" is a classical BFS realisation, using a double ended queue. It's faster than using a list and also we can easily switch BFS to DFS by simply replacing "q.popleft()" => "q.popright()".

from collections import deque
​
​
def checkio(maze_map, start=(1, 1), goal=(10, 10)):
    def get_adjacent(n):
        x, y = n
        n = [(x - 1, y, "N"), (x, y - 1, "W"),
             (x + 1, y, "S"), (x, y + 1, "E")]
        return [((x, y), c) for x, y, c in n if maze_map[x][y] != 1]
​
    q, v = deque([(start, "")]), set()
​
    while q:
        cords, path = q.popleft()
        if cords == goal:
            return path + mark
        if cords in v:
            continue
        v.add(cords)
        for pos, mark in get_adjacent(cords):
            if pos in v:
                continue
            else:
                q.append((pos, path + mark))

Sarah: "You don't by any chance know the way through this labyrinth, do you?"
The Worm: "Who, me? No, I'm just a worm. Say, come inside, and meet the missus"

A* search algorithm

As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way. You can read more on Wikipedia.

For priority queuing, Python has the heapq module and @PositronicLlama's solution "First" takes advantage of it combined with namedtuples to add readabilty here.

"""
Navigate a maze and return a route from the start to the finish.
Use A* to find a path in an efficient manner.
"""
import heapq
import collections
​
# The cardinal directions
DIRECTIONS = [
        (0, -1, 'N'),
        (0, 1, 'S'),
        (-1, 0, 'W'),
        (1, 0, 'E'),
    ]
​
Node = collections.namedtuple('Node', ['hist', 'ix', 'dist', 'pt', 'prev', 'direction'])
​
def heuristic(point, goal):
    """
    Return an admissible heuristic for the distance from point to goal.
    For the case of a grid with orthogonal movement, use the Manhattan distance.
    """
    return abs(point[0] - goal[0]) + abs(point[1] - goal[1])
​
def checkio(labyrinth):
    """
    Return a string of the characters [NSEW] describing a path through labyrinth.
    labyrinth: A list of lists.  '0' indicates a passable cell.
    """
    height, width = len(labyrinth), len(labyrinth[0])
    start = (1, 1)
    goal = (height - 2, width - 2)

    # Each node consists of (estimated path distance, ix, dist, (x, y), previous node, direction)
    # The ix field is a serial number to ensure that subsequent fields are
    # not compared.
    open = [Node(heuristic(start, goal), 0, 0, start, None, None)]

    # A set of all visited coordinates.
    explored = set()

    ix = 1
    while open:
        node = heapq.heappop(open)
        _, _, dist, point, prev, prev_d = node
        if point in explored:
            continue
        if point == goal:
            break
        explored.add(point)

        # Now consider moves in each direction.
        for dx, dy, d in DIRECTIONS:
            new_point = point[0] + dx, point[1] + dy
            if new_point not in explored and \
            not labyrinth[new_point[1]][new_point[0]]:
                h = dist + 1 + heuristic(new_point, goal)
                tie_break = 4 if prev_d != d else 0 # Prefer moving straight
                new_node = Node(h, ix + tie_break, dist + 1, new_point, node, d)
                heapq.heappush(open, new_node)
                ix = ix + 1
​
    # Return a path to node
    result = ''
    while node.prev is not None:
        result = node.direction + result
        node = node.prev
    return result
    

And look at "Re-useable code' by @macfreek.

Sarah: That's not fair!
Jareth: You say that so often, I wonder what your basis for comparison is?

Dijkstra, Lee and others

BFS and A* are the most used algorithms, but there are many others.

Dijkstra's algorithm is famous, so @Miaou's "Dijkstra's Forever !" with explicit comments which can help you to figure out this algorithm.

Lee algorithm is a BFS variation and @suic demonstrates to us how it works in his "First" solution.

Or you can take the classic maze approach and always turn one direction (right or left) to find the exit as @tetedemerou did in the "Always a pit on the right" solution.

Technically a random movement algorithm is a viable algorithm too, and @AndriusMk made their "Trolling :)" solution to illustrate this point.

"Tell me Sarah, what do you think of my labyrinth?"

That's all folks!

Valentin Bryukhanov aka Bryukh