- 首页 >> Algorithm 算法
P09 Tile Matching Game
Programming II (CS300) Fall 2021
Pair Programming: NOT ALLOWED
Due: 9:59PM on November 24th
P09 Tile Matching Game
In this assignment, you are going to develop a simple tile-matching game. We consider four
columns of tiles where the player can drop tiles of different colors into any of them. Tiles will
be vertically arranged on these columns, stacked atop one another. If two tiles of the same
color are placed on the top of each others, they both disappear.
Learning Objectives
The goals of this assignment include (1) implementing, using, and testing an implementation
of the generic interface StackADT using linked nodes, (2) implementing an iterator to iterate
over a linked stack, (3) implementing the Iterable interface.
Grading Rubric
5 points Pre-Assignment Quiz: The P9 pre-assignment quiz is accessible through
Canvas before having access to this specification by 11:59PM on Sunday
11/21/2021. Access to the pre-assignment quiz will be unavailable passing
its deadline.
20 points Immediate Automated Tests: Upon submission of your assignment
to Gradescope, you will receive feedback from automated grading tests
about whether specific parts of your submission conform to this write-up
specification. If these tests detect problems in your code, they will attempt to
give you some feedback about the kind of defect that they noticed. Note that
passing all of these tests does NOT mean your program is otherwise correct.
To become more confident of this, you should run additional tests of your own.
15 points Additional Automated Tests: When your manual grading feedback
appears on Gradescope, you will also see the feedback from these additional
automated grading tests. These tests are similar to the Immediate Automated
Tests, but may test different parts of your submission in different ways.
10 points Manual Grading Feedback: After the deadline for an assignment has
passed, the course staff will begin manually grading your submission. We
will focus on looking at your algorithms, use of programming constructs, and
the style and readability of your code. This grading usually takes about a week
from the hard deadline, after which you will find feedback on Gradescope.
2021 Kacem & LeGault - University of Wisconsin - Madison.
Additional Assignment Requirements and Notes
Pair programming is NOT ALLOWED for this assignment. You MUST complete and
submit your p09 INDIVIDUALLY.
The ONLY import statements that you may include in your classes are import
java.util.Iterator; and any relevant exception.
DO NOT make any change to the provided source files StackADT.java, Node.java, and
Color.java. In addition, DO NOT submit any of these three files on gradescope.
Only your submitted TileMatchingTester class can contain a main method.
You CANNOT add any fields (static or instance) and any public methods to your submitted
classes other than those defined in this write-up.
You CAN define local variables that you may need to implement the methods defined in
this program.
You CAN define private methods to help implement the different public methods defined
in this write-up, if needed.
All your test methods should be defined and implemented in your TileMatchingTester.java.
All the required test methods in this assignment MUST be public static, DO NOT
take ANY input AND return a boolean.
In addition to the required test methods, we HIGHLY recommend (not require) that you
develop your own unit tests to convince yourself of the correctness of every behavior
implemented in your TileStack, TileListIterator, and TileMatchingGame classes
with respect to the specification provided in this write-up. Make sure to design the
test scenarios for every method before starting its implementation. Make sure also to test
all the special cases.
All implemented methods including the overridden ones MUST have their own javadoc-style
method headers, according to the CS300 Course Style Guide.
Feel free to reuse the descriptions provided in these javadocs in your own javadoc style
class or method headers.
You MUST adhere to the Academic Conduct Expectations and Advice
1 Getting Started
Start by creating a new Java Project in eclipse called P09 Tile Matching Game, for instance.
You MUST ensure that your new project uses Java 11, by setting the “Use an execution
environment JRE:” drop down setting to “JavaSE-11” within the new Java Project dialog box.
Then, add these provided StackADT.java, Tile.java, Color.java, and Node.java to the src folder
of your project.
The provided StackADT interface represents the generic abstract data type stack. This
interface will be implemented by a non-generic data structure stack in the next steps of
this assignment.
The Tile class defines the type of elements which will be stored in the stacks of our
matching game.
The enum Color defines the 4 constant colors of the tiles to be used in our game.
The Node class implements a linked node that can be used to implement any singly-linked
list of tiles.
2 Implement and test Tile.equals() method
First, let’s read through the implementation of the provided class Tile. Each tile has a color
of type Color. It defines one constructor and only one getter for the color (NO setter for
the color is defined). This class also overrides both toString() and equals() methods. The
implementation of the toString() method returning the color of the tile as a string is provided
for you. You MUST complete the implementation of the Tile.equals() method with respect
to the details provided in its javadoc style method header. A tile equals another object ONLY
and ONLY IF the other object is a tile of the same color.
Next, create a new class, with main method, called TileMatchingTester and add it to the src
folder of your project. All tester methods for this program should be added to this class. Then,
write your first tester method called tileEqualsTester with exactly the following signature.
public static boolean tileEqualsTester() {}
The tileEqualsTester method must check the correctness of any implementation of the
Tile.equals() method, not necessarily yours, returns false if any bug is detected, and true
otherwise. This method is NOT supposed to throw any kind of exception. Make sure to define
at least three scenarios for this tester method:(1) Try to compare a tile to an object which is
NOT instance of the class Tile (for instance to a String or an Integer). (2) Try to compare a
tile to another tile of the same color. (3) Try to compare a tile to another tile of different color.
You can define further scenarios. For instance, a tile must be equal to itself. When passed a
null reference, the equals() method is expected to return false.
3 Create TileListIterator class
Now, create a new class called TileListIterator and add it to the source folder of your
Your TileListIterator class MUST implement the Iterator < Tile > interface. It
MUST iterate through any chain of linked nodes (instances of our Node class) starting
from its head.
Your TileListIterator class must define a private instance field of type Node to
keep track of the next element in the iteration.
In addition to the hasNext and next methods which must appropriately be overridden
from the Iterator interface, your TileListIterator MUST define a unique constructor
as follows.
public TileListIterator(Node head) {
// Creates a new iterator to iterate through a list of tiles starting from its head
// head is a reference to the head of the linked list of tiles
Your TileListIterator.next() method MUST throw a NoSuchElementException if there is
no more tiles in the iteration.
Next, expand your tester class by adding the tileListIteratorTester method.
public static boolean tileListIteratorTester(){}
This unit test method MUST check for the correctness of your TileListIterator class. Please
find below some hints.
Your tileListIteratorTester tester method must at least create a chain of linked tiles
(nodes), create an instance of TileListIterator to iterate through the list of tiles starting
from its head, and check the correctness of both hasNext() and next() methods.
Keep in mind that the first call of Iterator.next() method MUST always returns the first
item in the collection if it is not empty, the next call of next() must return the second
item in the collection, etc.
Try to consider the different cases in your tester methods including when hasNext()
must return true, or false, and when the next() method call is expected to throw a
We highly recommend that you write the tester method for your TileListIterator class
before the implementation of the hasNext() and next() methods.
4 Create TileStack class
Now, create a new class called TileStack and add it to the source folder of your project. Your
TileStack class represents a linked stack of tiles. It MUST implement BOTH java.lang.Iterable
and the StackADT interfaces. Both Iterable and StackADT interfaces are generics. But your
TileStack class is NOT genenric. It stores elements of type Tile, only.
Your TileStack class defines two private instance fields, ONLY.
– top of type Node which refers to the top of the linked stack.
– size of type int which keeps track of the number of tiles stored in the stack.
Your TileStack class defines only one no-argument constructor which creates an empty
stack of tiles.
You MUST implement ALL the public methods defined in these javadocs with accordance
to the specification provided in their method headers.
You must expand your tester class by adding the following tester method.
public static boolean tileStackTester(){}
This tester method must return false if any of the methods implemented in the TileStack
class contains a bug, and false otherwise. You are encouraged to break down this
tester method into helper methods. For instance, you can first check the correctness
of isEmpty(), size(), push() and peek() methods. Then, you can check the correctness of
pop() and peek(), and finally you can check the correctness of the iterator() method.
Keep in mind that the TileStack class is modelled as a linked list of tiles while the top
of the stack is the head of the linked list. But only operations like push, peek, and pop
are allowed on that chain of nodes.
5 Create TileMatchingGame class
Now, create a new class called TileMatchingGame and add it to the source folder of your
project. The TileMatchingGame class models a tile matching game which consists of a certain
number of columns of stacks of tiles.
Your TileMatchingGame class defines only one private instance field:
– columns an array of TileStacks.
Only one constructor which takes an int as input (columnCount). The columnCount
represents the capacity of the array columns. This constructor must initializes the columns
array to an array which contains an empty tile stack at each of its index positions from
0 to its length -1.
You MUST implement all the public methods of the TileMatchingGame class with respect
to the specification defined in these javadocs .
Please refer to the output presented in the next section for more details about the format
of the returned string by the TileMatchingGame.toString() method.
You must expand your tester class by adding the following tester method.
public static boolean tileMatchingGameTester(){}
This tester method must return false if any of the methods implemented in the TileMatchingGame
class including the constructor contains a bug, and true otherwise. You are encouraged
to break down this tester method into helper methods.
6 Text-based Tile Matching Game Driver
In the following, we provide you with a sample of run of a text-based driver for this game. You
can download it and use it to play with a text-based version of this game. Read through its
implementation. You should get familiar with how to process user command lines. DO NOT
submit this driver class to gradescope.