CS200 Lab 4

Overview

This lab will explore induction and program debugging with assertions. Specifically, we will be covering:

Lab Assignment

You will need to following files to complete the induction portion of this lab: Meet your partner! After reviewing PA2, you'll be working with your partner on the last portion of this lab:

Create an R4 in your workspace, you will need the following files:

Debugging Overview

This week's assignment involves very little coding on your part. Instead, you will be reading, understanding, and debugging an application. Minesweeper is a simple, but popular, game available on virtually every platform. Given a square board (n rows by n columns), the player must identify board spaces that contain a mine (or bomb). At the start of the game, all squares obscure whether or not they contain a mine. However, the user is given hints about the locations of mines by other board spaces. Specifically, board spaces adjacent to one or more mines tell how many mines they neighbor. This enables the player to detect patterns and deduce where a mine is most likely to appear.

Once the player has guessed that a space contains a mine, they may "flag" the board space. The user wins the game by successfully flagging every mine or by exploring every space that does not contain a mine. The player is initially given a number of flags equal to the number of mines so that they may not simply guess that every space is a mine. Finally, the player immediately loses the game if they explore a board space that contains a mine. Upon winning or losing the game, the player is shown the true board layout (all unexplored spaces are shown). The provided code is a broken implementation of a text-based minesweeper game. Here is an example of a game in progress: 

  0 1 2 3 4 5 6 7 8 9
0| | | | | | | | | | |
1| | | | | | | | | | |
2| | | |1|1|1| | | | |
3| | | |1|?|1| | | | |
4| | | |1|1|1| | | | |
5| | | | | | | | | | |
6| | | | |1|1|1| | | |
7| | | | |1|?|2|2|1|1|
8| | | | |1|3|?|?|?|?|
9| | | | | |2|?|?|?|?|
Flags Remaining: 5
The top and left side of the board describe the column and row number, respectively. Board spaces are delimited by the "|" character. The top left board square is identified as (0, 0). This example contains several types of board spaces. Initially, all board spaces are marked as "hidden", that is, it is uncertain whether or not the space contains a mine. Hidden spaces are denoted by "?". Explored spaces that do not contain a mine and are not adjacent to a mine are referred to as "cleared". Cleared spaces are represented by " ". Board spaces adjacent to a mine contain an integer [1, 8] that describes how many mines the space neighbors. For example, the board space at row 3, column 3 contains the value 1. In other words, (3, 3) is adjacent to only 1 mine. Adjacency is counted in terms of left, right, up, down, as well as diagonal directions. Consider the board space (8, 5) that is adjacent to a total of 3 mines. Given this board state, the player may wish to immediately "flag" a mine. Here, (3, 4) is a fairly obvious choice. Once the user enters the "flag" command, the board state would change to 

  0 1 2 3 4 5 6 7 8 9
0| | | | | | | | | | |
1| | | | | | | | | | |
2| | | |1|1|1| | | | |
3| | | |1|F|1| | | | |
4| | | |1|1|1| | | | |
5| | | | | | | | | | |
6| | | | |1|1|1| | | |
7| | | | |1|?|2|2|1|1|
8| | | | |1|3|?|?|?|?|
9| | | | | |2|?|?|?|?|
Flags Remaining: 4
where the board space (3, 4) is now represented by "F". Note that the "Flags Remaining" status was also updated from 5 to 4. That is, the player has consumed a flag by placing it on the board. The player is initially given a sufficient number of flags to cover all placed mines.
Suppose the player chose to reveal a board space that contained a mine. For example, (7, 5): 

  0 1 2 3 4 5 6 7 8 9
0| | | | | | | | | | |
1| | | | | | | | | | |
2| | | | | | | | | | |
3| | | | |X| | | | | |
4| | | | | | | | | | |
5| | | | | | | | | | |
6| | | | | | | | | | |
7| | | | | |M| | | | |
8| | | | | | |M| |M| |
9| | | | | | |M| | | |
GAME OVER

Here, we see an "X" at position (3, 4) denoting a mine that was correctly flagged. 
The remaining mines, including the one revealed by the player, are displayed as "M". 
Finally, note that a GAME OVER message is displayed and the program terminates. 
Similarly, the full board is displayed if the player wins the game along with an appropriate message.
Thus far, we have mentioned two distinct commands the player may enter to play the game: reveal and flag. These commands are entered at the displayed ">" prompt.

Your Task

The provided implementation of minesweeper contains numerous bugs. Talk with your partner about how to read and interpret the provided code documentation to understand what each method should accomplish. You will then use this understanding to generate assertions using the assert keyword that reflect the method's goals. These assertions will enable you quickly identify bugs and reason about what code modifications should be made (and then make them).

In summary, your workflow for each method will roughly consist of:

  1. Understand how the method should work by reading its documentation.
  2. Convert your knowledge into assert statements in the code.
  3. Observe the program's behavior by running it and seeing what assertions are violated and/or exceptions are thrown.
  4. Read the program's code to understand why the observed behavior happens (or when it happens).
  5. Fix the problem.
  6. Re-run the program to confirm the bug is fixed.
This assignment does NOT involve writing a substantial amount of code. If you find yourself writing much more than a single if-statement here and there, something is wrong. Most of the required fixes are minor tweaks to the existing code.

Furthermore, you need only modify the code in BoardModel.java. There are no intentional bugs in BoardSpace.java and BoardController.java to worry about. BoardController is responsible for running the minesweeper game and interacting with the user. BoardSpace objects are used by the BoardModel to represent game spaces. You may encounter bugs in how BoardModel uses BoardSpace objects.

You should assume that the provided documentation is correct. There are no intentional bugs in the documentation.

Overview of the Program

The provided minesweeper game consists of three classes: BoardController, BoardModel, and BoardSpace. BoardController handles all I/O and interaction with the player. The BoardModel represents the current state of the game. More specifically, BoardModel describes the rules of the game (win/loss conditions, move validity, etc.) and the state of the game in progress (revealed spaces, flag/mine locations, etc.).

Internally, the game board is represented as a two dimensional array of BoardSpace objects in (row, column) order. For example: 

int row = 5;
int col = 2;

BoardSpace space = board[row][col];
refers to BoardSpace stored in row 5, column 2. Recall that row 0, column 0 is the top left corner of the board. Each BoardSpace describes whether or not the space has been revealed (directly or indirectly), if the space contains a mine, if the space has been flagged, and the number of mines that are adjacent to the space. In general, a BoardSpace object is responsible for storing information related to how that particular space is view by the user over the course of the game.

Board spaces are initially not "visible" to the player. That is, the player does not know whether or not a space contains a mine until it has been revealed. This information is displayed once the player reveals a space either directly (via the reveal command) or indirectly (triggered exploration). The BoardModel is the intermediary for all interaction with BoardSpace objects. The BoardController has no knowledge of the details of the BoardSpace class.

BoardModel contains numerous instance variables that help it keep track of the game's state. Aside from the previously discussed 2D board, BoardModel also keeps track of the unflagged mines (remainingMines), the number of mines that should be laid, whether or not the user has made their first move, and whether the game has been lost or won. BoardModel retains state of the user's first move in order to improve the game's playability. Mines are only laid after the player has made their first move. This prevents the player from picking a mine on their first move and immediately losing the game. We will discuss mine laying in more detail shortly.

Constructing BoardModels

Minesweeper games are created with respect to an initial board size and a difficulty setting. For the purposes of our game, the board should be a square with at least 3 rows. Anything smaller would not be a very fun game. The difficulty level determines the number of mines that should be laid after the player's first move. We allow three difficulty settings: easy, normal, and hard. Let R be the number of rows in the game board. The number of mines laid, M is set according to the following equations:

Game instances must also have at least 1 mine. Otherwise, it is not much of a game.

Finally, the constructor must ensure other pieces of the game's state are properly initialized. However, this task is delegated to the resetBoard() method. We will discuss this method soon.

Debugging the Constructor (Warm Up)

The initial BoardModel(int row, int col, int difficulty) constructor contains: 

	public BoardModel(int rows, int cols, int difficulty)
	{
		board = new BoardSpace[rows][cols];

		for (int r = 0; r < rows; r++) {
			for (int c = 0; c < cols; c++) {
				board[r][c] = new BoardSpace();
			}
		}

		switch (difficulty) {
		case HARD:
			numMines = rows + (rows/2);
			break;

		case NORMAL:
			numMines = rows;
			break;

		case EASY:
		default:
			numMines = rows/2;
			break;
		}

		resetBoard();
	}
We begin by adding assertions to the constructor that enforce the original design. More specifically, a game must be at have at least 3 rows and columns and must form a square board. A board must also contain at least one mine. 

	public BoardModel(int rows, int cols, int difficulty)
	{
		//Smallest board allowed is a 3x3
		assert rows >= 3 : "Expected rows >= 3, got " + rows;
		assert cols >= 3 : "Expected cols >= 3, got " + cols;

		//We only use a square board (rows == cols)
		assert rows == cols: "Expected rows == cols, got rows = " + rows + " cols= " + cols;

		board = new BoardSpace[rows][cols];

		for (int r = 0; r < rows; r++) {
			for (int c = 0; c < cols; c++) {
				board[r][c] = new BoardSpace();
			}
		}

		switch (difficulty) {
		case HARD:
			numMines = rows + (rows/2);
			break;

		case NORMAL:
			numMines = rows;
			break;

		case EASY:
		default:
			numMines = rows/2;
			break;
		}

		//Assert that there is at least 1 mine, otherwise it's not much of a game
		assert numMines >= 1 : "Expected numMines >= 1, got " + numMines;

		resetBoard();
	}
These requirements lead to four assertions. Note that Java assertions can take two distinct forms. We use a variation on the form used in class that enables us to print a special error message if the assertion is violated. The portion after the ":" is the message that is displayed is similar to what you would pass to System.out.println().

Examining the code reveals that the constructor has several bugs. First, we are trusting that the caller will pass rows and cols a values greater than or equal to 3. Similarly, we have no guarantee that rows will have the same value as columns and could potentially end up with a board that is not a square. If we assume that we have at least 3 rows and columns, then we can be certain that we will always have at least 1 mine since 3/2 is 1 (integer division). If we were to run this code, as you will for the later methods, the first three assertions could be tripped. As such, add some small fixes to ensure that we always have appropriate values. 

	public BoardModel(int rows, int cols, int difficulty)
	{
                //Fix having less than 3 rows
		if (rows < 3) {
			rows = 3;
		}

                //Fix having less than 3 columns
		if (cols < 3) {
			cols = 3;
		}

		//Smallest board allowed is a 3x3
		assert rows >= 3 : "Expected rows >= 3, got " + rows;
		assert cols >= 3 : "Expected cols >= 3, got " + cols;

                //Fix non-square board
		if (rows != cols) {
                        cols = rows;
		}

		//We only use a square board (rows == cols)
		assert rows == cols: "Expected rows == cols, got rows = " + rows + " cols= " + cols;

		board = new BoardSpace[rows][cols];

		for (int r = 0; r < rows; r++) {
			for (int c = 0; c < cols; c++) {
				board[r][c] = new BoardSpace();
			}
		}

		switch (difficulty) {
		case HARD:
			numMines = rows + (rows/2);
			break;

		case NORMAL:
			numMines = rows;
			break;

		case EASY:
		default:
			numMines = rows/2;
			break;
		}

		if (numMines == 0) {
			numMines = 1;
		}

		//Assert that there is at least 1 mine, otherwise it's not much of a game
		assert numMines >= 1 : "Expected numMines >= 1, got " + numMines;

		resetBoard();
	}
Running the program should now successful run the BoardModel constructor without failing any assertions. The remainder of this lab page will serve as the documentation for the remaining methods that you must debug. You should follow the above workflow to help you fix the problems.

The Rest

Your lab assignment is to fix bugs in the following methods: