Number-guessing game in C#

Question

I have just written a solution to the following problem:

We all know the classic "guessing game" with higher or lower prompts. lets do a role reversal; you create a program that will guess numbers between 1-100, and respond appropriately based on whether users say that the number is too high or too low. Try to make a program that can guess your number based on user input and great code!

I would like suggestions on how I can make my solution less complicated and if there is a more efficient way to solve the problem.

Here is my implementation. I have tried to implement a binary search strategy to solve the problem.

public class Guesser
{
    private List<int> _possibleAnswers = new List<int>();
    private bool _isCorrectNumber = false;
    private bool _higher = false;
    private int _numberOfGuesses = 0;
    private int _answer;

    public Guesser(int min, int max)
    {
        for (var i = min; i <= max; i++)
            _possibleAnswers.Add(i);
    }

    public void Guess()
    {
        while (!_isCorrectNumber)
        {
            var middleOfAnswers = _possibleAnswers.Max() - (_possibleAnswers.Count / 2);

            Console.WriteLine("Is the number {0}?", middleOfAnswers);

            var hint = Console.ReadLine().ToLower();

            _isCorrectNumber = hint.Equals("yes");

            if (_isCorrectNumber)
            {
                _answer = middleOfAnswers;
                continue;
            }

            _higher = hint.ToLower().Equals("higher");

            if (_higher)
            {
                var count = _possibleAnswers.FindIndex(guess => guess.Equals(middleOfAnswers)) + 1;
                _possibleAnswers.RemoveRange(0, count);
            }
            else
            {
                var startIndex = _possibleAnswers.FindIndex(guess => guess.Equals(middleOfAnswers));
                var count = _possibleAnswers.FindIndex(guess => guess.Equals(_possibleAnswers.Max())) - startIndex + 1;

                _possibleAnswers.RemoveRange(startIndex, count);
            }
            _numberOfGuesses++;
        }
        Console.WriteLine("The number was {0} and it took me {1} guess{2}",
            _answer, _numberOfGuesses, _numberOfGuesses > 1 ? "es" : string.Empty);
    }
}

Any suggestions on how I can improve this would be great. I'd also like to know if I have understood the concept behind a binary search and implemented it correctly.

Answer 1

It seems to me that you understand the concept correctly, but your implementation is horrible. That's because you don't need the whole _possibleAnswers list at all, you should just keep two numbers: the lower bound and the upper bound, you can compute everything you need from that.

There are also some smaller issues:

1. Don't use Max() if you know that the maximum number will be always the last one. You can instead use Last(), that will be much faster. And a something similar applies to the way you compute count in the else branch: you already know that FindIndex() will return the index of the last item in the list, you don't need to walk the list twice for that.

2. C# is not Java, you should use == to compare strings instead of Equals(), it's much more readable.

3. You won't need _isCorrectNumber, if you use break instead of continue. That would make your code shorter and less confusing. (I thought something like “wait, why does he continue when he wants to end iterating?” when I read that part of the code.)

Binary search should take only O(log n) time, but your code is O(n² log n), which is really bad. The n² part is caused by using Max() inside of the FindIndex() lambda, if you fixed that by simply computing the Max() once before calling FindIndex() (which is still horrible, see #1 above), it would make your code O(n log n), although that is still bad.

Answer 2

Here is my version. I made it a bit more "functional" - less state, more static (not to be confused with noise). I have two methods instead of one; An enum helps me pack an open-ended input (a string of arbitrary length) into what I really want (tri-state). I tried to minimize RAM usage by initializing the dictionary and the list of allowed keywords only once. At this small size, the dictionary is not a perfect choice in terms of run time; two plain arrays would do a better job, but it is a premature optimization.

The code is also slightly more unit-test friendly since it takes Console.In and Console.Out as parameters. I am still not perfectly happy with the code though. The body of the Guess method should be shorter; the logic and the textual "UI" is still not well separated, plus the language for interacting with a user is not that great. ideally the "engine" would be completely separated from "reporting".

namespace CodeReview
{
    using System;
    using System.Collections.Generic;
    using System.Diagnostics.Contracts;
    using System.IO;
    using System.Linq;

    internal enum Direction : short
    {
        Lower = -1,
        Equal = 0,
        Higher = 1
    }

    public class Guesser
    {
        // Perhaps an overkill? 
        private static readonly Dictionary<string, Direction> inputToDirection = new Dictionary<string,Direction>()
        {
            { "e", Direction.Equal},
            { "equal", Direction.Equal},
            { "h", Direction.Higher},
            { "higher", Direction.Higher},
            { "l", Direction.Lower},
            { "lower", Direction.Lower},
        };

        private static readonly string inputChoices = String.Join(", ", inputToDirection.Keys.OrderBy(v=>v));

        public static void Guess(int min, int max)
        {
            Guess(min: min, max: max, input: Console.In, output: Console.Out);
        }

        // This method exists for testability. Num steps should start with 1.
        public static void Guess(int min, int max, TextReader input, TextWriter output, int numSteps = 1)
        {
            Contract.Requires(min >= 0, "Lower bound cannot be negative.");
            Contract.Requires(max >= 0, "Upper bound cannot be negative.");
            Contract.Requires(min <= max, "Upper bound cannot be less than the lower bound.");

            if (min == max)
            {
                output.Write("The answer must be ");
                output.WriteLine(min);
                output.WriteLine("It took " + numSteps + " steps to solve.");
                return;
            }

            int middle = (min + max) / 2;
            output.WriteLine("Is the number {0} (lower|l equal|e, or higher|h?", middle);
            Direction direction = ScanDirection(input: input, output: output);
            if (direction == Direction.Equal)
            {
                output.WriteLine("It took " + numSteps + " steps to solve.");
                return;
            }

            if (direction == Direction.Higher)
            {
                min = middle;
            }
            else
            {
                max = middle;
            }

            Guess(min, max, input, output, numSteps + 1);
        }

        // A persistent user can turn this method into an infinite loop.
        private static Direction ScanDirection(TextReader input, TextWriter output)
        {
            string hint = Console.ReadLine().Trim().ToLower();

            Direction result;
            if (inputToDirection.TryGetValue(key: hint, value: out result))
            {
                return result;
            }

            output.WriteLine("Come again? The choices are: {0}.", inputChoices);
            return ScanDirection(input: input, output: output);
        }
    }
}