Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Dark Labyrinth by sawako.oono
from collections import deque
from collections import Counter
memory_outside=[]
def find_path(visible,memory=memory_outside):
graph=[list(row) for row in visible]
w_y=len(graph)
w_x=len(graph[0])
for y in range(w_y):
for x in range(w_x):
if graph[y][x]=="P":
start=(y,x)
end=None
for y in range(w_y):
for x in range(w_x):
if graph[y][x]=="E":
end=(y,x)
q=deque()
q.append(((start),""))
seen=[]
options={"E":(0,1),"W":(0,-1),"S":(1,0),"N":(-1,0)}
opposite={"E":"W","W":"E","S":"N","N":"S"}
final=[]
last=memory[-1][1] if memory!=[] else None
if last!=None:
last_o=Counter()
for i in range(len(last)-1,-1,-1):
last_o[opposite[last[i]]]+=1
while q:
now,path=q.pop()
if path in seen:
continue
else:
seen.append(path)
if len(path)>=1:
if end:
if now==end:
print("found")
memory.clear()
return path
Y,X=now[0],now[1]
for key,(y,x) in options.items():
if 0<=Y+y<=w_y-1 and 0<=X+x<=w_x-1 and graph[Y+y][X+x] in (".","E"):
if any((len(path)>=1 and path[-1]!=opposite[key],len(path)==0)):
now_c=(Y+y,X+x)
path_c=path+key
q.append((now_c,path_c))
if any((Y+y==-1,Y+y==w_y,X+x==-1,X+x==w_x)):
final.append(path)
continue
elif graph[Y+y][X+x]=="?":
final.append(path)
continue
if last==None:
final=sorted(final,key=lambda x:len(x),reverse=True)
else:
final=sorted(final,key=lambda x:len(x),reverse=True)
final=sorted(final,key=lambda x: sum([x.count(key) for key,value in last_o.items()]),reverse=True)
final2=[x for x in final if [visible,x] not in memory]
if final2!=[]:
final=final2.copy()
memory.append([visible,final[-1]])
last=final[-1]
return final[-1]
if __name__ == '__main__':
# These "asserts" using only for self-checking and not necessary for auto-testing
DIR = {"N": (-1, 0), "S": (1, 0), "W": (0, -1), "E": (0, 1)}
PLAYER = "P"
WALL = "X"
UNKNOWN = "?"
EXIT = "E"
EMPTY = "."
MAX_STEP = 250
def clear_zone(zone):
return [row for row in zone if not all(el == UNKNOWN for el in row)]
def get_visible(maze, player):
grid = [["?" for _ in range(len(row))] for row in maze]
grid[player[0]][player[1]] = PLAYER
for direction, diff in DIR.items():
r, c = player
while maze[r][c] != WALL:
r, c = r + diff[0], c + diff[1]
grid[r][c] = maze[r][c]
if direction in "NS":
grid[r + DIR["W"][0]][c + DIR["W"][1]] = maze[r + DIR["W"][0]][c + DIR["W"][1]]
grid[r + DIR["E"][0]][c + DIR["E"][1]] = maze[r + DIR["E"][0]][c + DIR["E"][1]]
else:
grid[r + DIR["S"][0]][c + DIR["S"][1]] = maze[r + DIR["S"][0]][c + DIR["S"][1]]
grid[r + DIR["N"][0]][c + DIR["N"][1]] = maze[r + DIR["N"][0]][c + DIR["N"][1]]
grid = clear_zone(list(zip(*clear_zone(grid))))
return tuple("".join(trow) for trow in zip(*grid))
def initial(maze, player):
return maze, get_visible(maze, player)
def checker(func, player, maze):
step = 0
while True:
result = func(get_visible(maze, player))
if not isinstance(result, str) or any(ch not in DIR.keys() for ch in result):
print("The function should return a string with directions.")
return False
for act in result:
if step >= MAX_STEP:
print("You are tired and your flashlight is off. Bye bye.")
return False
r, c = player[0] + DIR[act][0], player[1] + DIR[act][1]
if maze[r][c] == WALL:
print("BAM! You in the wall at {}, {}.".format(r, c))
return False
elif maze[r][c] == EXIT:
print("GRATZ!")
return True
else:
player = r, c
step += 1
assert checker(find_path, (1, 1), [
"XXXXXXX",
"X.....X",
"X.X.X.X",
"X.....X",
"X.X.X.X",
"X.X.E.X",
"XXXXXXX",
]), "Simple"
assert checker(find_path, (1, 4), [
"XXXXXXXXXX",
"X....X...X",
"X.XXXX.X.X",
"X....X.X.X",
"X.XXXX.X.X",
"X.X....X.X",
"X.XXEX.X.X",
"X.XXXXXX.X",
"X........X",
"XXXXXXXXXX",
]), "First"
assert checker(find_path, (10, 10), [
"XXXXXXXXXXXX",
"XX...X.....X",
"X..X.X.X.X.X",
"X.XX.X.X.X.X",
"X..X.X.X.X.X",
"XX.X.X.X.X.X",
"X..X.X.X.X.X",
"X.XX.X.X.X.X",
"X..X.X.X.X.X",
"XX.X.X.X.X.X",
"XE.X.....X.X",
"XXXXXXXXXXXX",
]), "Up down"
assert checker(find_path, (2, 1), [
"XXXXXXXXXXXXXXX",
"X.............X",
"X.XXXXXXXXXXX.X",
"X.X.........X.X",
"X.X.XXX.XXX.X.X",
"X.X.X.....X.X.X",
"X.X.X.XXX.X.X.X",
"X.X.X.XEX.X.X.X",
"X.X.X.....X.X.X",
"X.X.XXXXXXX.X.X",
"X.X.........X.X",
"X.X.XXX.XXX.X.X",
"X.............X",
"XXXXXXXXXXXXXXX",
]), "Left"
July 5, 2021
Comments: