Created
September 10, 2021 18:05
-
-
Save hodunov/67b82feb417385528689641fc683f372 to your computer and use it in GitHub Desktop.
Maze
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from sys import setrecursionlimit | |
maze = [ | |
['#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], # 0 | |
['#', '#', '#', '#', '#', '#', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '#', '#', '#'], # 1 | |
['#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '#', '#', '#', '#', '#', '#', '.', '#', '#', '#'], # 2 | |
['#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '#', '#', '#', '.', '.', '.', '.', '#', '#', '#'], # 3 | |
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '.', '#', '#', '.', '#', '#', '#'], # 4 | |
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '#', '#', '#'], # 5 | |
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '#', '#', '#'], # 6 | |
['#', '#', '.', '#', '#', '#', '#', '.', '#', '#', '#', '#', '#', '.', '#', '#', '.', '#', '#', '#'], # 7 | |
# 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 | |
] | |
def is_exit_here(x, y): | |
""" | |
Function will check if the coordinates match the coordinates of the exit | |
:param x: list coordinate | |
:param y: item coordinate in the list | |
:return: locations dict | |
""" | |
# possible exit positions for x or y | |
if any([x == main_list_length - 1, y == 0, x == 0, y == internal_list_length - 1]): | |
# if x == main_list_length - 1 or y == 0 or x == 0 or y == internal_list_length - 1: | |
# Skip entry coordinates | |
if locations["enter"] != [x, y]: | |
# There may be more than one exit, so let's add all of them | |
locations["exit"].append([x, y]) | |
return locations | |
def solve(maze, x, y, visited): | |
""" | |
Finding an exit of the maze | |
:param maze: NxN matrix | |
:param x (int): list coordinate | |
:param y (int): item coordinate in the list | |
:param visited: size duplicate maze | |
""" | |
if maze[x][y] == ".": | |
# mark the current cell as visible | |
visited[x][y] = True | |
# check exit | |
is_exit_here(x, y) | |
# down | |
if x + 1 < main_list_length and not visited[x + 1][y]: | |
solve(maze, x + 1, y, visited) | |
# up | |
if x - 1 >= 0 and not visited[x - 1][y]: | |
solve(maze, x - 1, y, visited) | |
# right | |
if y + 1 < internal_list_length and not visited[x][y + 1]: | |
solve(maze, x, y + 1, visited) | |
# left | |
if y - 1 >= 0 and not visited[x][y - 1]: | |
solve(maze, x, y - 1, visited) | |
return visited | |
if __name__ == "__main__": | |
# Set the maze entrance coordinates | |
row = 0 | |
column = 6 | |
enter = [row, column] | |
# Main list length | |
main_list_length = len(maze) | |
# Internal list length | |
internal_list_length = len(maze[0]) | |
# Different variants of maze are being considered. | |
# It is necessary to prevent RecursionError. | |
# I don't think making recursion infinite is a good idea, | |
# so I'll try increasing it as follows: | |
setrecursionlimit(1000 + main_list_length * main_list_length) | |
# matrix - a duplicate of the maze to follow the path. | |
visited = [ | |
[False for x in range(internal_list_length)] for y in range(main_list_length) | |
] | |
# Save the entrance and exit to the maze in dict | |
locations = {"enter": enter, "exit": []} | |
# Find a solution | |
solve(maze, enter[0], enter[1], visited) | |
if not locations["exit"]: | |
print( | |
"Buddy, it's really bad. This maze has no way out. " | |
"I hope you're ready for the walk back 😞" | |
) | |
else: | |
print( | |
"Yay! It was a challenge, but we did it!'🎉\n" "Exit location:", | |
*locations["exit"], | |
sep="\n" | |
) | |
print(*visited, sep="\n") | |
assert [7, 13] == locations["exit"][0] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Maze solution