Guess A Number (Array version) Solution

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 Java arrays.




Learning Goals




Exercise your understanding of Java arrays and classes.




Learn to break a larger problem down into a manageable set of methods.




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. Specif-ically, 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:




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 project is designed such that the computer can be either the host or the player. The game is as follows:




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.



The player takes a guess, for example, 1234.



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.



Based on the number of matches, the player performs some update and takes another guess, say 5533.



The host again tells the player the number of matches. This time, 5533 and 5432 have 2 matches.



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. A trivial solution could take guesses continuously from 1000 to 9999, ignoring the information that the host tells the player in each round. But this is too brute-force and would result in thousands of guesses, which is unacceptable. How can you design a better algorithm to solve the problem much faster? Such an algorithm should make good use of the information about the number of matches that the host tells the player in each round of the game. Take a break and think about a solution on your own. In the next page you will find the description of an algorithm you MUST implement for this project.




Explore the Starter Code




First, explore the starter code as is. In the src/guessme directory, you will find ArrayGame.java. This is 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, what are 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. You can try them out first, but because the starter code is not complete, the game will never end. You can terminate the running program by pressing the red square in the top left of the console window, as the image below shows:






















Array-based Implementation and Testing




You will complete this project by providing an array-based implementation in ArrayGame.java. The requirement is that you can only use primitive type Java arrays (such as int[], boolean[]). You may NOT use any Java classes that implement the Collection interface (such as ArrayList, Vector). The list of such classes can be found at: http://docs.oracle.com/javase/8/docs/api/java/util/Collection.html. The autograder will give a grade of 0 if you use any of these classes.




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 – your entire implementation must be in ArrayGame.java. Any new file you create will be ignored.




The methods that are required in your implementation are clearly marked by //TODO in ArrayGame.java. Care-fully read the comments therein to understand what you need to do for each method. The first method you should implement is int numMatches(int a, int b). This method calcualtes the number of matches between two integers a and b. You can assume that both integers are 4-digits long. The return value must be between 0 and 4. We have provided some public JUnit tests (in test/guessme/ArrayGamePublicTest.java) for the purpose of testing this method. Feel free to write additional tests yourself. When implementing this method, you should use basic integer arithmetic (e.g. + =%). Do NOT convert the integer to String, as doing so may cause your program to time out during some of the large private tests (see explanation later in this document). Once the numMatches method is correctly implemented, you can run HostGame.java in support/guessme folder to play this game as a player. See how many rounds it takes you to successfully find the number that the computer picks.




Solution Algorithm




Described here is the solution algorithm (based on the principle of elimination) that you MUST implement. At the start of the game, all numbers between 1000 and 9999 are candidates because none of them has been ruled out yet. Since any of them is equally likely to be the groundtruth, the algorithm simply chooses the first candidate, 1000, as the initial guess. Therefore the getGuess() method will initially return 1000 as the first guess.




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 palyer through the updateGuess method. What this method does is to examine all candidate numbers, and eliminate those that do not 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. What information do we get from this? Actually a lot: for example, any number that has a leading 1 cannot possibly be the groundtruth, otherwise it would have had at least 1 match with the player’s current guess (1000), which contradicts with the 0 match that the host tells you. Similarly, any number whose second, third, or fourth digit is 0 cannot possibly be the groundtruth. Therefore all such numbers should be eliminated. In other words, the only numbers that should remain are those that have 0 matches with the player’s guess 1000.




The updateGuess method then chooses the first number (starting from 1000) that has not been eliminated and that will be what getGuess method returns the next round it’s called. Continuing from the above example, 2111 will be the next guess, because this is the first number (starting from 1000) that still remains a candidate (i.e. not eliminated yet). In the second round, the host tells the player that there is exactly 1 match. The player will update the guess in






Page 5 of 6
the same way as before: it eliminates any number whose match with the current guess (2111) is not 1. As an example, 3211 will be eliminated because if it were the groundtruth, the host would have said 2 matches.



As the game goes on, the player will quickly eliminate many numbers in each round, narrowing down the list of possible candidates. In terms of data structures, you need to create a Java array to store the list of eliminated numbers. You can search in this array to find whether a number has been eliminated or not, and this list will grow in each round of the game. You should create a boolean array that stores a flag for each number between 1000 and 9999, indicating whether it’s eliminated or not. This allows you to quickly find out if a number has been eliminated or not. Remember, you must use primitive type arrays and you CANNOT use any Collection type Java classes (such as ArrayList, Vector etc.).




You will need an additional array that stores the list of guesses. At any time, we can call the int[] priorGuesses () method to return the list of guesses as an integer array, and int numGuesses() to return the number of guesses taken so far. If you have implemented the solution correctly, it should take less than 18 guesses, no matter which groundtruth number the host picks. Finally, you will 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. The private tests will call reset() and play the game over and over again, so make sure it’s implemented correctly. Once these methods are implemented, you can run PlayGame.java to let computer play as a player, and run all public JUnit tests.




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 errorneous situation when it finds that no candidate is left (i.e. all numbers have been eliminated). In this situation it should return false indicating a state of error.




Implementation Efficiency In order to direct you to write efficient code, some of the large private tests in this project have a timeout constraint. That is, if your program takes too long to run these large tests, they will time out and count as failure. The timeout is set intentionally to direct you to think about efficient implementation and avoid using extremely convoluted logic. Efficient solutions also generally lead to more elegant and shorter program code.




Optimality The algorithm described above is by no means optimal. For example, it always takes 1000 as the initial guess, and always picks the first candidate (starting from 1000) as the next guess. For certain groundtruth numbers, such as 9876, it can take many rounds. You may think that randomizing the guess can improve it, but surprisingly the gain is not much, considering that the groundtruth is equally likely to be any number. We will leave these improvements for you to explore on your own, but for the autograde you MUST implement the algorithm exactly as described above.




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

























Page 6 of 6