Skip to content

Instantly share code, notes, and snippets.

@mkorpela
Created November 29, 2023 10:18
Show Gist options
  • Save mkorpela/fc85d7c02c3f5c6af806136eb0eaf4cf to your computer and use it in GitHub Desktop.
Save mkorpela/fc85d7c02c3f5c6af806136eb0eaf4cf to your computer and use it in GitHub Desktop.
class MazeSolver:
def __init__(self, maze):
self.maze = maze
self.rows = len(maze)
self.cols = len(maze[0])
self.start = self.find_start()
self.position = self.start
self.visited = set([self.start])
self.path = [self.start]
def find_start(self):
for i in range(self.rows):
for j in range(self.cols):
if self.maze[i][j] == 'S':
return (i, j)
return None
def is_valid_move(self, position):
x, y = position
return 0 <= x < self.rows and 0 <= y < self.cols and self.maze[x][y] != 1
def get_neighbors(self, position):
x, y = position
neighbors = []
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: # Up, Down, Left, Right
new_pos = (x + dx, y + dy)
if self.is_valid_move(new_pos):
neighbors.append(new_pos)
return neighbors
def solve(self):
while True:
if self.maze[self.position[0]][self.position[1]] == 'E':
return True # Exit found
neighbors = self.get_neighbors(self.position)
unvisited_neighbors = [n for n in neighbors if n not in self.visited]
if not unvisited_neighbors:
# Dead end or loop, backtrack
if not self.path:
return False # No path to exit
self.position = self.path.pop()
continue
# Choose the next position (right-hand wall-following)
next_position = min(unvisited_neighbors, key=lambda n: (n[1], n[0]))
self.visited.add(next_position)
self.path.append(next_position)
self.position = next_position
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment