PA3: LittleJohns¶
Danger
There is (essentially) no partial credit on this assignment. You must write two classes, and each must be correct for you to receive credit for it.
Your code must comply with the style guide and, if it does, you will earn 30 points. You must write one algorithm that need not be (and probably shouldn't be) recursive; if it is correct you will earn 30 additional points. Finally, you must write one recursive algorithm; if it is correct you will earn 40 additional points.
Warning
Be very careful when using Piazza for PA3. As always, you must not include code in your posts. In addition, you must now be careful when your posts involve discussions of the base case and the refinement process. You may ask general questions about recursion, but your posts must not include details about what you think the base case is or how your are refining the difficult cases. If you have specific questions about the base case and the refinement process you should ask your professor directly (either in person, using email, or in a private post).
Learning Objectives¶
This homework/programming assignment is designed to help you learn about recursion. It is also designed to help you think about what it means for code to be correct, and why programmers shouldn't be satisfied with code that is "partially correct" and/or "almost correct".
Overview¶
You have probably seen the game dominoes (which long predates the pizza company with a similar name and related logo). The (fictitious) company Punch Card Games is developing an electronic version of a game called LittleJohns that has a forward version (that is similar to dominoes) and a reverse version (that is unlike any existing game).
Punch Card Games has developed most of the code that they need. This includes most of the code required for the forward version of the game, and most of the code they need for the reverse version of the game. What they need for both is a class that can be used to verify that a particular play (in the forward version) or configuration of tiles on a board (in the backward version) is consistent with the rules of play.
Background¶
The game gets its name from one of the classic "openings" in the forward version of the game:
which is reminiscent of the quarter-staff battle between Little John and Robin Hood that took place on a log. (The battle predates the two pizza companies with similar names.)
Definitions¶
- Adjacent
- Two tiles are said to be adjacent if the edge of one tile touches (over the entire length) the edge of the other tile
- Attached
- Two tiles are said to be attached if they were placed on the board as part of a single round of play in the forward version of the game.
- Board
- The two-dimensional surface upon which tiles are placed. The dimensions are denoted by North-South and East-West, and (theoretically) extend to infinity.
- Edge
- The side of a tile.
- Forward Version of the Game
- The board is empty and players add pieces to it.
- Reverse Version of the Game
- The board is full and players remove pieces from it.
- Tile
- A square (usually made of wood, though other materials are possible and digital representations can be used) with a number (1, 2, 3, 4, 5, or 6) on the top surface. All tiles used in a single game are the same size. Each tile has four edges, a top surface (containing a number) and a bottom surface (which is blank).
- Pass
- When a player is unable to make a play in the forward version of the game, they are said to "pass".
- Play
- In the forward version of the game, a play involves the placing of two attached tiles on the board by a single player. In the reverse version of the game, a play involves the removal of two attached tiles from the board by a single player.
- Round
- A sequence of single plays or passes by all players.
The Pieces and the Board¶
LittleJohns is a multi-player game that is played in rounds.
The only pieces used in LittleJohns are square tiles, each of which has a number (1, 2, 3, 4, 5, or 6) on the top surface. The game is played on a two-dimensional board (with the dimensions denoted by North-South and East-West) that (theoretically) extends to infinity in both directions.
Rules of Play for the Forward Version¶
Before the game starts, the tiles are divided up evenly among the players in such a way that each player has an even number of tiles. In each round, each player places two tiles on the board.
The game starts with the first player placing one tile anywhere on the board and placing a second tile with one edge adjacent to the first tile. Each player (in turn) places two tiles on the board. The first tile must be placed adjacent to an open edge of one or more tiles with the same number that is already on the board. The second tile must be placed adjacent to an open edge of the first tile of that play. It need not (but can) have the same number as the first tile of the play. The second tile of a play may also be placed adjacent to one or more other tiles but, if so, it must match the numbers on all such tiles.
If a player cannot place two tiles in this way then they must "pass". The game ends when no player can make a play. The winner is the player with the fewest unplayed tiles.
For example, suppose the first tile of the first play is a 3. Then, the board would look as follows:
The second tile of the first play can have any number and can be placed adjacent to any edge of the first tile. Suppose that it is a 5 that is placed to the south of the first tile. Then, the board would look as follows:
where the dotted line indicates that the two tiles were part of a single play.
The first tile of the second play must involve a 3 or a 5. Suppose that it is a 3 that is placed to the east of the existing 3. Then, the board would look as follows:
The second tile of the second play can have any number, but it must be adjacent to an open edge of the first tile of the play (i.e., either to the north, east, or south of the first tile of the play). Suppose that it is a 2 that is placed to the east of the tile that was just played. Then, the board would look as follows:
The first tile of the third play can be a 3, 5, or 2. Suppose it is a 3 that is placed to the north of the original 3. Then, the board would appear as follows:
The second tile can be any number, but can only be placed to the north, east, or west of the tile that was just played. Suppose it is a 6 that is placed to the north. Then, the board appears as follows:
Finally, suppose that the first tile of the fourth play is a 3. There are many possible valid placements. Suppose it is placed as follows:
Then the second tile of the fourth play must be a 2 or a 6, since it must be adjacent to an open edge of the first tile of the play (i.e., placed either to the north or east), and must have the same number as any other tiles that it is adjacent to. If it is a 2, then the resulting board is as follows:
Rules of Play for the Reverse Version¶
Before the game starts, the board is filled with tiles. The total number of tiles is a multiple of two times the number of players. The placement of the tiles must be consistent with rules of play for the forward version of the game.
In each round, each player removes two attached tiles from the board. The player receives a number of points equal to the sum of the the numbers on the two tiles that are removed. At the end of the game, the player with the most points wins.
Existing Classes Provided to You¶
Punch Card Games has provided you with a Tile
class and a Board
class. They are both in the pa3.game
package in the following .jar
file:
As in the past, pa3.jar
must be placed in the lib
directory folder
that is under the CS159
folder.
The capabilities of these components and the relationships between them are illustrated in the following UML class diagram.
The constructor in the Board
class is passed the name of the file
containing the tiles on the initial board. The behavior of the other
methods in these components should be obvious from their names.
The Board
class can read boards that are contained in
"human-readable" text files. The following files are useful
for testing the ForwardStatusChecker
class:
and the following files are useful for testing the ReverseStatusChecker
class:
As in the past, these files must be placed in the CS159
directory/folder.
You must not read these files in any code you write. You must use the
methods in the Board
class.
Specifications for the ForwardStatusChecker
Class¶
You must write a ForwardStatusChecker
class (in the pa3.controller
package). It must have:
- A
public
explicit value constructor that is passed theBoard
to check. - A
checkPlay()
method that is passed aTile
object in thatBoard
. ThecheckPlay()
method must first check theTile
it is passed to determine if it was placed according to the rules (i.e., if all of the adjacent, not-attached tiles have the same number). It must then check the attached tile to determine if it was placed according to the rules.
Specifications for the ReverseStatusChecker
Class¶
You must write a ReverseStatusChecker
class (in the pa3.controller
package). It must have:
- An explicit value constructor that is passed the
Board
to check. - A
check()
method that is passed aTile
object in thatBoard
. Thecheck()
method must returntrue
if the numbers on all of theTile
objects in the board were placed according to the rules, and it must returnfalse
otherwise. Thecheck()
method must use a recursive algorithm. That is, it must call itself either directly (i.e., it must invoke itself) or indirectly (i.e., it must invoke another method that invokescheck()
), or it must invoke another method that calls itself directly or indirectly. In other words,check()
must use a recursive algorithm, but not need be recursive itself (i.e., it could use another method that is recursive).
Getting Started¶
The following ReverseStatusChecker
class has a check()
method that will
check a single Tile
object and its neighbors. It is not recursive,
and does not do everything that is necessary, but should help you get
started on both the ForwardStatusChecker
and the ReverseStatusChecker
.
package pa3.controller;
import pa3.game.*;
public class ReverseStatusChecker {
private Board board;
private boolean result;
public ReverseStatusChecker(Board board) {
this.board = board;
result = true;
}
public boolean check(Tile t) {
Tile n, e, s, w;
// Check the Tile to the north of t
n = board.getAdjacent(t, Direction.NORTH);
if ((n != null) && !board.isChecked(n)) {
if (!board.areAttached(t, n) && (t.getNumber() != n.getNumber())) {
result = false;
}
}
// Check the Tile to the east of t
e = board.getAdjacent(t, Direction.EAST);
if ((e != null) && !board.isChecked(e)) {
if (!board.areAttached(t, e) && (t.getNumber() != e.getNumber())) {
result = false;
}
}
// Check the Tile to the south of t
s = board.getAdjacent(t, Direction.SOUTH);
if ((s != null) && !board.isChecked(s)) {
if (!board.areAttached(t, s) && (t.getNumber() != s.getNumber())) {
result = false;
}
}
// Check the Tile to the west of t
w = board.getAdjacent(t, Direction.WEST);
if ((w != null) && !board.isChecked(w)) {
if (!board.areAttached(t, w) && (t.getNumber() != w.getNumber())) {
result = false;
}
}
// Tell the Board object that t has now been checked (in case
// I want to use this information in the future).
board.setChecked(t);
return result;
}
}
You could then test this code in JUnit as follows:
@Test
public void gettingStartedTest() throws IOException {
Board board = new Board("game01.txt");
ReverseStatusChecker sc = new ReverseStatusChecker(board);
Tile tile = board.getLast();
assertTrue(sc.check(tile));
}
Testing¶
Obviously, you will need to test your code. However, you should not be concerned with the coverage of your tests. It can be quite difficult to get 100% coverage of a recursive algorithm. Instead, you should focus on black-box tests that will help to determine the correctness of your code.
To get you started, you are being provided with some JUnit tests that make use of the files discussed above. They are in the following files:
Debugging¶
The pa3.game
package contains a BoardWindow
class that you might
find helpful when debugging the ReverseStatusChecker
. It shows all
of the Tile
objects in the Board
, and highlights those that have
been "checked" (i.e., which Tile
objects have been passed to the
Board
object's setChecked()
method.
To use it, you should (temporarily) add a BoardWindow
attribute
to the ReverseStatusChecker
class and initialize it in the
constructor as follows:
public ReverseStatusChecker(Board board) {
this.board = board;
this.window = new BoardWindow(board);
}
Then, somewhere in your code (e.g., at the top of your
check()
method), (temporarily) add the following:
if (window != null) {
try {
Thread.sleep(1000);
} catch (InterruptedException ie) {
// Ignore
}
window.repaint();
}
This will cause the program to pause for 1000 milliseconds (i.e., 1 second)
and then refresh the BoardWindow
object so that you can see the state
of your algorithm.
When running, this window will look something like the following
(for the file named "game01.txt"
):
The dotted red rectangles show the tiles that are attached (i.e., were played together).
Infinite Recursion¶
It is very easy to make a mistake that leads to an infinite recursion.
For this assignment, one thing that can lead to an infinite recursion
is checking a Tile
that has already been checked.
You should try very hard to eliminate the possibility of your code containing an infinite recursion before you submit to Gradecsope. Gradescope will allow your code to run for up to 10 minutes before it terminates it.
Submission¶
You must submit (using Gradescope):
- A
.zip
file containing yourpa3
directory/folder (which must include thecontroller
directory/folder that contains theForwardStatusChecker
andReverseStatusChecker
classes).
There is no limit on the number of submissions and no penalty for excessive submissions. Note that your submission will not be graded if it does not comply with the specifications.
Note that you must remove any references to the BoardWindow
class
before you submit your code. Note, finally, that you do not need to
submit any JUnit tests, but you should test your code before
submitting it.
Grading¶
Your code will first be graded by Gradescope and then by the Professor. The grade you receive from Gradescope is the maximum grade that you can receive on the assignment
Gradescope Grading¶
Your code must compile (in Gradescope, this will be indicated in the section on "Does your code compile?") and all class names and method signatures must comply with the specifications (in Gradescope, this will be indicated in the section on "Do your class names, method signatures, etc. comply with the specifications?") for you to receive any points on this assignment. Gradescope will then grade your submission as follows:
Criterion | Points | Details |
---|---|---|
Conformance to the Style Guide | 30 | Success Required |
Correctness | 70 | All or Nothing for Each Class |
In other words, each class is either correct or it isn't.
Manual Grading¶
After the due date, the Professor may manually review your code. At this time, points may be deducted for inelegant code, inappropriate variable names, bad comments, etc.
If your algorithm in the ReverseStatusChecker
class is not
recursive, you will receive no points for it.
Help¶
You should carefully consider all of the following topics before starting.
Allocating Time¶
You should be able to complete the ForwardStatusChecker
relatively
quickly. You should then start thinking about the
ReverseStatusChecker
.
Almost all of your time on this assignment should be spent thinking
about the ReverseStatusChecker
;
very little time should be spent typing/compiling/etc. Indeed, the
recursive method in the ReverseStatusChecker
class may contain as few
as 20 lines of code.
Though it may have worked for you in the past, it is very unlikely
that you will discover an algorithm for the ReverseStatusChecker
using trial and error (i.e., trying something, compiling, testing,
making a change, and repeating). You will need to think carefully
about how to solve problems recursively in general, and how recursive
thinking can be used to solve this problem in particular.
Writing a Recursive Algorithm¶
Remember that there are two parts of a recursive algorithm:
-
The part of the algorithm that handles the "easy" case.
-
The part of the algorithm that moves "difficult" cases toward the "easy" case.
The first thing to think about is how to define the "easy" case. To
do so, suppose you are checking a particular Tile
. When (in terms of
the data) is your job really easy?
After that, think about how, given the definition of the "easy" case, you can make a "difficult" case look more like an "easy" case.
Thinking About Other Recursive Algorithms¶
Thinking about other recursive algorithms may help you write this one.
Finding the Factorial of n
¶
The base case is when n
is 1 (or 0) since all you have to do in this
case is return the value 1. Refinement involves moving from the hard
case toward the easy case (adjusting the answer accordingly). So,
refinement involves reducing the value by 1.
Finding the Size of a Directory/Folder¶
A directory/folder can contain files and other directories/folders. The base case is when we you are examining a file since all you have to do in this case is return its size. Refinement involves moving from the hard case toward the easy case (adjusting the answer accordingly). So, refinement involves entering each directory/folder.
Questions to Think About¶
You don't have to submit your answers to these questions, but you should try to answer them because they will help you determine whether or not you understand some of the important concepts covered in this assignment.
-
If your code works "sometimes" and a
Board
is determined to be valid, have you learned anything? -
If the software in the air traffic control system works correctly and assures a pilot that there are no planes on the runway that they have been directed to, can the pilot land confidently?
-
If the software in the air traffic control system works "sometimes", can a pilot ever land confidently?
-
Would you fly on an airplane if the software in the air traffic control system and the software in the plane's avionics system work "sometimes"?
-
Would you complain if Canvas contained defects that led it to read and write grade files incorrectly every time it did so? Suppose it only read and wrote grade files incorrectly "sometimes"?