In [1]:
class Grid:
def __init__(self, width, height, number):
self.number = number
self.width = width
self.height = height
self.grid = self.get_grid()
def __repr__(self):
return "\n".join([''.join(['.' if col else '#' for col in row]) for row in self.grid])
def solve_equation(self, x, y):
return x * x + 3 * x + 2 * x * y + y + y * y + self.number
@staticmethod
def is_wall(n):
return False if bin(n).count('1') % 2 == 0 else True
def is_valid(self, x, y):
if x < 0 or x >= self.width or y < 0 or y >= self.height:
return False
if not self.grid[y][x]:
return False
return True
def get_grid(self):
return [[not self.is_wall(self.solve_equation(x, y))
for x in range(self.width)]
for y in range(self.height)]
In [2]:
class Maze:
def __init__(self, start_x, start_y, end_x, end_y, grid):
self.grid = grid
self.start_x = start_x
self.start_y = start_y
self.end_x = end_x
self.end_y = end_y
self.visited = set([])
self.solution = []
self.solutions = []
self.movements = []
def __repr__(self):
grid = ''
for y, row in enumerate(self.grid.grid):
line = ''
for x, col in enumerate(row):
if (x, y) in self.solution:
grid += 'o'
elif (x, y) in self.visited:
grid += '-'
else:
grid += '.' if col else '#'
grid += '\n'
return grid
def solve(self, init=False):
if init:
self.movements.append((self.start_x, self.start_y, [(self.start_x, self.start_y)]))
if len(self.movements) == 0:
return False
(x, y, path) = self.movements.pop(0)
self.visited.add((x, y))
if x == self.end_x and y == self.end_y:
self.solution = path
return True
for (x_, y_) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if self.grid.is_valid(x_, y_) and (x_, y_) not in self.visited:
self.movements.append((x_, y_, path + [(x_, y_)]))
return self.solve()
# This method does not give the shortest path
def solve_recursion(self, x=None, y=None):
if x is None or y is None:
x = self.start_x
y = self.start_y
if x == self.end_x and y == self.end_y:
self.solutions.append((x, y))
return True
elif (x, y) in self.visited:
return False
elif self.grid.is_valid(x, y):
self.visited.add((x, y))
if (self.solve_recursion(x + 1, y) or
self.solve_recursion(x - 1, y) or
self.solve_recursion(x, y + 1) or
self.solve_recursion(x, y - 1)):
self.solutions.append((x, y))
return True
else:
return False
def get_steps(self):
return len(self.solution) - 1
In [3]:
# Test
grid = Grid(width=10, height=7, number=10)
maze = Maze(start_x=1, start_y=1, end_x=7, end_y=4, grid=grid)
#maze.solve_recursion()
maze.solve(init=True)
assert maze.get_steps() == 11
In [4]:
print(grid)
print()
print(maze)
In [5]:
grid = Grid(width=34, height=42, number=1362)
maze = Maze(start_x=1, start_y=1, end_x=31, end_y=39, grid=grid)
maze.solve(init=True)
print(maze.get_steps())
print(maze)
In [6]:
class MazeSteps(Maze):
def solve(self, init=False, max_steps=None):
if init:
self.movements.append((self.start_x, self.start_y, [(self.start_x, self.start_y)]))
while len(self.movements) > 0:
(x, y, path) = self.movements.pop(0)
self.visited.add((x, y))
for (x_, y_) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if self.grid.is_valid(x_, y_) and (x_, y_) not in self.visited and len(path) <= max_steps:
self.movements.append((x_, y_, path + [(x_, y_)]))
def get_visited(self):
return len(self.visited)
In [7]:
grid = Grid(width=50, height=50, number=1362)
maze = MazeSteps(start_x=1, start_y=1, end_x=31, end_y=39, grid=grid)
maze.solve(init=True, max_steps=50)
print(maze.get_visited())
print(maze)