CSCI 136 :: Spring 2021

Data Structures & Advanced Programming

Home | Schedule | Labs | Handouts | Links | CS@Williams

Lab Overview: The Silver Dollar Game

In this lab, we will write a program to play the Silver Dollar Game described at the end of Bailey Chapter 3 (page 67). In addition to gaining experience writing, compiling, and running programs from scratch, this lab will help us to think about how we can efficiently represent data and break our logic into reusable methods. Careful planning will help tremendously, so take the time to write a well-thought-out design document before arriving at your scheduled lab session. Your design doc may evolve after lab begins; by having a completed design doc in hand, we will all have a concrete way to discuss design plans with others.

PRE-LAB Tasks

Before the start of lab, please (1) watch the lab intro video, and (2) read through this lab handout and sketch out a design for your Silver Dollar Game program. You should feel free to use the sample Nim Design Document as a guide. For this first lab, it is OK if the design is rough: we are not going to deduct points for correctness. The purpose is to ensure that you think about the lab in advance.

Step 1: Getting The Code

By the start of lab, you should have a private lab repository available in your department GitLab account, named USERNAME-lab01-coinstrip, where USERNAME is replaced with your GitLab ID. Clone the repository to your local disk using the following steps:

1. (If you are on campus, skip this step.) If you are off campus, please turn on the college’s VPN. The GitLab infrastructure on the CS department web-servers is configured to reject all network requests that do not originate from within the campus network. The VPN creates the illusion that your computer’s Internet traffic originates from the campus. Note: The VPN only needs to be enabled when interacting with the GitLab infrastructure. You can safely disable it afterwards.
2. After logging into the LDAP textbox using your CS department username/password, you should be greeted with a list of all of your projects. Click on the project USERNAME-lab01-coinstrip.
3. You should now see a convenient view of your repository contents. Click the green “clone or download” button on the right side of the repository page, above the list of repository contents. You are given the option to clone via HTTPS or SSH. You’ll probably want to use HTTPS, so first click on the “Clone with HTTPS” link and then click on the little clipboard with an arrow icon to copy the URL to the local clipboard. (If you are curious about the SSH option, you can read a little bit about it here.)
4. Terminal.app on MacOS, Git Bash on Windows) and navigate to the directory where you would like to store your work for this class (e.g., the cs136 directory we created last week).

   $ cd ~/cs136

   (Note: cd changes your current working directory, and the ~ is a shortcut for your home directory.)
5. Verify that you are in the correct directory using:

   $ pwd

6. Now that you are inside the directory where you will keep all of your CS136 coursework, clone your private repository USERNAME-lab01-coinstrip by typing git clone and then pasting the copied repository URL on the command line. It should look (sort of) like this:

   $ git clone https://evolene.cs.williams.edu/cs136-f20/lab01-coinstrip/USERNAME-lab01-coinstrip.git

   You will be prompted for your username, and then for your password. Enter them when prompted.
7. Change your directory into the new repository directory using

   $ cd USERNAME-lab01-coinstrip

8. Type ls. You should see all of your starter files!

Step 2: Opening Your Lab Code

As we saw in our environment lab, there are many text editors to choose from, and this semester, we will be using the Atom text editor. Let’s use Atom to open your lab code:

• To open your USERNAME-lab01-coinstrip project folder in Atom:
  • Launch the Atom application.
  • Once you have launched Atom, go to the File menu, click on Add Project Folder, and select the USERNAME-lab01-coinstrip folder that you just cloned.
  • Now, in the left pane, you should see a list of all of the files in your project. You can navigate your repository easily using this pane.

(Note: If you would like to simplify this step in the future, you may wish to install Atom’s “shell commands”. After doing so, you can open Atom with a specific project directory from the command line by specifying atom followed by the name of the project folder.)

Step 3: Implementing CoinStrip

This week, we will implement the Silver Dollar Game that is found at the end of Bailey Chapter 3 (Note: page 67 of the text, 83 in the PDF) or in this PDF exerpt.

As you think about the design of your game, you should first decide on a representation of the coin strip. Make sure your representation supports all of the operations necessary such as:

• Generating different game boards. Your game boards must conform to the following rules:
  1. Each game board must have at least three coins, but the exact number of coins on a given game board must be chosen with some randomness. (See the first thought question for inspiration.)
  2. The locations of coins must be randomly selected. In other words, over the course of playing several games, I should expect to encounter different starting configurations.
  3. No game should be “won” before it starts. In other words, there must be at least one legal move.
• Testing whether a move is legal. The rules are fully described in the textbook, but here is a summary:
  1. No “going right”: Coins can only move to the left.
  2. No “double occupancy”: At most one coin can occupy a space at a given time.
  3. No “jumps”: Coins cannot pass another coin.
  4. “Mandatory progress”: A coin must move one or more spaces.
• Printing the board. Somewhere in your code, you will call System.out.println, but we recommend using the following approach:
1. Override the Object class’s public String toString() method. Your CoinStrip class’s toString method should yields a “reasonable” String representation of the gameboard. This is where there we intentionally provide the least specification and give you the most flexibility. Your game board’s String representation should make it clear to the players exactly what the state of the game is at any given time. The string should also provide enough information to the player that they can specify the move that they would like to make next. However, you have some flexibility to add your own “style” to how you display the board. Simple is fine. Elaborate is fine. Please just make it clear!
• Testing for a win: That is, is the game over?
• Moving pieces. When a legal move is given, you should be able to adjust the state of the game to reflect that move. This includes things like relocating coins, changing the current player, etc.

When we say “representation,” our real focus is: what data structures will you use? For instance, you might use a variable boolean[10] board; to represent the game board, where each index of the array represents a space on the coinstrip, and true indicates that a coin is present in that space while false indicates that the space is empty. This is a sensible approach, but let’s think about the implications of this design:

• If I have a game with 3 coins, how large is my board array? What if I instead have 6 coins? In this representation, the size of the array is always larger than the number of coins, and the smallest size the board can be is the position of the rightmost coin.
• Let’s think about enforcing the rules. If I want to make sure a move doesn’t violate the “no jumps” rule, one approach is to check the starting position of the coin, and then examine every array index between that position and the target position of the coin after the move. If there is a true somewhere between those two locations, I know that my coin is “jumping” another. Given this implementation, how many locations do I need to check? The number depends on the “size” of my move.

There are other interesting design questions that would come up if we were to implement the Silver Dollar game this way. Now, it is certainly possible to use this design to successfully create all the game’s required functionality, but it probably isn’t the best solution we can come up with. Let’s explore an alternative design.

The Two-Player Game Interface

In your starter code, we provide a Java interface inside the file TwoPlayerGame.java. This interface describes three methods that you must implement in your Coinstrip.java class. We’ve replicated the contents of TwoPlayerGame.java below:

        public interface TwoPlayerGame {
        
            /**
            * Returns true if the specification of a move describes a legal move
            * given the rules of the game. Note: this does not check whether the
            * move is a *good* move, only whether the move is legal.
            * The move specified is checked against all game rules.
            *
            * A move is described by:
            *   - a resource (e.g., position, gamepiece, pile of matches, etc.)
            *   - a description of the move (e.g., how many matches to remove, how
            *                                many spaces to move, etc.)
            * @param resource describes the game element
            * @param units describes the move
            * @return true if the move is valid
            */
            public boolean isValidMove(int resource, int units);
        
            /**
            * At the conclusion of this method, the game state is changed to represent
            * the completion of the described move. If the described move is not valid,
            * the behavior of this method is undefined.
            *
            *
            * A move is described by:
            *   - a resource (e.g., position, gamepiece, pile of matches, etc.)
            *   - a description of the move (e.g., how many matches to remove, how
            *                                many spaces to move, etc.).
            *
            * @param resource describes the game element
            * @param units describes the move
            */
            public void makeMove(int resource, int units);
        
            /**
            * Returns true if the game is over.
            * @return True if the game is over, false otherwise.
            */
            public boolean isGameOver();
        }

Since we require that you use this interface, we’ll talk now about a design that we think lends itself to a nice implementation of the Silver Dollar game.

Instead of representing the spaces on the gameboard, we can create a data structure that represents the locations of the coins. Let’s use an array of integers, int coins[], where each index corresponds to a single coin, and the value stored at a given index represents the location of that coin on the board.

Now let’s reexamine the questions we posed for the previous design:

• If I have a game with 3 coins, how large is my coins array? What if I instead have 6 coins? In this representation, the size of the array is always the number of coins. It does not change based upon where those coins are located.
• Let’s think about enforcing the rules. If I want to make sure a move doesn’t violate the “no jumps” rule, one approach is to check the starting position of the coin to be moved (examining the coins array at some index i), and then verifying that no coins lie between that location and the target position of the coin after the move. If I’m smart about my representation, I do not need to check every element of the array! Suppose I require that my coins array is in ascending order; how many “coins” do I need to check? Only one!

This is a very compact representation of the game, and it makes enforcing many rules fairly efficient!

Once you have worked through the details of your representation, write down the set of operations needed to adjust/check/populate your data structure (including operations you may need that are not in the TwoPlayerGame interface). Since we’re using Java, your representation should be hidden inside a class called CoinStrip. Operations are made possible by providing public methods that implement those operations. Think about what parameters your methods will take, what values they return, and what the methods do. In lab, we will briefly discuss your initial design (so have a copy of your design handy for discussion).

Required Methods

In addition to the TwoPlayerGame.java interface, we also require two methods to help us test your code. These methods are shown below:

          /**
           * Returns the number of coins on the CoinStrip gameboard.
           * @return the number of coints on the CoinStrip gameboard.
           */
          public int getNumCoins() {
          	return 0;
          }

          /**
           * Returns the 0-indexed location of a specific coin. Coins are
           * also zero-indexed. So, if the CoinStrip had 3 coins, the coins
           * would be indexed 0, 1, or 2.
           * @param coinNum the 0-indexed coin number
           * @return the 0-indexed location of the specified coin on the CoinStrip
           */
          public int getCoinPosition(int coinNum) {
          	return 0;
          }

We rarely impose any particular implementation strategy on you in this course, and we don't think these methods do so; the getNumCoins() and getCoinPosition(int coinNum) methods are quite general. In other words, the methods themselves ask you to provide specific behaviors (which we will rely upon to test your programs), but the methods do not impose any restrictions on the way you implement those behaviors. Further, we think the behaviors these methods provide is critical for any CoinStrip implementation that we can imagine, so we hope that you use these methods to simplify your code.

Further Details / Instructions

The main method of your CoinStrip class should create a CoinStrip object and then prompt each of two players to make their moves. A move will be of the form:

          <cn> <ns>

where <cn> (coin number) specifies the coin to be moved and <ns> (number of spaces) specifies the number of spaces that coin should be moved.

The program should prompt the user for another input if the move is illegal.

To read input from a terminal window, you should use the Scanner class, as we have seen in lecture. Consult the scanner handout, Oracle Scanner documentation, or sample code from lecture for details.

Step 4: Thought Questions

Consider the following questions as you complete the lab. Versions of these questions can be found in the textbook, but we have tried to clarify them where ambiguous. Your solutions to these problems should be submitted with your completed lab inside a file called PROBLEMS.md:

1. What strategy might you use to pick a random number of coins such that there is a 50 percent chance of a game with three coins, a 25 percent chance of a game with four coins, a 12.5 percent chance of a game with five coins, and so on? (You are not required to implement this strategy in your Coinstrip game, but after you’ve concretely described the strategy in text, writing the code to implement it is often the easy part)
2. How might you ensure that the initial games your program generates are not immediate wins? Can you describe a property of the game state that would guarantee that it is possible for players to select a sequence of n moves before the game is won (you would be able to choose the moves)?
3. Suppose the computer could occasionally provide good hints. What opportunities appear easy to recognize? (Some strategies may be hard for the computer to determine, but are there “obvious” cases where the computer should always make a particular move?)
4. How might you write a method, computerPlay, where the computer plays to win? You do not need to write the method, but give a high-level idea of how you might go about implementing it.
5. A similar game, called Welter’s Game (after C. P. Welter, who analyzed the game), allows the coins to pass each other. Would this modification of the rules change your implementation significantly?

Hint: When flipped, the Belgian Euro is heads 149 times out of 250.

Step 5: Style

As relatively new programmers, we are all developing our understanding of what it means to have “good style”. This is made difficult by the fact that the definition of “good style” is both hard to quantify, and hard to agree upon.

To help us all along our lifelong quests to write better code, we have included a tool inside each of our repositories that checks our code against some industry-standard, agreed-upon best practices. This tool is called checkstyle.

In this first lab, we have configured checkstyle to give warnings for most classes of stylistic “mistakes” that we might make. We encourage you to review these warnings and follow the suggestions to improve your code.

However, we have also configured one checkstyle rule to output an error. You must fix all checkstyle errors. Your program will be graded on both correctness and style, and we will use checkstyle errors as our measure of your program’s style.

checkstyle will report an error if your program:

1. Declares a class variable but does not specify the variable’s visibility.

All class variables must be declared as public, private, or protected. If you do not specify a class variable’s visibility, the variable is given “default” visibility, which is very likely not what you want.

As the semester progresses, we will convert more and more style checks from warnings to errors. It is in your best interest to fix all warnings—both to develop better coding practices, and to prepare yourself for future labs.

To run checkstyle, you would type the following command at the terminal:

             $ ./checkstyle

The ./ is a Unix thing: it tells the terminal where to look for the checkstyle program. The . (dot) tells Unix to look in the current directory. This will run checkstyle on every Java program in your directory. To run checkstyle on just one Java file, you would instead specify:

             $ ./checkstyle SomeFile.java

checkstyle is a relatively new addition to the course, and we added it based on student feedback. We hope it helps! If you have any questions about checkstyle output, please ask an instructor or a TA for guidance.

Lab Deliverables

When you are finished with your CoinStrip program, answer the thought questions at the end of the lab, and put your answers in a separate file called PROBLEMS.md. Commit and push PROBLEMS.md along with your other lab files as part of your repository. Your repository should have the files:

          USERNAME-lab01-coinstrip/
                 checkstyle
                 CoinStrip.java
                 TwoPlayerGame.java
                 README.md
                 PROBLEMS.md
  

(Note: you may notice one or more “hidden” files inside your repository that start with a . (dot). These files should not be modified; they are there to help git. We use them to instruct git not to include files that end in the .class extension, back up files, or other files that are automatically generated by various programs; these types of files clutter our repositories and aren’t useful to include in your final submission.)

Submitting Your Lab

As you complete various milestones, you should commit your changes and push them. Commit early and often. When the deadline arrives, we will retrieve the latest version of your code. If you are confident that you are done, please include “Lab 1 Submission” as the commit message for your final commit. If you later decide that you have more edits to make, it is OK. We will look at the latest commit before the deadline.

• Be sure to push your changes to GitLab
• Verify your changes on GitLab. Navigate in your web browser to your private repository on GitLab. It should be available in your project listing after logging into https://evolene.cs.williams.edu. You should see all changes reflected in the various files that you submit. If not, go back and make sure you committed and pushed.

We will know that the files are yours because they are in your git repository. Do not include identifying information in the code that you submit. Our goal is to grade the programs anonymously to avoid any bias. However, in your README.md file, please cite any sources of inspiration or collaboration (e.g., conversations with classmates). We take the honor code very seriously, and so should you. Please include the statement “I am the sole author of the work in this repository.” in the comments at the top of your Java files.

Late Days

At any point up to the lab deadline, and for any reason at all, you may decide to take a late day. In order to let us know, you must fill out this form.

Over the course of the semester, you have a total of 3 free late days at your disposal. You may not take more than two late days on a given lab. When deciding whether or not to take a late day, please remember that we give partial credit for any work that you complete.