# Improving the efficiency and design of my number guessing game

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;

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

public void Guess()
{
while (!_isCorrectNumber)
{

_isCorrectNumber = hint.Equals("yes");

if (_isCorrectNumber)
{
continue;
}

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

if (_higher)
{
}
else
{

}
_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 and if I have understood the concept behind a Binary search and implemented it correctly.

-

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 `string`s 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(n2 log n), which is really bad. The n2 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.

-
Thanks svick, I got caught up in reading about the binary search on wikipedia where it says you need an ordered list and didn't actually realise I could use it in this case without. I will implement your suggestions later and update, thanks. –  Aesir Jul 30 '12 at 9:33
Sorry if this seems like a silly question but what is meant by O(n log n)? –  Aesir Jul 30 '12 at 17:04
You mean you don't know the big O notation? In that case, read this answer on SO, it explains in quite a detail, but in plain English. If you want to write fast algorithms, it's quite important to understand the time complexity (which is what the big O represents here) of the algorithm. –  svick Jul 30 '12 at 17:17
No I hadn't heard of it before, thanks for the link. –  Aesir Jul 30 '12 at 17:32
I made some of the changes you suggested here: gist.github.com/f5f7e57353e78ede7433 –  Aesir Jul 30 '12 at 18:59

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.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)
{

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);
}
}
}
``````
-
that's an interesting version, nice to see a recursive implementation and the fact that input and output are passed in as parameters, keeping it nice and flexible. The answer would be even more helpful with an explanation of the changes you made. –  codesparkle Aug 14 '12 at 22:39