Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Breadth First Search solution in Uncategorized category for Open Labyrinth by Anne29
from collections import deque
# Okay, let's express the compass directions as tuples: (delta x, delta y)
direction = { "N": (-1, 0), "S": (1, 0), "E": (0, 1), "W": (0, -1)}
map = [] # Yeah, global data bitches. It's faster.
# We're gonna have to find the next position often, so let's write a function.
def next_place(x, y, dir):
(delta_x, delta_y) = direction[dir]
new_x = x + delta_x
new_y = y + delta_y
return (new_x, new_y)
def next_thing(x, y, dir):
(delta_x, delta_y) = direction[dir]
new_x = x + delta_x
new_y = y + delta_y
if new_x < 0 or new_x >= len(map[0]):
return 1
if new_y < 0 or new_y >= len(map):
return 1
return map[new_x][new_y]
# Breadth first search seems like the thing to do.
def bfs(data):
# Let's create a queue of positions and paths to that position.
# Originally, we just have the start position
states = deque([(1, 1, "")])
visited = {}
global map
map = data
while len(states) > 0: # boy, I hope there's a solution!
(x, y, path) = states.popleft()
# print ("X = ", x, ", y = ", y)
visited[(x, y)] = True
if x == 10 and y == 10:
# Yay! Found it!
return path
# So, we normally want to go SE, so bias the data in that direction
# checking S and E first (this would be a bigger deal for dfs).
possible_dir = ["S", "E", "W", "N"]
for next_dir in possible_dir:
if next_thing(x, y, next_dir) == 0:
# Safe? Go!
(sx, sy) = next_place(x, y, next_dir)
if (sx, sy) not in visited:
states.append((sx, sy, path + next_dir))
def checkio(data):
#Your code here
#It's main function. Don't remove this function
#It's using for auto-testing and must return a result for check.
#replace this for solution
#This is just example for first maze
#return "SSSSSEENNNEEEEEEESSWWWWSSSEEEESS"
return bfs(data)
#Some hints
#Look to graph search algorithms
#Don't confuse these with tree search algorithms
#This code using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
print(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 careful with infinity loop
print(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]
]))
print(checkio([
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]))
print(checkio([
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1],
[1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]))
Nov. 7, 2013
Comments:
