Number Guessing Game

Consider the following number-guessing game:

  1. Player A thinks of a 4-digit secret integer between the range of 1000 and 9999, inclusive.
  2. Player B formulates a guess with regard to the value of the secret number.
  3. Player A reveals how many digits in the guess match those in the secret number.
    (A "match" consists of a correct digit at the correct position.)
  4. If player B's guess matched all four digits, the game is over. Otherwise, go back to step (2) above.

Write a Java program that can play the role of player B efficiently, using only a small number of guesses on average to discover the secret number.

Some starter code is provided, which has a main method that handles user interactions. Complete in the implementation for the constructor and the following methods:

  • public int myGuessIs()
    Tthis method returns a guess. It should return -1 if there is no available guess (see notes below).

  • public int totalNumGuesses()
    This method returns the total number of guesses the program has taken -- in other words, the total number of calls to myGuessIs().

  • public void updateMyGuess (int nmatches)
    This method performs some updates based on the number of matches input by the user, and prepares for the next number to guess.

Additional Notes

  • The number of matches one inputs must be an integer between $0$ and $4$. If it's not, the program will report an invalid input and prompt the user to input the number of matches again.

  • If the user intentionally or unintentionally reports the number of matches incorreclty, be aware this could eventually cause the program to run out of available guesses. In this case, the myGuessIs() function should return $-1$, indicating either the secret number does not exist, or the number of matches was mis-reported at some point.

  • A trivial algorithm could take a guess continuously from $1000$ to $9999$, ignoring the number of matches provided by the user. But this is terribly inefficient, as it could lead to thousands of guesses. Here is a better solution for the number-guessing game: prepare an ArrayList that contains all possible 4-digit numbers that are available guesses. Initially this ArrayList will contain all integers between $1000$ to $9999$ inclusive. The algorithm then randomly picks a number from the array as the first guess, let's call it my guess. The user then compares it with the number in her mind, and provides the number of matches, let's say there are $n$ matches. Next, the program will scan through all numbers currently in the ArrayList, compare each of them with myguess, and delete those that do not result in the same number of matches. Intuitively, the program tries to eliminate numbers that cannot possibly be the correct answer. After this round, the ArrayList will become shorter, and the program will repeat the same steps as above, until it either succeeds in guessing, or the ArrayList becomes empty, indicating that the user must have miscalculated the number of matches at some point.

    Let's say 5432 is the number you have in mind. The program takes a guess, say, 9876, and you tell the program that there are 0 matching digits. This actually gives the program a lot of information: for example, 9111 could not possibly be the secret number because it has 1 match with 9876. In fact, any number that has 9 in the first position cannot possibly be the secret number. So all you need to do is to eliminate numbers according to the current guess and the number of matches provided by the user. The pool of available guesses will shrink very quickly after each round.