Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Corn Fields are Awesome! solution in Clear category for Open Labyrinth by zero_loss
"""
This set of functions provide some basic assistance to determine
how far two points are apart and if the chose location is a valid
point to travel to in the labyrinth.
"""
def abs_delta_move(pt1, pt2):
return sum([abs(p-q) for p,q in zip(pt1,pt2)])
def valid_location(maze, x, y):
return maze[x][y] == 0
"""
This set of functions defines how to move through the representation
of the labyrinth in terms of cardinal directions.
"""
def move(x, y, h, v):
return (x + h, y + v)
#define directional moves
north = lambda x, y: move(x, y, -1, 0)
south = lambda x, y: move(x, y, 1, 0)
east = lambda x, y: move(x, y, 0, 1)
west = lambda x, y: move(x, y, 0, -1)
move_direction = {'N':north, 'S':south, 'E':east, 'W':west,}
"""
This block of code is used to turn an iteratable of locations into
a string. This is predicated on the fact that each location is 1
absolute distance from the previous location.
"""
directon_moved = {(0,0):'',(-1,0):'N',(1,0):'S',(0,1):'E',(0,-1):'W',}
def path_to_string(path):
def moved(pt1, pt2):
return (pt2[0] - pt1[0], pt2[1]-pt1[1])
return ''.join([directon_moved[moved(p,q)] for p,q in zip(path[:-1], path[1:])])
"""
This is a function to test if a path string is a valid way to move
through the representation of the labyrinth. This is used to test the
path finding algorithm.
"""
def run_maze(maze, path, start=(1,1), goal=(10,10)):
location = start
for d in path:
location = move_direction[d](*location)
if not valid_location(maze, *location): return False
return location == goal
"""
This is the code used to find the way through the labyrinth. The
path is returned as a string of N, E, S, W directional moves from
the start to the goal. While the returned path should be valid,
there is no guarantee that it is optimal. In fact, it is likely
**NOT** optimal.
"""
def checkio(maze, start=(1,1), goal=(10,10)):
directions = ['N','E','S', 'W',]
nodes_visited = []
nodes_to_vist = [start]
path = [start]
while len(nodes_to_vist) > 0:
location = nodes_to_vist.pop()
while abs_delta_move(path[-1], location) > 1:
path.pop()
path.append(location)
if location == goal: break
nodes_visited.append(location)
for d in directions:
next_location = move_direction[d](*location)
if valid_location(maze, *next_location) and \
next_location not in nodes_visited:
nodes_to_vist.append(next_location)
return path_to_string(path)
#Tests
if __name__ == '__main__':
maze_1 = [
[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, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
assert run_maze(maze_1, 'E'*9 + 'S'*9), 'run east and south'
assert run_maze(maze_1, 'N'*9 + 'W'*9, (10,10), (1,1)), 'run north and west'
assert abs_delta_move((1,2),(1,2)) == 0
assert abs_delta_move((1,2),(2,2)) == 1
assert abs_delta_move((1,1),(2,2)) == 2
assert abs_delta_move((2,2),(1,1)) == 2
assert checkio(maze_1, find_path(maze_1))
Jan. 11, 2015
