Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Open Labyrinth by PositronicLlama
"""
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
if __name__ == '__main__':
#Return any route to exit
checkio([
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],
[1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]])
#be carefull with infinity loop
checkio([
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
])
April 11, 2013
Comments:
