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 is not 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:

• pa3.jar

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:

• play01.txt
• play02.txt
• play03.txt
• play04.txt
• play05.txt

and the following files are useful for testing the ReverseStatusChecker class:

• game01.txt
• game02.txt
• game03.txt
• game04.txt
• game05.txt
• game06.txt
• game07.txt
• game08.txt

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:

1. A public explicit value constructor that is passed the Board to check.
2. A checkPlay() method that is passed a Tile object in that Board. The checkPlay() method must first check the Tile 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:

1. An explicit value constructor that is passed the Board to check.
2. A check() method that is passed a Tile object in that Board. The check() method must return true if the numbers on all of the Tile objects in the board were placed according to the rules, and it must return false otherwise. The check() 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 invokes check()), 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 .zip file (which includes a testing directory/folder):

• ForwardStatusCheckerTest.java
• ReverseStatusCheckerTest.java

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(window);
}

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):

1. A .zip file containing your pa3 directory/folder (which must include the controller directory/folder that contains the ForwardStatusChecker and ReverseStatusChecker 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:

1. The part of the algorithm that handles the "easy" case.

2. 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.

1. If your code works "sometimes" and a Board is determined to be valid, have you learned anything?

2. 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?

3. If the software in the air traffic control system works "sometimes", can a pilot ever land confidently?

4. 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"?

5. 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"?