Assignment 8

Harvey Mudd College
Computer Science 42
Assignment 8, Due Monday, November 1, by 11:59pm

This assignment is proudly brought to you by Spam, the official canned meat product of CS 42. We strongly recommend that you do the three parts of this assignment in the order presented below. Parts 1 and 2 and the extra credit (both parts) can be done individually or in pairs. Parts 3 is individual only.

Provided code:

Spamsweeper.py - The starter code for problem 1
Spamsweeper.pyc - The compiled spamsweeper game. You can run it from the command line by calling "python Spamsweeper.py"
Queue.py - The starter code for problem 2
Maze.py - The starter code for problem 3
mazes.zip - maze files for use in problem 3

A Reminder on Style

Please keep in mind that at this point in the course some of the assignment points will be awarded based on your programs' commenting, formatting, and design -- under the heading of style.

Any readable and well-commented style is OK. These are some of the things to look out for when writing programs for yourself (or others) to read:

Design

For large programs, be sure to design your program on paper before you sit down at the computer. Think about what functions you will want and how they will interact with one another.
Each function should be fairly short and should have a clear "mission". Use helper functions of your own design, as needed or desired. Large, convoluted functions are difficult to read and understand -- more importantly, however, they're very difficult for the original programmer to modify and debug!
Avoid MAGIC VALUES! Recall from lecture that instance variables are appropriate in lieu of magic value. However, you should keep the number of these variables as small as possible.

Formatting

Please use ample whitespace: blank lines between functions, spaces within expressions to make them readable and separate component parts.
This also includes a clear and clear structure to your code, and indenting that indicates that structure.
You should use meaningful variable and function names. For example, use row rather than r and current rather than c.
You should keep your lines of code to less than 80 characters -- this helps to make it readable from within all kinds of programs, and avoids wrapping issues.

Comments

We ask you to include a top-of-file comment with your name, partner (if any), time spent, and any other comments for the graders (or instructors)
Each function, even your own helper functions, should have at least a short top-of-function comment documenting its purpose, inputs, and outputs.
Comments within functions are welcome, but not required unless something tricky is going on. Many people find them helpful to write because they keep the flow of the program in mind.

Part 1: Spamsweeper (35 Points, Individual or Pair), submitted in a file named Spamsweeper.py

First the utterly gratuitous story... You've been hired by Spamsoft, a major software company. Spamsoft would like to implement a "retro" version of the famous Minesweeper game which they call Spamsweeper. (By "retro" we mean that the game will be played on the keyboard and using text-based graphics rather than with a mouse and fancy graphics.)

Spamsoft is a big company, and one division of the company has already developed a few Python classes that will be of useful in your game. However, writing the actual game is your job. (In real software development projects, many people are usually involved and different teams will develop different pieces of the project. Therefore, this part of the assignment exposes you to the idea of using existing classes to write more sophisticated programs.)

The objective of the Spamsweeper game is to safely "defuse" all of the hidden cans of Spam. You will find a compiled version of our game on the top-level assignment page. You can play that game by double-clicking the file after you download it, or running it from the command line using python Spamsweeper.pyc.

At each iteration, you are asked for the row (number) and then column (letter) that you wish to play. Then, you are asked if it is Spam ('s') or free ('f'). If you choose 's' for Spam, there had better be a can of Spam at that location! If so, the cell is exposed and the Spam counter is decremented by one. If not, you lose. If you choose 'f' for free, there had better not be a can of Spam at that location. If there is a can of Spam there, you lose! If not, the cell is exposed. You win when there are no more cans left to find. That is, when you have exposed all non-spam cells OR all the spam cells (or both).

To get you started, download the files Spamsweeper.py from the top of this page. This file contains classes that have been provided for you by "another team" at the company. In a nutshell, the Boardcell class defines one cell of the board of a game. The cell keeps track of not just whether it is "mined" (i.e. contains a can of Spam) but also whether or not this cell should be exposed to the player (initially all cells are unexposed but they become exposed as the player selects them during the course of the game), and the number of surrounding cells that contain mines (Spam). Please read through this code carefully. Read the comments and the code and make sure that you understand what each class provides. Not only will you use these classes in your game, but some of the implementation ideas in this code will be useful to you in later parts of this assignments.

Note that one method (a function defined inside a class is called a "method") of particular utility is printBoard. This method displays the board for the user, hiding the contents of all of the cells that have not yet been exposed by the player and revealing all of the exposed cells. There is also a cheatPrintBoard method that exposes everything! This is useful when debugging your program. It will be handy for you to know where the Spam is located and what the neighor count values are so that you can see if your program is working correctly.

Your job is to write the Spamsweeper game. You need not define it as a class. Simply use the classes that Here are the requirements of the game and the implementation:

You should use the provided Boardcell and Gameboard classes without modification. Spamsoft has invested considerable energy developing and testing those classes and wants them to be used in their games.
The game should have the same functionality as the provided sample. As a reminder, you can run the provided sample by typing In particular it should start automatically when the user presses F5 (using the "main trick") and begin by asking the user to specify the number of desired rows, columns and cans of spam on a single line, allowing the user to simply hit <enter> to obtain the default values (12x12 board with 20 cans of spam). Also, please make sure to print the current status of the board and the number of spam cans remaining. Similarly, the game should report a win or loss appropriately.
You've seen how to read input from the console in class. Use the input and raw_input functions as appropriate.
An important part of your game is the "Auto Expose" feature. Here is how it works: If you select a cell and correctly defuse it as Spam or select a non-Spam cell and correctly identify it as "free", that cell should be marked as exposed (recall that the printBoard method only displays the contents of exposed cells). Moreover, if a free cell is exposed and it's neighbor count is 0, we know that none of its neighbors contains Spam. Therefore, there is no information revealed in exposing all of the neighbors of that cell, since the player would have done this her/himself. Each cell will have 8 neighbors in general, but possibly fewer if the cell is at an edge or corner of the board. The program therefore automatically exposes those neighbors. Moreover, if any of those cells are themselves ones with 0 neighbor count, then the automatic exposure recursively continues from there. Use recursion for the auto expose mechanism and try to keep that code as clean and simple as possible. It's possible to implement in just a few lines of code! In particular, try to avoid having a separate line of code for each of the eight possible neighbors that need to be looked at.

Submit your code as Spamsweeper.py, including the provided classes that were in this file originally.

Part 2: Comparing Queue Implementations (25 Points, Individual or Pair)

In this second part of the assignment, you will compare several implementations for the abstract data type (ADT) Queue. Your goal in this section is to compare the efficiencies of these implementations. You will compare the following three impementations:

A "raw" implementation that you will write from scratch
An implementation using Python's built-in lists
Python's own implementation of the Queue interface (i.e., an implementation using Python's deque class) [We have provided this implementation].

You should start with the file Queue.py, which is provided above. In that file we have defined the class DequeQ, which is a deque-based implementation of the Queue ADT. You will see that it implements the following methods:
def __init__(self):
''' Initialize a new empty queue. '''

    def __repr__(self):
        ''' Return a string representation of the queue.'''

    def getType(self):
        ''' Return the type of queue we've implemented as a string. (RawQ, DequeQ or ListQ)'''

    def enqueue(self, item):
        ''' Add an item to the queue.'''

    def dequeue(self):
        ''' Remove an item from the queue.'''

    def empty(self):
        ''' Return whether or not the queue is empty.'''

    def peek(self):
        ''' Look at the first item in the queue, but don't remove it.'''

You'll also see that there is a lot of other provided code. We'll talk about that in a minute.

Your task is to implement two new classes: RawQ and ListQ. To do so, you need to implement all of the methods above, for each of those two classes.

ListQ will be similar to DequeQ, but it will use a standard Python list to store its contents. (Note that you'll likely find Python's dir command that we have discussed in class useful to figure out what lists can do).

RawQ is a "from scratch" implementation of a queue as a linked list. It should be implemented as a linked list, like the Stack example we saw in class.

Helper class: QCell

Similar to the way in which the Stack class used an inner class named StackCell, your RawQ file might use a QCell class that will be the type of each cell in your RawQ.

Data members for RawQ

The RawQ class itself should have two data members (initialized in __init__)


self.front # the front of the RawQ object - cells are removed from here
self.back # the back of the RawQ object - cells are added to here

Format to use for __repr__

For uniformity of display, please use the following format when implementing your __repr__ method. Notice that <FRONT> and <BACK> always are printed, and <FRONT> always has a single space after it. When elements are present, they are printed from front-to-back, each with a single space after it, including the final element. <BACK>, however, does not have a space following it.

printing an empty queue: <FRONT> <BACK>
printing a queue whose elements are the Strings a, b, and c: <FRONT> a b c <BACK>

Testing your code is important! We have provided a simple tester function. Make sure that it works for your implementation. Also note that it does not test the __repr__ function. You should be sure to test that function too, possibly by adding it to the tester we've provided.

Profiling your implementations

Finally, the last part of problem 2 is to use the profiling code we provide to see which implementation is fastest. All you need to do is uncomment the relevant lines in the profiling part of the code and run it using F5 or via the command line.

In a comment at the top of your file (CLEARLY VISIBLE), comment on the results you see. Do they supprise you? How do you explain the differences you see? You don't have to go overboard here. A few sentences will do.

Part 3: A Breadth-First Maze Solver (aka "Spamseeker") (40 Points, Individual Only): submit in a file named Maze.py

This problem should be done individually. If you worked with a partner on the previous parts, you may use the Queue implementation that you wrote together. Or you may choose to use the built-in Python deque class.

You should start this problem with the Maze.py file provided above. You must run this file from the command line, passing the maze file as a command-line argument. E.g.:

% python Maze.py test1.maze

What is already in Maze?

Please read carefully through the provided Maze.py file. The Maze class has a method for reading a maze from a file. The format of the file should be something like this


6 10
**********
*S*      *    
* *      *    
*    **  *   
*    *D  *   
**********

where the first line has the height and width of the maze, and the subsequent lines contain the maze itself, as characters, with the asterisk '*' representing the walls, spaces are free space, and letters are special free space: 'S' is the start, and 'D' is the destination for the maze.

The Maze class also has a __repr__ method, a method named findMazeCell that will return a MazeCell that is holding a particular character (S or D, usually), and a main method for testing.

What needs to be implemented?

The method that needs to be implemented is

 BFS(self, start, destination)

This BFS method does not need to return a value. However, it needs to either

find a shortest solution to the maze by breadth-first search and then add lowercase-o characters 'o' to indicate the path between the start and destination OR
realize the maze is unsolvable and announce that fact by printing Maze not solvable!.
You may wish to implement one or more helper functions as well.

What should BFS return?

Nothing!

Rather, the idea is that once your search has found the destination, it should have set each cell's parent reference. Before returning our of the BFS method, run a loop to change the contents of the MazeCells on the path from 'D' to 'S' to the lowercase 'o' character.

Note that this means running through the path in reverse.

Some IMPORTANT tips...

Remember that breadth-first search (BFS) uses a queue to keep track of the MazeCells that are waiting to be explored. To support this, you'll need to use your queue implementation from Part 2, or you may use Python's deque class directly. The queue will contain references to MazeCells that are waiting to explore their surrounding cells. Initially, the queue will be populated with just one reference - namely to the MazeCell corresponding to the starting element. You'll just enqueue this MazeCell onto your initially empty queue to get started. Then, while the queue is not empty, repeatedly dequeue the next MazeCell to be processed, mark all its non-wall unvisited neighbors, and enqueue them for later consideration!

Do I need to make new MazeCells to enqueue? You could, but this would be messy! Notice that the maze is already made up of MazeCells! Therefore, the queue need not make new MazeCells - it can just keep references to the MazeCells that are already making up the maze!

Notice that your queue implementation can happily enqueue any kind of Object, so it will be happy to enqueue MazeCells in particular!

Finally, bear in mind that the perimeter of the maze is not necessarily entirely made of walls. Be careful not to fall of the edge of the maze - this will inevitably cause a null pointer exception error.

Other notes and details...

Note that Maze starts automatically using the "main trick" as usual. However, this time it must be called from the COMMAND LINE (e.g., shell prompt), because you need to pass an argument to it:

% python Maze.py test1.maze

The provided file doesn't really do much, since BFS is not yet implemented.

Here is what the Maze shown in the example above might look like when printed after calling BFS:


**********
*S*      *
*o* oooo *
*oooo**o *
*    *Do *
**********

There certainly may be more than one shortest path (a tie for shortest). For example, this is equally valid:


**********
*S*      *
*o*ooooo *
*ooo **o *
*    *Do *
**********

The difference would be that, in the latter example, the maze-solving "mouse" searches North before searching East; in the former example, the opposite is true.

And, again, if there is no path from start to destination, please print out the statement Maze not solvable! and do not change what the maze will look like when printed.

There are several mazes provided that you can try out!

You need only submit the Maze.py file.

Want More? (15 Point Optional Bonus Problem, Pair or Individual): Submit in a file named MazeBonus.py

If you want to have more fun with the BFS program, here's an optional bonus problem. There is more thinking here than coding!

Your objective now is to emulate the kind of service that several direction-finding websites provide. Specifically, your breadth-first search should be modified to find the shortest path with the fewest number of turns. That is, among all shortest paths, we want one that turns the fewest number of times. The reason is that paths with fewer turns are easier for humans to follow and are easier to describe.

Specifically, you should make a copy of your Maze.py file and call it MazeBonus.py. This program should take a maze as input and should display a shortest path with the least number of turns. In addition, it should report the length of the trip, the number of turns required, and then give English instructions on how to get from the start to the destination following this shortest path with fewest turns. For example, instructions might look like:

 Trip length: 14 cells
 Number of turns: 2

 Go north 5 cells.
 Turn to the west.
 Go west 6 cells.
 Turn to the south.
 Go south 3 cells.
 You have arrived at your destination.

You may wish to modify some of the code that we've provided in Maze.py. In any case, please test your code carefully to make sure that it really is giving the absolute minimum number of turns among all shortest paths. Of course, your program must still be very fast: We'll test your program with large mazes and allow your program only a couple of seconds to find the solution. Thus, using a brute-force approach will not suffice.

Submit this file as MazeBonus.py.

Harvey Mudd College Computer Science 42 Assignment 8, Due Monday, November 1, by 11:59pm