Last active
November 26, 2023 16:41
-
-
Save a613/49d65dc30e98c165d567 to your computer and use it in GitHub Desktop.
Maze Solver in Python
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
Source code is copyright 2014 alex@python.code.trimtab.ca | |
Feel free to use and modify for commercial and non-commercial purposes. | |
A link back to this page must be included UNLESS the source is functionally changed. |
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
#################################### | |
#S# ## ######## # # # # # | |
# # # # # # # | |
# # ##### ## ###### # ####### # # | |
### # ## ## # # # #### # | |
# # # ####### # ### #E# | |
#################################### |
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
# | |
# Maze Solver 1.0 | |
# March 2014 | |
# alex@python.code.trimtab.ca | |
# | |
# Solves a maze stored in a text file, and outputs the solution | |
# path to a second text file in the same format. | |
# | |
# Required command-line arguments: <input_file> <output_file> | |
# Example usage: | |
# | |
# <in.txt> | |
# #################################### | |
# #S# ## ######## # # # # # | |
# # # # # # # # | |
# # # ##### ## ###### # ####### # # | |
# ### # ## ## # # # #### # | |
# # # # ####### # ### #E# | |
# #################################### | |
# | |
# python maze.py in.txt out.txt | |
# | |
# <out.txt> | |
# #################################### | |
# #S# ## ########.#.#>>>>>v# >>v# # | |
# #v#>>v# >>>v.....#^# >>>>^#>>v# | |
# #>>^#v#####^##v######^# ####### #v# | |
# ###.#v##>>>^##>>>>>v#^# # ####v# | |
# #...#>>>^#..#######>>^# ### #E# | |
# #################################### | |
# | |
import operator | |
import sys | |
class Maze(object): | |
"""Represents a two-dimensional maze, where each cell can hold a | |
single marker.""" | |
def __init__(self): | |
self.data = [] | |
def read_file(self, path): | |
"""Read a maze text file and split out each character. Return | |
a 2-dimensional list where the first dimension is rows and | |
the second is columns.""" | |
maze = [] | |
with open(path) as f: | |
for line in f.read().splitlines(): | |
maze.append(list(line)) | |
self.data = maze | |
def write_file(self, path): | |
"""Write the specified 2-dimensional maze to the specified | |
file, writing one line per row and with columns | |
side-by-side.""" | |
with open(path, 'w') as f: | |
for r, line in enumerate(self.data): | |
f.write('%s\n' % ''.join(line)) | |
def find(self, symbol): | |
"""Find the first instance of the specified symbol in the | |
maze, and return the row-index and column-index of the | |
matching cell. Return None if no such cell is found.""" | |
for r, line in enumerate(self.data): | |
try: | |
return r, line.index('S') | |
except ValueError: | |
pass | |
def get(self, where): | |
"""Return the symbol stored in the specified cell.""" | |
r, c = where | |
return self.data[r][c] | |
def set(self, where, symbol): | |
"""Store the specified symbol in the specified cell.""" | |
r, c = where | |
self.data[r][c] = symbol | |
def __str__(self): | |
return '\n'.join(''.join(r) for r in self.data) | |
def solve(maze, where=None, direction=None): | |
"""Finds a path through the specified maze beginning at where (or | |
a cell marked 'S' if where is not provided), and a cell marked | |
'E'. At each cell the four directions are tried in the order | |
RIGHT, DOWN, LEFT, UP. When a cell is left, a marker symbol | |
(one of '>', 'v', '<', '^') is written indicating the new | |
direction, and if backtracking is necessary, a symbol ('.') is | |
also written. The return value is None if no solution was | |
found, and a (row_index, column_index) tuple when a solution | |
is found.""" | |
start_symbol = 'S' | |
end_symbol = 'E' | |
vacant_symbol = ' ' | |
backtrack_symbol = '.' | |
directions = (0, 1), (1, 0), (0, -1), (-1, 0) | |
direction_marks = '>', 'v', '<', '^' | |
where = where or maze.find(start_symbol) | |
if not where: | |
# no start cell found | |
return | |
if maze.get(where) == end_symbol: | |
# standing on the end cell | |
return where | |
if maze.get(where) not in (vacant_symbol, start_symbol): | |
# somebody has been here | |
return | |
for direction in directions: | |
next_cell = map(operator.add, where, direction) | |
# spray-painting direction | |
marker = direction_marks[directions.index(direction)] | |
if maze.get(where) != start_symbol: | |
maze.set(where, marker) | |
sub_solve = solve(maze, next_cell, direction) | |
if sub_solve: | |
# found solution in this direction | |
return sub_solve | |
# no directions worked from here - have to backtrack | |
maze.set(where, backtrack_symbol) | |
if __name__ == '__main__': | |
if len(sys.argv) < 3: | |
print 'Arguments: <input file> <output file>' | |
sys.exit(1) | |
input_file, output_file = sys.argv[1:3] | |
maze = Maze() | |
maze.read_file(input_file) | |
solution = solve(maze) | |
if solution: | |
print 'Found end of maze at %s' % solution | |
else: | |
print 'No solution (no start, end, or path)' | |
print maze | |
maze.write_file(output_file) |
still getting an error, a window pops up and closes immediately
still getting an error, a window pops up and closes immediately
Please try running the command in a terminal, if you are on Windows and you run the python program directly it will not allow you to provide arguments and you also won't get to see output.
- Run a terminal/console
- Run
2to3 -w maze.py
to convert the Python 2 code to Python 3 code - Run
python3 maze.py in.txt out.txt
and you'll see this output:
Found end of maze at [5, 34]
####################################
#S# ## ########.#.#>>>>>v# >>v# #
#v#>>v# >>>v.....#^# >>>>^#>>v#
#>>^#v#####^##v######^# ####### #v#
###.#v##>>>^##>>>>>v#^# # ####v#
#...#>>>^#..#######>>^# ### #E#
####################################
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
In case anyone grabs the original code and gets an error when running it with Python 3, you'll need to update it with 2 changes to make it compatible with Python 3.
print
functions, i.e. instead ofprint maze
, make itprint(maze)
map(operator.add, where, direction)
withlist(map(operator.add, where, direction))
Alternatively (and even simpler) just run
2to3 -w maze.py
to convert it in a single shot.If you don't do these changes, when you run
python maze.py in.txt out.txt
there will an error printed: