My file name is maze1.txt which has the maze made in it. I want to solve the maze using dfs and have made stack and queue frontiers for it with various functions. Originally, this code was in .py and i tried to change it to .ipynb. I keep getting ValueError: No axis named A for object type DataFrame. I don't know how to correct this. The following is the code i have come up with so far. I don't know how to call the Maze class and proceed further to get a result. I am very new at this..
import sys
from sys import argv
import os
import pandas as pd
# Class node that keeps track of state, the state of state (parent) and action. No path cost as we can calculate it in the end.
class Node():
def __init__(self, state, parent, action):
self.state = state
self.parent = parent
self.action = action
# Stack Frontier class that generates objects. We create object and fns on the object that stores all the data of frontier
class StackFrontier():
def __init__(self): # Creates a frontier which is empty
self.frontier = []
def add(self, node): # Adding nodes to frontier
self.frontier.append(node)
def contains_state(self, state): # Checks the state of the frontier
return any(node.state == state for node in self.frontier)
def empty(self): # Checks if frontier is empty, if it is empty the length of the frontier is zero.
return len(self.frontier) == 0
def remove(self): # Remove something from frontier after checking if it's empty or not
if self.empty():
raise Exception("empty frontier")
else:
node = self.frontier[-1] # Removes last item of the list (LIFO Structure)
self.frontier = self.frontier[:-1] # Updating the frontier to say that go ahead and remove the node that was removed from frontier
return node
# Queue Frontier class like Stack frontier. This inherits Stack's functions. We only readjust the remove function into FIFO
class QueueFrontier(StackFrontier):
def remove(self):
if self.empty():
raise Exception("empty frontier")
else:
node = self.frontier[0] # Removes first item of the list (FIFO Structure)
self.frontier = self.frontier[1:] # Updation of frontier
return node
class Maze():
# Takes a txt file as an input
def __init__(self, filename):
# Read file and set height and width of maze
file_path = 'maze1.txt'
contents = pd.read_csv(file_path, delimiter = "\t")
# Validate start and goal
if contents.count("A") != 1:
raise Exception("maze must have exactly one start point")
if contents.count("B") != 1:
raise Exception("maze must have exactly one goal")
# Determine height and width of maze
contents = contents.splitlines()
self.height = len(contents)
self.width = max(len(line) for line in contents)
# Keep track of walls
self.walls = []
for i in range(self.height):
row = []
for j in range(self.width):
try:
if contents[i][j] == "A":
self.start = (i, j)
row.append(False)
elif contents[i][j] == "B":
self.goal = (i, j)
row.append(False)
elif contents[i][j] == " ":
row.append(False)
else:
row.append(True)
except IndexError:
row.append(False)
self.walls.append(row)
self.solution = None
def print(self):
solution = self.solution[1] if self.solution is not None else None
print()
for i, row in enumerate(self.walls):
for j, col in enumerate(row):
if col:
print("█", end="")
elif (i, j) == self.start:
print("A", end="")
elif (i, j) == self.goal:
print("B", end="")
elif solution is not None and (i, j) in solution:
print("*", end="")
else:
print(" ", end="")
print()
print()
def neighbors(self, state):
row, col = state
candidates = [
("up", (row - 1, col)),
("down", (row + 1, col)),
("left", (row, col - 1)),
("right", (row, col + 1))
]
result = []
for action, (r, c) in candidates:
if 0 <= r < self.height and 0 <= c < self.width and not self.walls[r][c]:
result.append((action, (r, c)))
return result
def solve(self):
"""Finds a solution to maze, if one exists."""
# Keep track of number of states explored
self.num_explored = 0
# Initialize frontier to just the starting position
start = Node(state=self.start, parent=None, action=None)
frontier = StackFrontier() # DFS Algo used here
frontier.add(start) # Has start state
# Initialize an empty explored set
self.explored = set() # Explore set
# Keep looping until solution found
while True: # The repeat part
# If nothing left in frontier, then no path
if frontier.empty():
raise Exception("no solution")
# Choose a node from the frontier
node = frontier.remove()
self.num_explored += 1 # Adding one to the number of states explored
# If node is the goal, then we have a solution
if node.state == self.goal:
actions = []
cells = []
# Follow parent nodes to find a solution
while node.parent is not None:
actions.append(node.action)
cells.append(node.state)
node = node.parent
actions.reverse()
cells.reverse()
self.solution = (actions, cells)
return
# Mark node as explored
self.explored.add(node.state)
# Add neighbors to frontier (Exploration)
for action, state in self.neighbors(node.state):
if not frontier.contains_state(state) and state not in self.explored:
child = Node(state=state, parent=node, action=action)
frontier.add(child)
def output_image(self, filename, show_solution=True, show_explored=False):
from PIL import Image, ImageDraw
cell_size = 50
cell_border = 2
# Create a blank canvas
img = Image.new(
"RGBA",
(self.width * cell_size, self.height * cell_size),
"black"
)
draw = ImageDraw.Draw(img)
solution = self.solution[1] if self.solution is not None else None
for i, row in enumerate(self.walls):
for j, col in enumerate(row):
# Walls
if col:
fill = (40, 40, 40)
# Start
elif (i, j) == self.start:
fill = (255, 0, 0)
# Goal
elif (i, j) == self.goal:
fill = (0, 171, 28)
# Solution
elif solution is not None and show_solution and (i, j) in solution:
fill = (220, 235, 113)
# Explored
elif solution is not None and show_explored and (i, j) in self.explored:
fill = (212, 97, 85)
# Empty cell
else:
fill = (237, 240, 252)
# Draw cell
draw.rectangle(
([(j * cell_size + cell_border, i * cell_size + cell_border),
((j + 1) * cell_size - cell_border, (i + 1) * cell_size - cell_border)]),
fill=fill
)
img.save(filename)
I expect the program to run smoothly and be able to call the functions with the Maze1.txt file. This code should solve the Maze problem using DFS but in a jupyter notebook.