CSC 421: Algorithm Design and Analysis
Spring 2019

HW2: Decrease & Conquer Guessing

As a child, you probably played a guessing game where one person thinks of a number and the other tries to guess it, receiving only "TOO HIGH" or "TOO LOW" responses until the number is guessed. The goal is to determine the number in the fewest guesses. This game has been the cause of numerous playground fights, as it is possible for the person who picked the number to cheat without any way of proving it. For example, suppose the number picker selects 37 as the secret number. If the other player luckily guesses 37 on their first guess, there is nothing to stop the picker from changing the number to 38 and responding "TOO LOW." Of course, the picker does need to be consistent with their responses, or else their dishonesty may be revealed. For example, responding "TOO HIGH" on a guess of 38 would be incinsisent with the earlier response, and prove that the picker cheated.

For this assignment, you are to write a program that simulates guessing games, where the computer is the number picker and the user is the guesser. The program should allow for multiple games to be played and each game may have a different range of numbers to guess from (always starting at 1). For example, the output of your program should look as below, with user input highlighted in bold:

Let's play a guessing game.
Enter the maximum possible value (< 1 to quit): 20
Enter your guess: 8
Enter your guess: 15
Enter your guess: 12
Enter your guess: 13
Enter your guess: 14
You got it in 5 guesses.

How about another game?
Enter the maximum possible value (< 1 to quit): 3
Enter your guess: 2
Enter your guess: 1
You got it in 2 guesses.

How about another game?
Enter the maximum possible value (< 1 to quit): 0
Thanks for playing.

You are to implement two different strategies for the computer to play the game: FairGuessingGame is an honest strategy, where the computer picks a random number from the specified range and sticks with that number throughout; UnfairGuessingGame is a dishonest strategy, where the computer can essentially change the number to disadvantage the player. For example, if the initial range is 1..100 and the player guesses 30, the dishonest computer would respond "TOO LOW" since this leaves 70 possible numbers (31..100), whereas answering "TOO HIGH" would leave only 29 possible numbers (1..29). If the player subsequently picks 80, the dishonest computer would respond "TOO HIGH", since 31..79 is a larger range than 81..100. Note that the computer's responses must remain consistent, so it can't respond that 75 is "TOO LOW" if it already said 70 is "TOO HIGH." This means that the player should eventually be able to pin down even the dishonest computer when the range of possible values gets down to a single number.

Both of your classes for playing the game should implement the GuessingGame interface, shown below. In particular, each class should have a makeGuess method, which takes a guess as input and returns a response (either "TOO LOW", "TOO HIGH" or "CORRECT"), and a numGuessesSoFar method, which returns the number of guesses the player has made. The fields and implementation details for each class are up to you.

public interface GuessingGame {
    public String makeGuess(int guess);
    public int numGuessesSoFar();

Since both classes will implement the GuessingGame interface, switching from one strategy to the other should require only minimal editing. Within your driver there should be a declaration and initialization of a GuessingGame variable for playing the game. If that variable is initialized to be a FairGuessingGame, then the honest strategy will be used:

GuessingGame game = new FairGuessingGame(maxValue);

If the type on the right-hand side is changed to UnfairGuessingGame, then the dishonest strategy will be used:

GuessingGame game = new UnfairGuessingGame(maxValue);

No other edits should be required to switch between the two strategies. As always, you should follow standard coding practices, including the use of meaningful variable names, consistent indentation, and javadoc comments for each class and method.