CS1027 ASSIGNMENT 4 Computer Science Fundamentals II solution

$24.99

Original Work ?
Category: You will Instantly receive a download link for .ZIP solution file upon Payment

Description

5/5 - (4 votes)

Learning Outcomes
To gain experience with
 Working with linked data structures
 Recursive approaches to problem solving
 Putting together many concepts into one project
 Algorithm design
Introduction
Minesweeper is a solitaire computer game in which there are bombs hidden in a grid of cells,
and the objective is to clear out all the non-bomb cells without hitting a bomb. If a bomb is
clicked, the game is over in failure.
To help the player determine where the bombs are located, the other cells contain a number
that indicates the number of bombs in the eight adjacent (both orthogonal and diagonal) cells.
The number on a cell is revealed when that cell is clicked. Additionally, when a cell that has no
adjacent bombs (let’s call this a 0-cell) is clicked, it triggers a “region clear” which means that a
region beginning with the clicked cell and expanding outward will be revealed at once. The
region will include all 0-cells connected to the clicked cell, and numbered cells connected to
those 0-cells. Figure 1 shows examples of 3 cleared regions. For each of these regions, one of
the inner 0-cells was clicked, and the surrounding region was consequently cleared.
CS1027
ASSIGNMENT 4 Computer Science Fundamentals II
Figure 1. A screenshot of a completed (lost) game in which a bomb cell was clicked after
revealing 3 regions throughout the board. Cells with a number indicate how many bombs cell
are neighbouring (orthogonally or diagonally adjacent).
Provided files
The following is a list of files provided to you for this assignment. Please do not alter these files
in any way.
 BombRandomizer.java – provides a method for randomly placing bombs
 GUI.java – provides the visual GUI for the program
 GUICell.java – represents each cell in the game board
 LinearNode.java – represents a node for a singly-linked list
 LinkedListException.java – a simple exception class
 TestLinkedGrid.java – provides several tests to check that LinkedGrid is working
 TestGame.java – provides several tests to check that the Game methods are working
CS1027
ASSIGNMENT 4 Computer Science Fundamentals II
Classes to implement
For this assignment, you must implement 2 Java classes: LinkedGrid and Game. Follow the
guidelines for each one below.
In both of these classes, you can implement more private (helper) methods, if you want to, but
you may not implement more public methods. You may not add instance variables other than
the ones specified below. Penalties will be applied if you break these rules.
LinkedGrid.java
This class represents a 2D grid (matrix) that is created as an array of singly linked lists. This
class must work for any generic type T and must be created using the descriptions explained
here. The array, which must be the width of the grid, will contain the front (or top) nodes of each
of the linked lists. The height of the grid is represented by the number of nodes in each of the
linked lists. The example below shows a 5 by 4 grid (remember the front node of each list is
contained in the array so there are 4, not 3, nodes in each list).
Figure 2. A diagram depicting the LinkedGrid structure as an array of linked lists.
CS1027
ASSIGNMENT 4 Computer Science Fundamentals II
The class must have the following private variables:
 width (int)
 height (int)
 grid (LinearNode array)
The class must have the following public methods:
 LinkedGrid (constructor) – takes in 2 parameters for width and height and assigns their
values into the corresponding instance variables. The grid must be initialized properly by
creating the LinearNode objects and connecting them as singly linked lists. The first
node of each list must be stored in the corresponding array cell in the grid parameter.
 setElement – takes in 3 parameters: int col, int row, T data. If the col or row is outside
the bounds of the grid, throw a LinkedListException. Otherwise, find the cell in the grid at
the given col, row pair and set the element of that node to the given value, data.
 getElement – takes in 2 parameters: int col, int row. If the col or row is outside the
bounds of the grid, throw a LinkedListException. Otherwise, find the cell in the grid at the
given col, row pair and return the element contained in that node.
 getWidth – returns the width
 getHeight – returns the height
 toString – builds a string that represents the entire grid of elements. Include 2 spaces
between each of the elements and use a newline character at the end of a row to
continue the string on the next line. Return the completed string.
Game.java
This class contains the Minesweeper-related code. It is used to initialize the game board,
determine the numbers for each cell (which indicate how many bombs are in neighbouring
cells), the recursive “region clearing”, etc.
The class must have the following private (unless stated otherwise) variables:
 board (LinkedGrid)
 cells (LinkedGrid)
 width (int) – must be public static
 height (int) – must be public static
 gui (GUI)
The class must have the following methods:
 Game (constructor #1) – takes in int width, int height, boolean fixedRandom, boolean
showGUI. Set the width and height class variables and then initialize the board grid with
an ‘_’ (underscore) character in every cell. Then initialize the cells grid of GUICell
elements (NOTE: even if the GUI is not being shown, we still use the GUICell class for
CS1027
ASSIGNMENT 4 Computer Science Fundamentals II
these cells). Use the BombRandomizer’s placeBombs method (sending in the board and
fixedRandom parameter) to randomly place bombs throughout the game board. Call the
determineNumbers method (see description below) to get the number for each cell
which indicates how many bomb cells are neighbouring each cell. Lastly, if showGUI is
true, then initialize the GUI object.
o NOTE: the fixedRandom variable is used to determine if you want to use the
same random seed each time you run it for testing purposes. If fixedRandom is
true, then it uses a fixed seed so the board will be the same every time you run it
(assuming the size is not changed). Otherwise set fixedRandom to false if you
want to run the game with a different, actually random board each time.
 Game (constructor #2) – takes in LinkedGrid board, boolean showGUI. This
constructor is almost the same as the 1st one above. The only differences are that the
board is already set so you do not need to follow the same board initialization and
random bomb placement. Instead, simply assign the board parameter to the
corresponding instance variable. The rest of the method is identical.
 getWidth – returns the width
 getHeight – returns the height
 getCells – returns the LinkedGrid cells
 determineNumbers – go through every single node in the board and calculate how many
bombs are in surrounding cells, and insert that number into the corresponding node in
the cells grid. Cells that contain bombs must have a number of -1 (even if they are
adjacent to other bombs), but all other cells must have a number (from 0 to 8) that
indicates the number of bombs around that cell.
 processClick – this method processes a cell being clicked OR a simulated click and
returns an int value representing how many cells are being revealed or -1 if a bomb is
revealed. It takes in two integers for col and row, and gets the GUICell from that position
in the grid.
o If the given cell contains -1 (bomb) then set the background of this cell to red
(use cell.setBackground(Color.red)) and reveal the cell (look at the GUICell
methods to see how to do this).
o If the cell contains a 0, begin the recursive “region clearing” from this cell and
return the result that is returned from the recursive method.
o If the cell contains any other number (1 through 8), then check if it was previously
revealed. Return 0 if previously revealed. If it wasn’t previously revealed, make
sure to reveal it and set it to white and then return 1.
 recClear [private, and name is not important] – takes in two integers for col and row and
returns an int representing the number of cells being revealed from this method call. This
is the recursive helper method invoked from the processClick method. Read the
description of “Region clearing” and the pseudocode for recClear below.
CS1027
ASSIGNMENT 4 Computer Science Fundamentals II
Region clearing
One of the terms used in this assignment is “region clearing”. This occurs when a 0-cell (a cell
that does not have a bomb nor is adjacent to a bomb) is clicked. The cell itself is revealed but it
also triggers its region to become revealed immediately. The region is defined as the contiguous
(connected) 0-cells and even up to numbered cells along the perimeter of the region but no
further than the numbered cells. This form of clearing can be done very elegantly with recursion.
Examine the following illustrations that demonstrate “region clearing” in a sample 5 by 5 game
grid with 7 bombs. Figure 3 shows the original game board before clicking any cells, and it
shows the bombs’ locations just for demonstrative purposes (bombs are not shown in the actual
game!) Figures 4-6 illustrate each recursive step in the algorithm from clicking the middle cell.
Figure 3. A sample 5 by 5 game grid with 7 bombs (visible for demonstration purposes)
Figure 4. The sample game board after clicking the middle cell, which is a 0-cell. Red arrows
indicate which cells will be revealed in the first recursive step of the region clearing.
CS1027
ASSIGNMENT 4 Computer Science Fundamentals II
Figure 5. After one recursive step, the cells surrounding the clicked (middle) cell are revealed.
The next step will reveal the cells surrounding the 0-cells at the top of the existing region.
Numbered cells indicate the region’s perimeter, so the clearing doesn’t go beyond those cells.
Figure 6. The clearing has completed since Figure 4. The cells just revealed are either
numbered or are along the edge of the board itself, so there are no more recursive calls. This is
the finished “region clearing” from clicking that middle cell (NOTE: the region would have been
the exact same from clicking on any of the 0-cells in the top-left corner of this region).
CS1027
ASSIGNMENT 4 Computer Science Fundamentals II
Pseudocode
function recClear (int c, int r)
Input: column c and row r of cell being clicked
Output: int value representing how many cells were revealed
if c or r is outside bounds of game board, return 0
if cells(c, r) is already revealed, return 0
if cells(c, r) is a bomb (-1), return 0
else if cells(c, r) is a numbered cell (> 0)
reveal cells(c, r)
set cells(c, r) colour to white in gui (if gui != null)
return 1
else
reveal cells(c, r)
set cells(c, r) colour to white in gui (if gui != null)
result = 1;
result += recClear(c-1, r)
… (all other recursive calls)
return result
Marking notes
Marking categories
 Functional specifications
o Does the program behave according to specifications?
o Does it produce the correct output and pass all tests?
o Are the class implemented properly?
o Are you using appropriate data structures?
 Non-functional specifications
o Are there Javadocs comments and other comments throughout the code?
CS1027
ASSIGNMENT 4 Computer Science Fundamentals II
o Are the variables and methods given appropriate, meaningful names?
o Is the code clean and readable with proper indenting and white-space?
o Is the code consistent regarding formatting and naming conventions?
 Penalties
o Lateness: 10% per day
o Submission error (i.e. missing files, too many files, etc.): 5%
o “package” line at the top of a file: 5%
Remember you must do all the work on your own. Do not copy or even look at the work of
another student. All submitted code will be run through cheating-detection software.
Submission (due Wednesday, December 9, 2020 at 11:55pm ET)
Assignments must be submitted to Gradescope, not on OWL.
Rules
 Please only submit the files specified below. Do not attach other files even if they were
part of the assignment.
 Submit the assignment on time. Late submissions will receive a penalty of 10% per day.
 Forgetting to submit is not a valid excuse for submitting late.
 Submissions must be done through Gradescope.
 Assignment files are NOT to be emailed to the instructor(s) or TA(s). They will not be
marked if sent by email.
 You may re-submit code if your previous submission was not complete or correct,
however, re-submissions after the regular assignment deadline will receive a penalty.
Files to submit
 LinkedGrid.java
 Game.java