programming abstractions and methods

Problem

Part 0: A linked list implementation of the priority queue ADT

The priority queue ADT is a queue, but one where every item stored in it has a priority (thus the name priority queue). It is probably not hard to come up with examples where you (and other people) have been waiting for some kind of service, but people are taken not in first-come, first-serve order (as in a regular queue), but according to some priority (for example, most serverely ill in an emergency room).

You will implement a priority queue in a class called PriorityQueue in the file priority_queue_linked.py, which is in the code repository. Your implementation must use a linked list, and it must maintain the property that the highest priority item is at the front of the linked list, down to the lowest priority item at the back of the linked list. If two items have the same priority, then the first item placed into the list should be closer to the front of the list.

To compare the priority of two items, use the < operator. So any programmer using your PriorityQueue class to store objects of some class, must have implemented the < operator (using the __lt__() method) in their class in order for the PriorityQueue class to work properly. You might find yourself wanting to use the <= or > or >= operators, but the convention is to do your implementation with just the < operator. Interestingly, by convention in programming, when a < b when comparing priorities, a has the higher priority. So smaller priority number means higher priority.

The method of the PriorityQueue class that you must implement are: (and the headers are given to you in priority_queue_linked.py.

1. __init(self)__ – Initialize the priority queue
2. isEmpty(self) – Returns True if the priority queue is empty, and False if not
3. size(self) – Returns the number of elements in the priority queue.
4. delete_min(self) – Removes and returns the item in the priority queue with highest priority. (And that is the smallest item in the list. See comment above.)
5. insert(self, item) – Insert item into the priority queue.

Some notes on your implementation:

1. You must implement the priority queue using a linked list, and your implementation must maintain the list in sorted order, from smallest item (the item with highest priority) at the front, to biggest item (the item with lowest priority) at the back. Ties (items with equal value) go to the item that was first inserted. So if items a and b have equal value, then a should be before b in the list.
2. Use the linked list implementation of the list ADT (in linked_list.py) that we wrote in class to get ideas for your code.
3. To implement insert(self, item), start at the front of the list, iterate down the list looking for the insert point, and once found, put the item in. Look at the insert method of the LinkedList (in linked_list.py) to remind yourself of how to iterate down a linked list, with insertion in mind. Be sure to keep in mind special (boundary) cases, similar to the boundary cases of the LinkedList class.
4. To implement delete_min(self), you are just removing and returning the item at the front of the list. But keep in mind special (boundary) cases.

To test your PriorityQueue class, run the program test_priority_queue_linked.py, and look for the message that your code passes the tests. If you get this message, move on to Part 1 below, and if not, go back and debug.

Part 1: Representing the Maze

First let’s talk about your basic maze. We will represent a maze as a 2D grid of cells, where each cell is either open, a wall, the start cell, or the finish cell. Below is a graphical representation of such a maze:

It has walls and pathways, it has one starting point, and it has one finish point. The walls in this representation are made up of the black cells, and the pathways the white cells. The start cell is green, and the finish cell is red.

The job of your program will be to find (and display) a path from the start cell to the finish cell.

You must first read a description of the maze from a file, which will have the following format: The first line of the file contains two integers (separarted by one or more spaces). The first indicates the number of rows (R), and the second the number of columns (C).

The remainder of the file will consist of R lines, each containing C integers (the C integers on a line are separated by one or more spaces). The value of the integers will be as follows:

0 - an empty space
1 - a wall
2 - the start 
3 - the finish

In terms of coordinates, consider the upper left corner to be in row 0 and column 0, and the lower right corner to be in row R - 1 and column C - 1.

For example, this is the text version of the maze above (start is at [6,4] and finish at [6,11]).

7 13
0 0 0 0 0 0 1 0 0 0 0 0 0
1 1 0 1 1 1 1 1 1 1 0 1 0
0 1 0 0 0 0 0 0 0 0 0 1 0
0 1 0 1 1 0 0 1 1 1 0 1 0
0 0 0 1 0 0 0 0 0 1 0 1 0
0 1 1 1 1 1 0 1 0 1 0 1 0
0 0 0 0 2 0 0 1 0 0 1 3 0

Once you understand how a maze is represented in a text file, you need to decide how to represent in memory. First, you will define a Cell class that will represent one cell of the maze. Cell will need to have the instance variables listed below. (The need for the row and column instance variables will be apparent later. Note that you will be adding more instance variables to this class for Part 2 of the assignment.)

• row: the row index of the cell within the maze
• col: the column index of the cell within the maze
• state: the type of cell (wall, open, start, or finish)

Your Cell class should have

class Cell:
    """ Represents a single cell in the maze. """
    def __init__(self, row, col, value):
        """ Initializes a cell.  Coordinates are (row, col).  The meaning of value
        is: 0 - empty space, 1 - wall, 2 - start, 3 - finish 
        """

    def __str__(self):
        """ Returns string representation of the cell.  Returns
        the string representation of the state instance variable,
        which is: `_` - empty space, `#` - wall, `S` - start, `F` - finish 
        """

Next, define a Maze class to store the entire maze. In the next part of this assignment, the Maze class will also solve the maze. The Maze class should have the following instance variables:

• num_rows: the number of rows in the maze grid.
• num_cols: the number of columns in the maze grid.
• maze: the actual maze, stored as a list of lists of cells. Each list is a row of the maze, so self.maze[r][c] is the cell in row r and column c of the maze.
• start: the cell that is the start of the maze.
• finish: the cell that is the finish of the maze.

Your Maze class should have: (more to be added later)

class Maze:
    def __init__(self, filename):
        """
        Opens filename and reads a maze from it.  Initialize num_rows, num_cols, maze, start, and finish.
        If file cannot be opened, print the message `File filename could not be opened.` (Here, replace filename with
        the actual name of the file.)
        Also, print out the maze to the terminal, using the print method with step = 0 parameter.
        """

    def print(self, step):
        """
        Print the current state of the maze to the terminal, labeled with the specified 
        step of the solution process.  (The format of the output is described below.)
        """

The format of the display of the maze is illustrated here. Note that this is for the same maze as is displayed above in graphical form and in its file format.

Step = 0
______#______
##_#######_#_
_#_________#_
_#_##__###_#_
___#_____#_#_
_#####_#_#_#_
____S__#__#F_

So the display of each cell is as follows:

`_` - an empty space
`#` - a wall
`S` - the start 
`F` - the finish

Note that you can use the __str__ method of the Cell class to display each cell, because that method returns the same value as is specified here. (Remember that when you call, for example, str(cell) the Python interpreter calls the __str__ method on cell.

Also remember here if you call, for example, print("Hello", end=''), a newline character is not displayed after Hello. You can then print a newline character by calling print() with no parameters.

I will be testing your code with software, so the output of your program must exactly match the correct output. So be sure to format your output as described above.

The test_mazes directory of the PSA2 repository contains a number of different maze files. Each starts with the word maze (and doesn’t have the string Sol in its name). Corresponding to each maze file is a file that contains what should be printed by Part 1 of your assignment. The names of these files are the name of the maze file with SolPart1 appended. For example, if the maze filename is maze-4, the name of the solution file is maze-4SolPart1.

To check your code, run the program test_maze_display.py. This program

1. Iterates over all of the maze files in the test_mazes directory, and for each test maze
2. Creates a Maze object using the Maze class constructor in your code (in maze_solve.py),
3. Prints out the Maze object using the print method of your Maze class.
4. Compares what is printed by your code with what should be printed.

If your code correctly displays all test mazes, you will get a positive message from the test program, and you can move on to Part 2 of the assignment. Otherwise, debug your code until you do.

When you are first testing your code, you can temporarily edit test_maze_display.py so that it only tries a subset of the mazes. (I suggest trying them in order.) Do this by editing the loop range on line 35. Be sure to restore test_maze_display.py before going on to Part 2.

Part 2: Solving the Maze

In this part of the program you will write the solve(self, method) method of the Maze class that solves the maze, and returns the path from the start cell to the finish cell, or returns the string No solution if the maze has no solution.

The method parameter of solve indicates the kind of worklist (worklist is described below in the algorithm description) that the algorithm should use, and is either "stack", "queue", or "priority_queue".

Here, in pseudocode, is the algorithm for solving the maze:

At the start:

1. You will start your search (for the finish cell) from the start cell.
2. Create an empty worklist (a stack, queue, or priority_queue, depending on the method parameter of the solve method) to hold cells that you you have reached, but have not yet explored from.
   Initialize this data structure to contain the start cell.
3. Start a counter (at 0) of the number of steps the algorithm has taken. (A step will be one iteration of the instructions below.)

Keep repeating the following instructions until the algorithm terminates (because you’ve reached the finish cell, or determined that no such path exists):

1. Increment the count of the number of steps the algorithm has taken.
2. Is the worklist empty? If it is, the finish is unreachable, and terminate the algorithm.
3. Otherwise, from the worklist get the “next” cell (called next_cell here) that you will now explore.
4. For each of the cell c adjacent to next_cell (in the order up, right, down, left – and order is important to get the right answer), do the following:
   1. If c exists, and the cell is not a wall, and the cell has not previously been put on the worklist, then
      1. Make next_cell the previous cell for c (to remember how you got to c).
      2. If c is the finish cell, then you have found a path. You should
         • Compute the path from start to finish, marking every cell on the path (except the start and finish) as being on the solution path.
         • Print the final state of the maze.
         • Return the solution path.
      3. Else, Mark c has having been put on the worklist, and put it on the worklist.
5. Mark the cell next_cell has having been explored
6. Print the current state of the maze.

Some notes about this:

1. You have three new states that a cell can be in: a cell that starts out as open can change to being on the worklist, and then can change again to having been explored, and then can change again when it is identified as being on the solution path. You can use the same state instance variable of the Cell class that you already have to keep track of the changing state of a cell (from open -> on the worklist -> explored -> on solution path). Note that the start and finish cells never change their state.
2. To be able to create the solution path, once you’ve arrived at the finish cell, each cell should maintain a previous instance variable that references the cell from which the algorithm arrived at the cell (in step 4a1 of the algorithm).
3. As said above, the worklist that your algorithm uses can either be a stack, a queue, or a priority_queue.
   The repository has implementations of the stack (stack.py) and queue (queue_list.py), and in Part 0 of this assignment you implemented the priority queue (priority_queue_linked.py). The starter code already has imported all of these.
4. As the algorithm above makes clear, it is the cells of the maze that are placed on the worklist, and if the type of worklist is a priority queue, you have to be able to compare cells in order to determine their relative priority. You will do this by going into the Cell class (in maze_solver.py) and defining the method __lt__(self, other_cell). This returns True if the self cell is less than other_cell. What criteria will you use to compare cells? You will use their distance from the finish cell, where the distance is computed using the Manhattan distance. (You can Google this, but it is the sum of the distances to the finish cell along the x and y axes. So, for example, if a cell is at row 3 and column 5 of the maze, and the finish cell is at row 1 and column 8, the Manhattan distance is 5.) So if in __lt__(self, other_cell), self is closer to the finish than other_cell, True should be returned, and False otherwise. (So, in summary, the priority of a cell is based on its Manhattan distance to the finish cell.) For all cells in the maze, you should compute the distance to the finish cell one time when the maze is initialized, and store it in an instance variable of the Cell class. This way, you do not have to recompute the distance every time __lt__(self, other_cell) is called.And remember that in your PriorityQueue class, you use the < operator to compare items in the priority queue, and Python calls the __lt__ method when it encounters this.
5. When you print out the maze now, use the following symbols to represent the state of a cell:
   • _ – an empty space (not yet on the worklist)
   • o – an empty space on the worklist
   • . – an empty space that has been explored
   • X – an empty space that is on the solution path (this is a capital X)
   • # – a wall
   • S – the start
   • F – the finish

   To print out the maze, as before, print the step, and then the current state of the entire maze.

6. The solution path returned by your solve method should be a list of cells that are on the path starting with (and including) the start cell, and ending with (and including) the finish cell. Each cell on this list should be a tuple containing the row and column (in that order) of the cell. The previous field of each cell makes it straightforward to trace from the finish to the start, but you want a list starting from the start and going to the finish. A stack (different from the worklist stack) can be helpful here.

Suggestions:

1. You can write separate helper solve methods (e.g., solve_queue), one for each worklist type, and then have the main solve method called the appropriate helper method. There are other ways to handle the different worklist types, but this works.
2. It will be helpful for you to have a method of the Maze class called get_next_cells that takes as its parameter a cell, and returns the adjacent cells that are open (or the finish cell) that have not been put on the worklist yet. As said above, the order you should consider adjacent cells in is up, right, down, left. This will ensure that your output matches mine. Having a method that returns this list of cells will make it easier to write the loop in step 4 of the algorithm above.

To check your code, run the program test_maze_solver.py. This program

1. Iterates over all of the maze files in the test_mazes directory, and for each test maze
2. Creates a Maze object using the Maze class constructor in your code (in maze_solve.py),
3. Prints out the Maze object using the print method of your Maze class.
4. Compares what is printed by your code with what should be printed.
5. Solves the maze three times, once using a stack as a worklist, once using a queue, and once using a priority queue. For each of these, it checks what is printed (and returned) by your code against what it should be.

If your code correctly displays all test mazes, and correctly displays the solving of the maze for each worklist type, then you will get a positive message from the test program, and you can move on to submitting your code. Otherwise, debug your code until you do.

When you are first testing your code, you can temporarily edit test_maze_solver.py so that it only tries a subset of the mazes. (I suggest trying them in order.) Do this by editing the loop range on line 35. Be sure to restore test_maze_solver.py before submitting.

Looking for solution of this Assignment?

WHY CHOOSE US?

We deliver quality original papers	Our experts write quality original papers using academic databases.We dont use AI in our work. We refund your money if AI is detected
Free revisions	We offer our clients multiple free revisions just to ensure you get what you want.
Discounted prices	All our prices are discounted which makes it affordable to you. Use code FIRST15 to get your discount
100% originality	We deliver papers that are written from scratch to deliver 100% originality. Our papers are free from plagiarism and NO similarity.We have ZERO TOLERANCE TO USE OF AI
On-time delivery	We will deliver your paper on time even on short notice or  short deadline, overnight essay or even an urgent essay