What functions are there in the “mazeAsn4” module:

print_maze(maze)
Description: This function displays the maze. The accessible cells are labelled “G” i.e. green, the blocked cells are labelled “R” i.e. red, and the null cells are labelled “Y” i.e. yellow. The argument

“maze” is a string over an alphabet set “G”, “R”, “Y” that encodes the cell labels of the maze. Row labels of the maze are concatenated to form a single string that represents the maze, see figure 1.

create_maze(problem_num)
Description: This function creates and returns a “maze” string of size n × n.
When problem_num is 0: The function asks the user to input a valid value (>= 3) of maze size n. The function validates the value of n and returns a string “maze”. The value “0” should be used for problem 1.
When problem_num is 1: The function randomly generates and returns a maze string of size n × n, where 3 <= n <= 9. The value “1” should be used for problem 2.
When problem_num is any other number: The function will raise an error and stop the program execution.

get_source()
Description: This function returns the coordinates of the source cell as a list in the format [[“source_x : ”, a], [“source_y : ”, b]]. Here a, b are the x, y coordinates of the source cell.
Example:
[[“source_x : ”, 12], [“source_y : ”, 0]] represents a source cell at coordinates (12, 0).

get_destination()
Description: This function returns the coordinates of the destination cell as a list in the format [[“destin_x : ”,a],[“destin_y : ”,b]]. Here a, b are the x, y coordinates of the destination cell. Example:
[[“destin_x : ”,4],[“destin_y : ”,13]] represents a destination cell at coordinates (4,13).

Problem 1

Write a program in Python that performs the following tasks in order:

1. Using the functions of the “mazeAsn4” module, first create and print a new maze. Then, print the coordinates of the source and the destination cells in the format shown below:
Source coordinates: X: 0 Y: 1
Destination coordinates: X: 4 Y: 4

2. Create a function “compute_path” that computes and returns a list containing a valid condi- tional path from the source cell to the destination cell if there exists such a path. If a valid path does not exist, then the function should return an empty list. This function should have exactly three parameters: the first for the maze string returned from the “create_maze” function, the second for the list returned from the “get_source” function, and the third for the list returned from the “get_destination” function.

Note: Remember that any valid path can only go through the accessible “green” cells. For this problem, a path has to be valid and should follow the following additional conditions:

(a) Your function should compute the forward row-wise path if it exists i.e. at any step, you need to move from the current row to the next.

(b) You can not stay in the same row. Also, you can not go from a row with a higher index to a row with a lower index.

(c) There are no restrictions on the column-wise moves i.e. you can stay in the same column, move backward to the previous column, or move forward to the next column.

(d) To summarize, if the current cell is (i, j), then there are only three possible moves ahead: (i+1, j-1), (i+1, j), and (i+1, j+1).

Hint: You can use the following algorithm to compute a valid path: Algorithm compute_path(maze, src, dest)
#maze: maze string returned from the create_maze function
#src: list returned from the get_source function

#dest: list returned from the get_destination function
1 Create a list T and add source tuple as a list [(src_x, src_y)] to T

2 While T is not empty:

2.1 Remove the first list element E from T
2.2 Obtain last tuple (i,j) of sub-list E
2.3 Explore all 3 possible moves from (i,j) i.e. (i+1,j-1), (i+1,j), and (i+1,j+1)
2.4 For all valid moves, concatenate the valid moves to the sub-list E and add the newly

found partial paths to T
2.5 If any of the three moves leads to the destination cell, then we have found a valid

path; exit the loop with a successful path search
3 If a valid path is found, then return the path as a list; otherwise, return an empty list

3. Print the computed path in the format as shown in figure 3 if found, otherwise print “A valid path does not exist!”

Problem 2

This problem is the continuation of problem 1. You have already created the maze, printed the maze, obtained the coordinates of the source and the destination cells, and computed a valid conditional path if there exists such a path. Using the maze produced by the functions of the “mazeAsn4” module, write a program in Python that performs the following tasks in order:

1. Using the functions of the “mazeAsn4” module, create 10 mazes with valid paths. If the original maze (the one created in problem 1) has a valid path, then consider this as the first maze with a conditional valid path. If the original maze does not have a valid path, then repeatedly perform the following tasks until a maze with a valid path is found: create a new maze, get its source and destination cells, and compute a conditional valid path if there exists such a path (hint: make use of the code that you wrote for problem 1). Repeat the process to produce 10 mazes with valid paths.

2. Create a dictionary with maze numbers as keys and their respective valid paths as values. A key for any maze number X should be in the format “MazeX”, where 1 <= X <= 10.

3. Create a new text file “maze.txt” and write the dictionary created in step 2 into this text file. The contents of text file should be in the format as shown in figure 4. At the end of your program, print "Successfully created maze.txt with dictionary keys and values!".