$ mkdir ~/cs170/labs/lab25 $ cd ~/cs170/labs/lab25
It's that time to submit your Pseudo-code for the word families for Evil Hangman. Don't forget to get any last minute questions about this part of the assignment out of the way now, since I will not be answering any questions about this after today.
Stacks allow us to write recursive code iteratively, since we can mimic the system stack. When we used stacks for the paint bucket program, you all noticed some weird patterns that emerged, if something were to go wrong with the system. A data structure related to Stacks are Queues. Maybe Queues will fix that peculiar pattern you all noticed last week?
Queues are referred to as First In-First Out, or FIFO, data
structures. The data you retrieve is always the oldest
from within the data structure. For example,
the line of people waiting to get their food at the Commons is a
queue. We are again going to use
our LinkedList to accomplish this goal.
To start off, download
my LinkedList
module. Place this file in your lab25 directory, so you can
use it in your queue definition.
Create a new file called queue.py. In this file, you should
define a class Queue, which will inherit the linked list
class. You will need to import linked_list at the top of
your file so that you can have access to the LinkedList class.
Your class must have the three key methods for a queue, plus two additional methods for testing purposes:
enqueue - Takes data as a parameter, and
adds it to the end of the queue.
dequeue - Removes the node from the front of the queue,
and returns its data.
peek - Returns the data from the node at the front
of the queue without removing it.
size - Returns an integer, the number of items
currently in the stack.
__str__ - Returns a string representation of the
queue.
Make sure that your methods work appropriately. You should handle the
special cases in dequeue and peek, when there is
nothing currently in the queue by
raise-ing
a ValueError exception.
>>> my_queue = Queue() >>> my_queue.enqueue(1) >>> my_queue.enqueue(2) >>> my_queue.enqueue(3) >>> print(my_queue) Front -> 1 -> 2 -> 3 -> End >>> print(my_queue.peek()) 1 >>> print(my_queue.dequeue()) 1 >>> print(my_queue) Front -> 2 -> 3 -> End >>> my_queue.dequeue() >>> print(my_queue) Front -> 3 -> End >>> my_queue.dequeue() >>> print(my_queue) Front -> End >>> my_queue.dequeue() Traceback (most recent call last): File "queue.py", line 64, inmy_queue.dequeue() File "queue.py", line 24, in dequeue raise ValueError("Queue is empty!") ValueError: Queue is empty!
Notice that dequeue is almost exactly the same as
pop was from your Stack exercises. The code for dequeue
should look exactly the same.
peek is also exactly the same as in stacks as well.
enqueue is a little bit more complicated. Our
append method currently only adds to the front of a linked
list. However, we don't want to add to the front of the
linked list. We want to add to the end.
You could use the insert method, but the code for
insert is a little more complicated than is really necessary
to accomplish enqueue. Instead of just
using insert, you should write this method from
scratch. Simply traverse the list until you find the current
end of the list. Then add a new node at the end.
As you might have noticed, the enqueue operation as
it stands is a O(n) operation. That is fine for small
list sizes, but is undesirable once list sizes become large. This
is especially true in comparison to Stacks, which have
a O(1) push and pop operation.
We can fix this by adding a tail reference to our linked
list. The tail will operate under the invariant that it
always refers to the last node in the list, or None if
the list is empty. Modify the LinkedList class, so
that all of the operations handle the tail attribute
accordingly. You will also need to modify
your enqueue method of Queue.
You have been solving for a majority of your lives by this point. You are probably aware that there are systematic mechanisms for finding the exit of the maze. Typically, we are looking for the shortest path out of a maze. Luckily, using a Queue, we can quickly find this path.
The file maze.py contains a simply maze traversal program. The maze is simply represented by a 2-dimensional list of integers, either 0 or 1. 0 means the cell is empty, while 1 means the cell is occupied.
The can_traverse(self, start_cell, end_cell method of
the Maze class takes two tuples as parameters: the starting location
and ending location in the maze. This method should
return True if there exists a path, and False if a
path does not exist. You will use a queue and a loop in order to
determine this. This seems pretty complicated, but the code for
this is fairly short. If you get stuck, don't forget to check the
hint section below.
What is the Big-Oh complexity of this method? Let n = WIDTH * HEIGHT = the number of cells in the map. Write up an analysis of the complexity in the comments of maze.py
$ python3 maze.py Actual: True Expected: True Actual: False Expected: False Actual: True Expected: True Actual: False Expected: False
You need to create a queue, and initialize it with some value. A good starting value would be the starting cell of the path.
In your loop, you will dequeue a tuple out of
the queue. This is the cell you are exploring. You should
mark the cell as VISITED, and add all of the
unvisited neighbors to the queue.
If you are exploring the end cell, then a path exists and you return True. If the queue ever becomes empty without finding the end cell, you should return False.
You might notice that we didn't use recursion for this. However, it is still very possible to write this recursively. As a matter of fact, there are two ways you can write this method recursively.
The first way to write it recursively is very similar to how the
paint bucket program worked before you got hold of it. Write a
method can_traverse_recursive(self, current_cell,
ending_cell), which takes as
parameters the current cell and the ending cell. This should
return the same values as before. Does this explore more cells
than the above code?
The other recursive function is to use a queue, just perform the
loop recursively. Write a
method can_traverse_rec_queue(self, queue, end_cell),
which takes a queue of tuples, and the ending cell as parameters.
You will have to write a helper
function can_traverse_rec_queue_helper(self, start_cell,
end_cell), which initializes the queue and calls the real
recursive function. Does this method work as well as the previous
method?
When you have finished, create a tar file of your lab25
directory. To create a tar file, execute the following commands:
cd ~/cs170/labs tar czvf lab25.tgz lab25/
To submit your activity, go to cseval.roanoke.edu. You should
see an available assignment called Lab Assignment 25.
Make sure you include a header listing the authors of the file.