Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Dark Labyrinth by freeman_lex
LAB = {(0, 0): "."}
MOVES = {(1, 0): "S", (-1, 0): "N", (0, -1): "W", (0, 1): "E"}
PL = 0, 0
def find_path(visible: list[list[int]]) -> str:
global LAB, MOVES, PL
EX = None
# finding player coords and differences from stored player's coord
ir = 0
while ir < len(visible):
ic = 0
while ic < len(visible[0]):
if visible[ir][ic] == "P":
dr = PL[0] - ir
dc = PL[1] - ic
ir = len(visible)
break
ic += 1
ir += 1
# filling the dict with coords (adjusted by the diffs, so player's
# coords become the same as stored) and respective maze chars
for ir, row in enumerate(visible):
for ic, char in enumerate(row):
ir2, ic2 = ir + dr, ic + dc
if char in "?.X":
if (ir2, ic2) not in LAB or LAB[(ir2, ic2)] == "?" != char:
LAB[(ir2, ic2)] = char
elif char == "E":
LAB[(EX := (ir2, ic2))] = "."
# if exit at the current maze - build path and
# clear working vars before next test
if EX:
path = move(PL, EX)
LAB = {(0, 0): "."}
PL = 0, 0
EX = None
return path
# finding all coords near unknown (near "?" or enge of the maze)
dirs = []
for (row, col), char in LAB.items():
if char == ".":
for dr, dc in MOVES:
if LAB.get((row + dr, col + dc), "?") == "?":
dirs.append(((row, col)))
# choosing the closest one to the player,
# building path and mooving there
closest = min(dirs, key = lambda i: (i[0]-PL[0])**2 + (i[1]-PL[1])**2)
path = move(PL, closest)
PL = closest
return path
def move(start: tuple[int, int], end: tuple[int, int]) -> str:
global LAB, MOVES
sols = [([start], 0)]
while sols:
path, dist = sols.pop(0)
pr, pc = path[-1]
for dr, dc in MOVES:
pr1, pc1 = pr + dr, pc + dc
if LAB.get((pr1, pc1), "X") != "X" and (pr1, pc1) not in path:
path1 = path[:] + [(pr1, pc1)]
if (pr1, pc1) == end:
return "".join(MOVES[(r2 - r1, c2 - c1)]
for (r1, c1), (r2, c2) in zip(path1, path1[1:]))
dist1 = (pr1 - end[0])**2 + (pc1 - end[1])**2
sols.append((path1, dist1))
sols.sort(key = lambda i: i[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"
Feb. 11, 2023
Comments:
