Hi i am taking a A.I class and i was given this piece of code and i need to implement the Depth-First Search and Uniform Cost search algorithm in the code. I am new to python and don't really understand how to do this assignment. If anyone can please help me with this i appreciate it. would you also be able to add comments in the code as well

## Imports

import random

import time

from colorama import init

from colorama import Fore, Back, Style

## Functions

def printMaze(maze):

for i in range(0, height):

for j in range(0, width):

if (maze[i][j] == 'u'):

print(Fore.WHITE + str(maze[i][j]), end=" ")

elif (maze[i][j] == 'c'):

print(Fore.GREEN + str(maze[i][j]), end=" ")

else:

print(Fore.RED + str(maze[i][j]), end=" ")

print(' ')

# Find number of surrounding cells

def surroundingCells(rand_wall):

s_cells = 0

if (maze[rand_wall[0]-1][rand_wall[1]] == 'c'):

s_cells += 1

if (maze[rand_wall[0]+1][rand_wall[1]] == 'c'):

s_cells += 1

if (maze[rand_wall[0]][rand_wall[1]-1] == 'c'):

s_cells +=1

if (maze[rand_wall[0]][rand_wall[1]+1] == 'c'):

s_cells += 1

return s_cells

# A* Algorithm to find the shortest path from start to end

def AStar(maze, start, end):

# Create the open and closed sets

open_set = set([start])

closed_set = set()

# Create a dictionary to store the g_score for each cell

g_score = {start: 0}

# Create a dictionary to store the f_score for each cell

f_score = {start: abs(start[0]-end[0]) + abs(start[1]-end[1])}

# Create a dictionary to store the parent of each cell

parent = {}

while open_set:

# Find the cell with the lowest f_score

current = min(open_set, key=lambda x: f_score[x])

if current == end:

# If the current cell is the end cell, return the path

path = []

while current in parent:

path.append(current)

current = parent[current]

return path[::-1]

open_set.remove(current)

closed_set.add(current)

# Check the neighbors of the current cell

neighbors = [(current[0]-1, current[1]), (current[0]+1, current[1]), (current[0], current[1]-1), (current[0], current[1]+1)]

for neighbor in neighbors:

if neighbor[0] < 0 or neighbor[0] >= height or neighbor[1] < 0 or neighbor[1] >= width:

# Skip the neighbors that are out of bounds

continue

if neighbor in closed_set:

# Skip the neighbors that are already in the closed set

continue

## Main code

# Init variables

wall = 'w'

cell = 'c'

unvisited = 'u'

height = 11

width = 27

maze = []

# Initialize colorama

init()

# Denote all cells as unvisited

for i in range(0, height):

line = []

for j in range(0, width):

line.append(unvisited)

maze.append(line)

# Randomize starting point and set it a cell

starting_height = int(random.random()*height)

starting_width = int(random.random()*width)

if (starting_height == 0):

starting_height += 1

if (starting_height == height-1):

starting_height -= 1

if (starting_width == 0):

starting_width += 1

if (starting_width == width-1):

starting_width -= 1

# Mark it as cell and add surrounding walls to the list

maze[starting_height][starting_width] = cell

walls = []

walls.append([starting_height - 1, starting_width])

walls.append([starting_height, starting_width - 1])

walls.append([starting_height, starting_width + 1])

walls.append([starting_height + 1, starting_width])

# Denote walls in maze

maze[starting_height-1][starting_width] = 'w'

maze[starting_height][starting_width - 1] = 'w'

maze[starting_height][starting_width + 1] = 'w'

maze[starting_height + 1][starting_width] = 'w'

while (walls):

# Pick a random wall

rand_wall = walls[int(random.random()*len(walls))-1]

# Check if it is a left wall

if (rand_wall[1] != 0):

if (maze[rand_wall[0]][rand_wall[1]-1] == 'u' and maze[rand_wall[0]][rand_wall[1]+1] == 'c'):

# Find the number of surrounding cells

s_cells = surroundingCells(rand_wall)

if (s_cells < 2):

# Denote the new path

maze[rand_wall[0]][rand_wall[1]] = 'c'

# Mark the new walls

# Upper cell

if (rand_wall[0] != 0):

if (maze[rand_wall[0]-1][rand_wall[1]] != 'c'):

maze[rand_wall[0]-1][rand_wall[1]] = 'w'

if ([rand_wall[0]-1, rand_wall[1]] not in walls):

walls.append([rand_wall[0]-1, rand_wall[1]])

# Bottom cell

if (rand_wall[0] != height-1):

if (maze[rand_wall[0]+1][rand_wall[1]] != 'c'):

maze[rand_wall[0]+1][rand_wall[1]] = 'w'

if ([rand_wall[0]+1, rand_wall[1]] not in walls):

walls.append([rand_wall[0]+1, rand_wall[1]])

# Leftmost cell

if (rand_wall[1] != 0):

if (maze[rand_wall[0]][rand_wall[1]-1] != 'c'):

maze[rand_wall[0]][rand_wall[1]-1] = 'w'

if ([rand_wall[0], rand_wall[1]-1] not in walls):

walls.append([rand_wall[0], rand_wall[1]-1])

# Delete wall

for wall in walls:

if (wall[0] == rand_wall[0] and wall[1] == rand_wall[1]):

walls.remove(wall)

continue

# Check if it is an upper wall

if (rand_wall[0] != 0):

if (maze[rand_wall[0]-1][rand_wall[1]] == 'u' and maze[rand_wall[0]+1][rand_wall[1]] == 'c'):

s_cells = surroundingCells(rand_wall)

if (s_cells < 2):

# Denote the new path

maze[rand_wall[0]][rand_wall[1]] = 'c'

# Mark the new walls

# Upper cell

if (rand_wall[0] != 0):

if (maze[rand_wall[0]-1][rand_wall[1]] != 'c'):

maze[rand_wall[0]-1][rand_wall[1]] = 'w'

if ([rand_wall[0]-1, rand_wall[1]] not in walls):

walls.append([rand_wall[0]-1, rand_wall[1]])

# Leftmost cell

if (rand_wall[1] != 0):

if (maze[rand_wall[0]][rand_wall[1]-1] != 'c'):

maze[rand_wall[0]][rand_wall[1]-1] = 'w'

if ([rand_wall[0], rand_wall[1]-1] not in walls):

walls.append([rand_wall[0], rand_wall[1]-1])

# Rightmost cell

if (rand_wall[1] != width-1):

if (maze[rand_wall[0]][rand_wall[1]+1] != 'c'):

maze[rand_wall[0]][rand_wall[1]+1] = 'w'

if ([rand_wall[0], rand_wall[1]+1] not in walls):

walls.append([rand_wall[0], rand_wall[1]+1])

# Delete wall

for wall in walls:

if (wall[0] == rand_wall[0] and wall[1] == rand_wall[1]):

walls.remove(wall)

continue

# Check the bottom wall

if (rand_wall[0] != height-1):

if (maze[rand_wall[0]+1][rand_wall[1]] == 'u' and maze[rand_wall[0]-1][rand_wall[1]] == 'c'):

s_cells = surroundingCells(rand_wall)

if (s_cells < 2):

# Denote the new path

maze[rand_wall[0]][rand_wall[1]] = 'c'

# Mark the new walls

if (rand_wall[0] != height-1):

if (maze[rand_wall[0]+1][rand_wall[1]] != 'c'):

maze[rand_wall[0]+1][rand_wall[1]] = 'w'

if ([rand_wall[0]+1, rand_wall[1]] not in walls):

walls.append([rand_wall[0]+1, rand_wall[1]])

if (rand_wall[1] != 0):

if (maze[rand_wall[0]][rand_wall[1]-1] != 'c'):

maze[rand_wall[0]][rand_wall[1]-1] = 'w'

if ([rand_wall[0], rand_wall[1]-1] not in walls):

walls.append([rand_wall[0], rand_wall[1]-1])

if (rand_wall[1] != width-1):

if (maze[rand_wall[0]][rand_wall[1]+1] != 'c'):

maze[rand_wall[0]][rand_wall[1]+1] = 'w'

if ([rand_wall[0], rand_wall[1]+1] not in walls):

walls.append([rand_wall[0], rand_wall[1]+1])

# Delete wall

for wall in walls:

if (wall[0] == rand_wall[0] and wall[1] == rand_wall[1]):

walls.remove(wall)

continue

# Check the right wall

if (rand_wall[1] != width-1):

if (maze[rand_wall[0]][rand_wall[1]+1] == 'u' and maze[rand_wall[0]][rand_wall[1]-1] == 'c'):

s_cells = surroundingCells(rand_wall)

if (s_cells < 2):

# Denote the new path

maze[rand_wall[0]][rand_wall[1]] = 'c'

# Mark the new walls

if (rand_wall[1] != width-1):

if (maze[rand_wall[0]][rand_wall[1]+1] != 'c'):

maze[rand_wall[0]][rand_wall[1]+1] = 'w'

if ([rand_wall[0], rand_wall[1]+1] not in walls):

walls.append([rand_wall[0], rand_wall[1]+1])

if (rand_wall[0] != height-1):

if (maze[rand_wall[0]+1][rand_wall[1]] != 'c'):

maze[rand_wall[0]+1][rand_wall[1]] = 'w'

if ([rand_wall[0]+1, rand_wall[1]] not in walls):

walls.append([rand_wall[0]+1, rand_wall[1]])

if (rand_wall[0] != 0):

if (maze[rand_wall[0]-1][rand_wall[1]] != 'c'):

maze[rand_wall[0]-1][rand_wall[1]] = 'w'

if ([rand_wall[0]-1, rand_wall[1]] not in walls):

walls.append([rand_wall[0]-1, rand_wall[1]])

# Delete wall

for wall in walls:

if (wall[0] == rand_wall[0] and wall[1] == rand_wall[1]):

walls.remove(wall)

continue

# Delete the wall from the list anyway

for wall in walls:

if (wall[0] == rand_wall[0] and wall[1] == rand_wall[1]):

walls.remove(wall)

# Mark the remaining unvisited cells as walls

for i in range(0, height):

for j in range(0, width):

if (maze[i][j] == 'u'):

maze[i][j] = 'w'

# Set entrance and exit

for i in range(0, width):

if (maze[1][i] == 'c'):

maze[0][i] = 'c'

break

for i in range(width-1, 0, -1):

if (maze[height-2][i] == 'c'):

maze[height-1][i] = 'c'

break

# Print final maze

printMaze(maze)