"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-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.
""" 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 - goal) + abs(point - goal) 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) 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 + dx, point + dy if new_point not in explored and \ not labyrinth[new_point][new_point]: 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
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.
"Tell me Sarah, what do you think of my labyrinth?"
That's all folks!
Valentin Bryukhanov aka Bryukh
Welcome to CheckiO - games for coders where you can improve your codings skills.
The main idea behind these games is to give you the opportunity to learn by exchanging experience with the rest of the community. Every day we are trying to find interesting solutions for you to help you become a better coder.Join the Game