CSCI 136 Spring 2026

CSCI 136 - Spring 2026

Data Structures

Home | Lectures | Labs | Handouts | CS@Williams

Lab 2: CoinStrip

This lab is about writing your first Java program with basic object-oriented programming. This is a take-home lab; you should start early, and get help at TA and Office Hours.

Obtaining the Starter Code

Open your terminal using Control-` (this is a backtick, not an apostrophe: the key is above your Tab key). Type git pull and then hit enter.

Once you have run the git pull command, use VSCode to open the Lab02 folder in your repo. Remember to use Open Folder, and not Open File. You should see three files: Move.java, CoinStrip.java, and OptimalAI.java. You only need to modify CoinStrip.java for this lab.

The CoinStrip Game

In this lab, we will make a simple program to play the "CoinStrip Game." In this game, there is a 1-dimensional strip of paper, with "slots" labelled 0, 1, 2, and so on. Each slot is either empty, or contains a coin.

To make a move, a player picks a coin, and moves that coin to a slot with a smaller label; in other words, the coin is moved to the left. This move cannot move to a slot that already contains a coin, and cannot "jump over" a slot containing a coin. For a quick example, imagine a game with coins in slots 2 and 5. If we move the coin in slot 5, we can move it to slots 3 or 4: slot 2 is not allowed because it already contains a coin; slots 1 and 0 would "jump over" the coin in slot 2, and slot 6 or more is not allowed because coins can only move to the left.

If a player goes to move, and there are no legal moves remaining (all coins are pushed all the way to the left, in the smallest slot possible), then that player loses.

For a more extensive exposition of this game (with pictures), see Page 67 of the optional Bailey textbook.

Using Methods in this lab

The code in this lab is organized into three files: Move.java, OptimalAI.java, and CoinStrip.java; each file contains a class. We will be going over how a class works in lecture on Monday and Wednesday (see the handouts as well). However, you should be able to make significant progress on the lab before these lectures.

To help practice with Java objects, we will have a restriction in this lab: you should only interact with the data using the following methods. For a Move, use:

int getPosition() // returns the starting position of the Move
int getNumSpaces() // returns the number of spaces of the Move
void printMove() // prints the Move to the terminal

So, to obtain the position for a move m, you should use m.getPosition(). To obtain the number of spaces, use m.getNumSpaces(). To print the move, use m.printMove().

Similarly, when interacting with the CoinStrip instace, you should use the following methods:

int getNumCoins() // returns the number of coins on the board
int getBoardLength() // returns the number of slots on the board
boolean isOccupied(int position) // returns true if position has a coin on it; false otherwise
void placeCoin(int position) // sets slot position to be true (contains a coin)
void removeCoin(int position) // sets slot position to be false (does not contain a coin)
Move getPlayerMove(int player) // requests the user to input a move. calls isLegalMove() to see if the move is legal; if not, asks the user again. When the user inputs a legal move, it is returned

For example, if you want to know if there is a coin in position 4, you should use isOccupied(4). If you want to move that coin to position 3, you would use removeCoin(4) and placeCoin(3).

Finally, OptimalAI gives the optimal move in any position using the following method.

Move findBestMove(CoinStrip game) // returns the best move for the game state stored in game

Note that you should always pass "this" as the argument to findBestMove, as in the following: Move m = findBestMove(this);. We haven't talked about the "this" keyword yet; in short, it is the equivalent of "self" in python.

Task 0: Compiling and Running the Code

To compile the code, use javac CoinStrip.java.

To run the code, there are three options.

If you use java CoinStrip, the main method will run, but that's it. This is good for testing: you can add your tests to the main method, and use java CoinStrip to run them.
Use java CoinStrip 1 for a one-player game. This will call your onePlayerGame() method (this won't do anything until you are done with task 5).
Use java CoinStrip 2 for a two-player game. This will call your twoPlayerGame() method (this won't do anything until you are done with task 6).

Task 1: Printing the Board

In this task, fill in the methods printCoins() and printSlotLabels(). These will be called one after the other in your code (see printBoard()).

printCoins() should go through each board slot; if it contains a coin, it should print the number of the coin. If the slot does not contain a coin, it should print _. In either case, it should print two spaces afterwards. (Note that there is a typo in the starter code comments: you should in fact have two spaces here; the comment immediately before printCoins() refers to only a single space.) For example, if we have a board with 5 slots, and a coin in the first, third, and fifth slot, this method should output:

1 _ 2 _ 3
Note that each character above has two spaces after it, to line up with the slot labels below.

printSlotLabels() is responsible for placing numbers below each slot. It should iterate through each slot. If the slot number has one digit, it should output the number of the slot, followed by two spaces. If the slot number has two digits, it should output the number of the slot, followed by one space. For example, for a board of length 11, this method should output:

0 1 2 3 4 5 6 7 8 9 10

To test if task is working correctly (both the coins and the labels), try calling game.printBoard() in main(); there is already a call in the comments there.

Task 2: Making a Move

Fill in the method makeMove(Move m). It should use removeCoin() and placeCoin() to move the coin in slot m.getPosition() down by m.getNumSpaces() positions. You can assume that m is a legal move. (We'll test move legality next, in Task 3.)

Task 3: Is this Move Legal?

Fill in the method isLegalMove(Move m). It should return true if m is a legal move, and false otherwise. Remember to use the methods described above to interact with the move m. Don't forget to test your code! In the comments in the main method, I have left code that creates a very simple board to help you with tests.

Task 4: Is the Game Over?

Fill in the method isGameOver() which should return true if the game is over, and false otherwise. Remember to use the methods described above to find which slots contain a coin. Don't forget to test your code!

Task 5: Playing a 2-Player Game

Fill in the twoPlayerGame() method to play a two-player game. Your method should keep track of whose turn it is. It should keep looping until the game is over, asking alternate players for a move.

Your method should call the method isGameOver() to determine if the game is over; getPlayerMove() to ask each player for input (note that you do not need to call isLegalMove(); getPlayerMove() will do so and ensure that the final move returned passes the tests in isLegalMove()); and makeMove() to actually make the move. Once the game is over, it should display which player won.

Once this is finished, you should be able to test your code by playing the game. (It won't check if a move is legal or if the game is over until you do the remaining tasks.) If you want to exit the program, you can use Control-c. If Control-c does not work, try Control-z.

Task 6: Playing a 1-Player Game

Fill in the onePlayerGame() method to play a one-player game. Your method should keep track of whose turn it is, alternating between player 1 and player 2. If it is player 1's turn, the method should ask the user for input. If it is player 2's turn, the method should call ai.findBestMove(this) to get the best possible move from the OptimalAI.java file. When getting an AI move, the method should print the move using m.printMove(). When the game ends, the method should display which player won the game.

Task 7: Test and Submit

Upload CoinStrip.java to Lab02 on Gradescope. You do not need to upload Move.java or OptimalAI.java. Make sure you pass the autograder tests.

Bear in mind that for this lab, the autograder does not test everything. Make sure that you test your own code as well!

Then, it's time to add, commit and push your file using git. Enter each of the following commands into your terminal one at a time. (The pdf instructions from Lab00 have more extensive instructions for how to do this.)

git add CoinStrip.java
git commit -m "finished with lab 2"
git push

After you commit, log into evolene.cs.williams.edu. Click on your repo, then Lab02, then CoinStrip.java, and make sure that you can see the modifications you made. If you can see the changes, you're all set! If you finish early, please talk to one of the instructors to make sure everything is in the right place before you leave.

Optional: Optimal AI Discussion

This discussion is totally optional: it's just for fun if you finish the lab early, and want to look at a much more advanced algorithmic topic.

One may wonder how the computer makes an optimal move at each game state. Oftentimes game AIs search to find the best possible move by trying all (or most) possible moves. In this case, the AI does not search: the best move is known for every possible position.

In particular, this AI works with something called a "reduction." It looks like each CoinStrip instance, and converts it into an instance of another game called Nim. The optimal move in every Nim position is known. The AI's strategy is to convert a CoinStrip position into a Nim position; calculate the best possible move in that Nim position; and then convert the best Nim move into a CoinStrip move.

If you're curious, read about optimal Nim play, and then look at the code in OptimalAI.java. See if you can figure out what the Optimal AI is doing, and why its play is the best possible. Also, please let me know if you see any mistakes in the code.