CSCI 136 - Spring 2026

Data Structures

Home | Lectures | Labs | Handouts | CS@Williams

Lab 6: CoinStrip With Takebacks

This lab is about inheritance and stacks. This is a take-home lab; you should start early, and get help at TA and Office Hours.

Task 0: Fix your CoinStrip

Before doing anything else, please look over your CoinStrip.java submission from Lab 2. Check for any instructor comments on Gradescope. Please implement any fixes, as we will be building on your code in this lab. If you do not know how to fix your code, please ask the instructors of TAs for help. (All of the fixes should be possible to implement very quickly—please be sure to get help to ensure that you don't get stuck on this task.)

Obtaining the Starter Code (Be Sure to Copy CoinStrip.java)

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 Lab06 folder in your repo. Remember to use Open Folder, and not Open File. You should see three files: Move.java, CoinStripTakeback.java, and OptimalAI.java.

Now, you must copy your CoinStrip file into your repository. Using the terminal, you can do this as follows:

cp ../Lab02/CoinStrip.java .

Let's look at what the above comand does. cp is short for copy: it makes a copy of a file. The next two arguments are the file being copied, and the destination for the copy (that is to say: where does it go, and what is it called).
The file being copied is ../Lab02/CoinStrip.java The two periods at the beginning means "go up a directory". Then, we have a folder name Lab02 and finally the file name, CoinStrip.java
For the destination, we only have a period. This means "use the same file name it had originally." In other words, the code you ran is exactly the same as this:

cp ../Lab02/CoinStrip.java CoinStrip.java

Therefore, you are copying your CoinStrip.java file from the Lab02 folder into the current Lab06 folder.

The CoinStrip Game: Now With Takebacks

The 1-player CoinStrip game played against an optimal AI. Since the AI plays optimally, we'd like every advantage we can get. In particular, it would be very nice to allow takebacks: we should be able to undo moves we've made in the past.

In our new one player game, the player has two options. They can input a move by inputting a slot, followed by a number of spaces (since we are more comfortable with Java, the player can input them on a single line now). Or, they can input "u" to undo a move.

Design: Implementing Undo

First, let's discuss undo. We want to keep track of what the board state was in the past: when the user says they want to undo a move, we will find the most recent board state, and set the current board state equal to that state.

First, we need a data structure to store the board states. We will only want to access the most recently added state. That means that we can use a stack. In this lab, we will use the Java library stack (this is why we have import java.util.Stack at the top of CoinStripTakeback.java).

In CoinStrip.java, we kept track of the board state using an array of booleans instance variable called board. We will keep the most recent board variables in our stack. In other words, each time the user makes a move, we will add the most recent board to the stack. Then, when the user undoes a move, we will pop the most recent board off the stack, and set our current board equal to that board.

Task 1: Extending CoinStrip

First, use the extends keyword to modify CoinStripTakeback.java so that CoinStripTakeback inherits from CoinStrip.

Let's look briefly at the starter code. You will see that the code overrides the printCoins() and printSlotLabels() methods to print the board. It also overrides the getPlayerMove() method to prompt the player to make a move.

Compile and run CoinStripTakeback. The board should be correctly printed, calling the new (override) print methods. However, it will not correctly make moves, since parseMove() has not yet been implemented.

Task 2: Reading Player Moves

Let's write code to allow the player to input a move (no undo/redo yet). The player's move will consist of two numbers, separated by a space. For example, if they want to move the coin in position 6, and the goal is to move it 3 spaces to the left, they would input: 6 3

Read the new getPlayerMove() method. The important takeaway is that this method calls another method, interpret(), which is what is responsible for actually reading what the user inputs. In turn, the interpret() method currently only calls the parseMove() method.

Fill in the parseMove() method with code to take in a String, and return the move that the string represents. The code to split the response string into an array of Strings (where each was separated from the next by a space in the response string), has already been provided in the starter code. You should use Integer.parseInt() to translate each of these strings into the corresponding int. The error message should have an example move with the numbers 83 and 82. Be sure to implement error checking in your code: what happens if the user inputs more or less than 2 numbers? What happens if they input (say) a letter instead of an int? This will require using a try/catch block as we saw in class (on April 8).

Test your code by running it and seeing if the game works. Make sure to make sure your error-checking works. You should now have a working coinstrip game (with improved input/output).

Task 3: Implement undo

First, create an instance variable called oldMoves. This variable should be a Stack where each item in the stack is an array of booleans.

Now, in interpret(), each time the user selects a legal move, you should push the current board state onto the oldMoves stack. To do this, you must change board to protected in CoinStrip.java (since otherwise you cannot access board). This is the only change you will make to CoinStrip.java in this lab.

When you push the board onto the stack, be sure to push a new copy of the board onto the stack: we don't just want a new reference to the same array, we want a new array. Java arrays have a .clone() method to do this: you want to push board.clone() rather than just board.

Now, implement the undo() method. To undo, you should pop the most recent board off the stack, and set the board variable equal to the value stored on the stack. Your undo() method should output an error message if there is no previous board state stored in the stack.

Then, modify interpret() so that if the user inputs the String "u", the method calls undo() and then returns a new Move (you may use the default constructor for this.)

Task 4: Test and Submit

Upload CoinStripTakeback.java and CoinStrip.java to Lab06 on Gradescope. You do not need to upload Move.java or OptimalAI.java. There is no autograder for this lab—you should check that your undo works correctly, and that you have implemented all error checking.

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 CoinStripTakeback.java CoinStrip.java
git commit -m "finished with lab 6"
git push

After you commit, log into evolene.cs.williams.edu. Click on your repo, then Lab06, then CoinStripTakeback.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.

Extra Credit: Implementing Redo

For extra credit, use another stack to implement a redo() method: if the user enters the string "r", then it should "redo" a previously-undone move; it should also output an error using a unicode cyrillic o (to show Java's unicode abilities)if there is no move to redo.

Remember to also add to the oldMoves stack when doing a redo: you should be able to undo your redos as well.