CMPSCI 187 / Fall 2018
Guess A Number (LinkedList version)
Mark Corner and Joe Chiu
1
CMPSCI 187 / Fall 2018 Guess A Number (LinkedList version)
CMPSCI 187 / Fall 2018 Guess A Number (LinkedList version)
Overview
In this project you will implement a game called Guess A Number. The goal is for the computer to guess a 4-digit
number given the game rules. You will write an implementation using linked lists.
Learning Goals
• Develop your understanding of linked list and its implementation.
• Continue to practise using JUnit tests and Java debugging tools to help you debug and correct your code.
Note: sections marked [Common] below are shared among all projects. We include them here for the completeness of
the description, but they present the same information across all projects.
General Information [Common]
Reminder: Copying partial or whole solutions, obtained from other students or elsewhere, is academic dishonesty.
Do not share your code with your classmates, and do not use your classmates’ code. If you are confused about what
constitutes academic dishonesty you should re-read the course policies. We assume you have read the course policies
in detail and by submitting this project you have provided your virtual signature in agreement with these policies.
• For some projects, it may be useful for you to write additional java files. Any java file you write MUST be
placed in the provided src directory of your Eclipse project.
• When submitting your project, be sure to remove all compilation errors. Any compilation errors will cause
the autograder to fail to run, and consequently you will receive a zero for your submission. No Exceptions!
In the test directory, we provide several JUnit tests that we refer to as the public tests. We recommend you run the
tests often and use them as starting points to test your project. In addition, some of the java files come with their own
main functions. You can run them as Java applications to interact with the project.
Be aware that the autograder will use a more comprehensive set of tests (referred to as private tests) to grade your
project. These tests are hidden from you. We recommend that you think about possible test cases and add new @Test
cases to your public test files as part of your programming discipline. In particular, you should consider:
• Do your methods handle edge cases such as integer arguments that may be positive, negative, or zero. Many
methods only accept arguments that are in a particular range.
• Does your code handle cases such as when an array or list is empty, or has reached full capacity?
More complex tests will be project-specific. To build good test cases, think about ways to exercise methods. Work out
the correct result for a call of a method with a given set of parameters by hand, then add it as a test case.
Import Project into Eclipse [Common]
Begin by downloading the starter project and importing it into your workspace. It is very important that you do not
rename this project as its name is used during the autograding process. If the project is renamed, your assignment will
not be graded, and you will receive a zero.
The imported project may have some compilation errors, but these should not prevent you from getting started. Specifically, we may provide JUnit tests for classes that do not yet exist in your code. You can still run the other JUnit tests.
After completing your code, the compilation errors should be gone.
The project should normally contain the following root items:
Page 3 of 6
CMPSCI 187 / Fall 2018 Guess A Number (LinkedList version)
src This is the source folder where all code you are submitting must go. You can change anything you want in this
folder (unless otherwise specified), you can add new files, etc.
support This folder contains support code that we encourage you to use (and must be used to pass certain tests). You
must not change or add anything in this folder. To help ensure that, we suggest that you set the support folder
to be read-only. You can do this by right-clicking on it in the package explorer, choosing Properties from the
menu, choosing Resource from the list on the left of the pop-up Properties window, unchecking the Permissions
check-box for Owner-Write, and clicking the OK button. A dialog box will show with the title “Confirm recursive
changes”, and you should click on the “Yes” button.
test The test folder where all of the public unit tests are available. You can feel free to add your own tests here.
JUnit 4 A library that is used to run the test programs.
JRE System Library This is what allows Java to run; it is the location of the Java System Libraries.
If you are missing any of the above or if errors are present in the project (other than as specifically described below),
seek help immediately so you can get started on the project right away.
Guess A Number Game
The goal of this game is to guess a 4-digit number according to the game rules. There is a host and a player. The game
rules are the same as the previous project, but for the sake of completeness, we repeat the rules below:
1. The host picks a 4-digit number (i.e. any number between 1000 and 9999). Let’s call this the groundtruth
number. In the following example, let’s pick 5432 as the groundtruth.
2. The player takes a guess, for example, 1234.
3. The host tells the player how many digits of the guess number match the groundtruth. A match is defined as the
same digit in the same position. For example, 1234 and 5432 have 1 match (at position 3); 2345 and 5432 have
0 match – even though it’s the same set of digits, none matches in the exact same position.
4. Based on the number of matches, the player performs some update and takes another guess, say 5533.
5. The host again tells the player the number of matches. This time, 5533 and 5432 have 2 matches.
6. Repeat steps 4 and 5 until the game is over. The game is over when the host tells the player that all 4 digits are
matched. Therefore the player has found the groundtruth number.
Ideally, you want to design an algorithm that allows the player to succeed with as few guesses as possible. In the next
page you will find the description of an algorithm you should implement for this project.
Explore the Starter Code
First, explore the starter code as is. In the src/guessme directory, you will find LinkedListGame.java and
LLIntegerNode.java. These two files are where you will be completing the starter code to implement this game.
For each method to be implemented, we have provided inline comments to help you understand the method, and the
expected input and output.
In support/guessme folder, you will find HostGame.java and PlayGame.java. If you run HostGame.java,
the computer will host the game, and you will interact with the computer as a player. If you run PlayGame.java,
the computer will be the player and you will be the host.
Page 4 of 6
CMPSCI 187 / Fall 2018 Guess A Number (LinkedList version)
LinkedList-based Implementation and Testing
You will complete this project by providing a LinkedList-based implementation. Since the goal of this project is to
practise implementing linked list, you must use your own implementation of linked list. You may NOT use Java
arrays of any type, and you may NOT use classes from the java.util package. The autograder will give a
grade of 0 if you violate the requirement.
You are allowed to add additional methods if necessary. However, do NOT change any provided method (e.g. method
name, parameters, return type), as the autograder will fail if any provided methods is altered. Also, do NOT make any
of your class variables static, as doing so will cause problems with multiple instances. Finally, do NOT create any
new file – any new file you create will be ignored by the autograder.
The methods that you are required to implement are clearly marked by //TODO in LinkedListGame.java and
LLIntegerNode.java. Carefully read the comments therein to understand what you need to do. The first step is to
complete LLIntegerNode.java by defining the data members of this class, and provide the methods require. You
won’t be able to run the JUnit tests until you complete this class. Specifically, you need to provide a constructor, and
the following four methods: setInfo, getInfo, setLink, getLink. These are standard methods in a linked
list node class that we covered in lectures. Next, go to LinkedListGame.java, and complete the numMatches
method as in the last project.
Solution Algorithm
The solution algorithm you should implement is the same as the last project, except that you must store data in linked
lists, and not in arrays. More specifically: 1) You should store prior guessses in a linked list, and the nodes in the list
must follow the order of prior guesses. For example, if the prior guesses are 1000, 2111, 3222 in that order, the nodes
must follow the same order; 2) You should store the candidate numbers also in a linked list, and the nodes must
follow the order of numbers (i.e. from the smallest to the largest). Note that this is different from the last project:
in the last project, you mark the eliminated numbers using a boolean array; this time, you store the candidate numbers
(i.e. the complement set of the eliminated numbers) in a linked list. The reason is that choosing the next guess is much
simpler this way, as you will see below.
At the start of the game, you should create the candidate list, which contains all numbers from 1000 to 9999, in that
order. Since any of them is equally likely to be the groundtruth, your algorithm simply chooses the first candidate (i.e.
the head), 1000, as the initial guess. Therefore the getGuess() method will initially return 1000.
The host compares the guess with the groundtruth, and tells the player how many matches there are. The number
of matches is passed to the player through the updateGuess method. What this method should do is to examine
all candidate numbers, and keep those that have the same number of matches with the player’s current guess.
Why? Let’s say the groundtruth is 4321, and the initial guess is 1000. The host tells the player there is 0 match. This
actually gives the player a lot of information, that is, a number remains a candidate if and only if it has 0 match with
the player’s current guess (1000). If the match is not 0, that number cannot possibly be the groundtruth and hence
should be removed from the candidate list.
You haven’t learned how to remove/delete nodes from a linked list yet. That’s ok, you don’t need to – instead, you can
simply create a new linked list that contains all numbers from the previous linked list except the numbers that should
be removed. Specifically, in your updateGuess method, you should create a new candidate list, then traverse the
existing candidate list and insert only those numbers that remain candidates to the new list. Finally the newly created
list replaces the old list. This way, you can achieve the effect of removing nodes without actually implementing
removal. Note that because the list must preserve the order of the numbers, you should implement insertion at the
end of the linked list (not front insertion).
Choosing the next guess now becomes trivial: the first candidate in the list (i.e. the head element) is the next number
to guess. Continuing from the above example, 2111 shuold be at the head of the candidate list, and is therefore what
Page 5 of 6
CMPSCI 187 / Fall 2018 Guess A Number (LinkedList version)
getGuess method should return the next round it’s called. As the game goes on, the candidate list will quickly
shrink, and eventually the player will find the groundtruth number.
There are several additional methods you should implement. At any time, we can call int numGuesses() to return
the number of guesses taken so far, LLIntegerNode priorGuesses() to return the head of the prior guesses
list, and String priorGuessesString() to return the prior guesses as a comma-separated string. You will
also need to implement boolean isOver() to indicate whether the game is over, and reset() to reset the data
structures and variables so we can play again. Once these methods are implemented, you can run PlayGame.java
to let computer play as a player, and run all public JUnit tests to help you check if there are any mistakes in your
implementation. The private JUnit tests will call reset() and isOver() repeatedly to play the game over and
over again, so you must ensure that these methods are implemented correctly.
Erroneous Situation What happens if the host makes a mistake and mis-calculates the number of matches? This can
lead to a situation where no candidate is left (i.e. all numbers are eliminated). Here is one example: let’s say the host
tells the player that the groundtruth has 3 matches with 1234, but 1 match with 1235. This is impossible because no
such number exists that has 3 matches with 1234 but only 1 match with 1235. The updateGuess method can easily
detect this situation when it finds that the candidate list is empty (i.e. no candidate is left). In this situation it should
return false indicating a state of error.
Export and Submit [Common]
When you have completed this project, you should export an archive file containing the entire Java project. To do
this, click on the guessme-list-student project in the package explorer. Then choose “File → Export” from the
menu. In the window that appears, under “General” choose “Archive File”. Then choose “Next” and enter a destination
for the output file. Be sure that the project is named guessme-list-student (otherwise you may be exporting
the wrong project!). Save the exported file with the zip extension.
Once you have the zip file ready, you can submit it to the online autograder (Gradescope). Please see the course
website and/or documentation explaining how to use the online autograder. If you have any questions please be
prompt in asking the course staff before it is too late to submit your solution. If you encounter any errors that look like
the autograder failed and not your project, please let the instructors know.