CODE IN PYTHON PLEASE! ADD CODE IN MAZE.PY WHERE IT SAYS # YOUR CODE HERE TO MAKE IT WORK. DO NOT COPY FROM OTHER ANSWERS!! WILL UPVOTE

In this project, we will model a maze solving problem as a state space problem, which can then be solved using search.

Consider the following maze, drawn out using ASCII text:

############### #+..........#o# #####.#.#####.# #.....#....o#.# #.#####.#####.# #.....#.....#x# ############### 

This maze is an m n grid of cells, where we use the following symbols: a plus (+) denotes a player in the maze; a cross (x) denotes the goal cell; a dot (.) denotes an empty cell;

a hash (#) denotes a wall that the player cannot enter;

a circle (o) denotes a portal/teleporter which the player can use to teleport to another part of the maze Our goal is to find a shortest path that allows the player to reach the goal cell. The player can perform five

different actions: move UP a cell move DOWN a cell move LEFT a cell move RIGHT a cell or TELEPORT from one portal (o) to another portal (o)

The player cannot move into a cell containing a wall. The player can only teleport when they are occupying a cell containing a portal. In this project, a maze may either contain exactly two portals, or none at all.

a Maze class which is a simple class that will take in the definition of a maze as a string, and convert it into a matrix, which can be indexed using the at function. The at function takes in a coordinate (x, y) as input, and returns a symbol representing the cell of the maze (i.e., whether it is empty, a wall, etc.)

a MazeState class which is simply just a maze and a position for the player (this suffices to define the state of a player in a maze).

a MazeProblem class, which is incomplete. The goal of this project is to complete this definition of a maze problem, so that it can be solved by one of the search algorithms already included in the AIMA repository. Once properly implemented, the included test.py script will run tests over multiple different mazes, each time showing the maze, the solution found, and the number of steps (actions) required to solve the maze (each action counts as one step).

maze.py

------------------------------------------------------------------------------

from search import Problem

"""Basic class for representing a maze.

Each maze cell is one of the following:

. is an empty cell

x is a goal

# is a wall

o is a teleporter (there are exactly two teleporter locations, or none)

"""

class Maze:

def __init__(self,maze_string,maze_size):

"""define the maze using a string, and the maze width and height"""

width,height = maze_size

maze_string = "".join(maze_string.split()) # this removes whitespace

assert len(maze_string) == width*height # sanity check

# convert the maze definition of a string to a 2D matrix

self.matrix = self._string_to_matrix(maze_string,maze_size)

self.maze_size = maze_size

# record the positions of the two teleporters (if they exist)

self.teleporters = [ i for i,c in enumerate(maze_string) if c == 'o' ]

self.teleporters = [ (i//width,i%width) for i in self.teleporters ]

# sanity check

assert len(self.teleporters) == 0 or len(self.teleporters) == 2

def __repr__(self,position=None):

"""this function re-draws the maze, possibly using a '+' marker

to denote the position of a player, if the position is given"""

if position is not None:

x,y = position

# save the original marker

marker = self.matrix[x][y]

# overwrite the position with the player marker

self.matrix[x][y] = '+'

# draw maze as string

st = " ".join( "".join(row) for row in self.matrix )

# restore the original marker

if position is not None:

self.matrix[x][y] = marker

return st

def at(self,position):

"""returns the symbol at the maze location position=(x,y).

the symbol can be either:

. (an empty cell)

x (a goal cell)

# (a wall)

o (a teleporter)

"""

x,y = position

return self.matrix[x][y]

def _string_to_matrix(self,string,size):

w,h = size

"""convert string into a character matrix of width w and height h"""

# turn the string into an array of rows

# where each row is a sub-string

mat = [ string[i*w:(i+1)*w] for i in range(h) ]

# break each row into an array

mat = [ list(row) for row in mat ]

return mat

"""This class keeps track of a maze, and a player's position inside of

the maze. When the state is printed, the player's position is denoted

with a + character"""

class MazeState:

def __init__(self,maze,position):

self.maze = maze

self.position = position

def __repr__(self):

return self.maze.__repr__(position=self.position)

"""This class defines a maze problem."""

class MazeProblem(Problem):

def __init__(self, initial):

"""A problem is initialized by its initial state.

This function does not need to be modified."""

super().__init__(initial)

def actions(self, state):

"""Give a maze state, we need to return a list of valid actions"""

# we have five possible actions

possible_actions = ['UP', 'DOWN', 'LEFT', 'RIGHT', 'TELEPORT']

x,y = state.position

# we need to move any possible action that is

# invalid based on the current state of the maze

# YOUR CODE HERE

raise Exception("IMPLEMENT THIS FUNCTION") # comment this out

return possible_actions

def result(self, state, action):

"""Given a maze state and a valid action, return the resulting

state found by applying the action"""

x,y = state.position

# YOUR CODE HERE

raise Exception("IMPLEMENT THIS FUNCTION") # comment this out

return MazeState(state.maze,new_position)

def goal_test(self, state):

"""Return true if the given state is a goal state and return

false otherwise"""

# YOUR CODE HERE

raise Exception("IMPLEMENT THIS FUNCTION") # comment this out

pass

------------------------------------------------------------------------------

test.py

------------------------------------------------------------------------------

#from search import breadth_first_graph_search as Searcher

from search import iterative_deepening_search as Searcher

from maze import *

def run_test(maze,starting_position,expected_cost):

state = MazeState(maze,starting_position)

problem = MazeProblem(state)

solution = Searcher(problem)

print("maze:")

print(state)

print("solution:")

print(solution.solution())

print("cost: %d (expected %d)" % (solution.path_cost,expected_cost) )

if solution.path_cost != expected_cost:

print("==== TEST FAILED ====")

return 0

return 1

# count how many tests pass

passed = 0

total = 4

print("""

########################################

# TEST 1

########################################

""")

maze_string = """

#######

#.....#

#.....#

#.....#

#.....#

#....x#

#######

"""

maze = Maze(maze_string,(7,7))

starting_position = (1,1)

expected_cost = 8

passed += run_test(maze,starting_position,expected_cost)

print("""

########################################

# TEST 2

########################################

""")

maze_string = """

#######

#.....#

#....o#

#######

#....o#

#x....#

#######

"""

maze = Maze(maze_string,(7,7))

starting_position = (1,1)

expected_cost = 11

passed += run_test(maze,starting_position,expected_cost)

print("""

########################################

# TEST 3

########################################

""")

maze_string = """

###############

#...........#o#

#####.#.#####.#

#.....#....o#.#

#.#####.#####.#

#.....#.....#x#

###############

"""

maze = Maze(maze_string,(15,7))

starting_position = (1,1)

expected_cost = 17

passed += run_test(maze,starting_position,expected_cost)

print("""

########################################

# TEST 4

########################################

""")

maze_string = """

###########

#x.......x#

#.........#

#.........#

#.........#

#o.......o#

#.........#

#.........#

#.........#

#x.......x#

###########

"""

maze = Maze(maze_string,(11,11))

starting_position = (5,5)

expected_cost = 8

passed += run_test(maze,starting_position,expected_cost)

print("====")

print("%d/%d TESTS PASSED" % (passed,total))

------------------------------------------------------------------------------