5
\$\begingroup\$

I'm trying to write a program where computer attempts to guess a number entered by user. Computer should keep asking until guessed number will be equal to user number.

If you know what can be improved to make this code more readable, if implementation of the binary search algorithm is efficient, let me know!

#include <cstdlib>
#include <iostream>

int main() {
    std::srand(time(nullptr));
    constexpr int MIN = 1;
    constexpr int MAX = 100;
    std::cout << "Choose a number from " << MIN << " to " << MAX << "\n";
    int number;
    std::cin >> number;
    int high = MAX;
    int low = MIN;
    int guess = (high + low) / 2;
    char lessThan = std::rand() % 2 == 0 ? 'y' : 'n';
    char greaterThan = std::rand() % 2 == 0 ? 'y' : 'n';
    while (greaterThan == lessThan)
        greaterThan = std::rand() % 2 == 0 ? 'y' : 'n';
    while (guess != number) {
        if (lessThan == 'y' && greaterThan == 'n') {
            std::cout << "Is your number less than " << guess << "? [y|n]\n";
            std::cin >> lessThan;
            if (lessThan == 'y') {
                high = guess - 1;
                greaterThan = 'n';
            } else if (lessThan == 'n') {
                low = guess + 1;
                greaterThan = 'y';
            }
        } else if (greaterThan == 'y' && lessThan == 'n') {
            std::cout << "Is your number greater than " << guess << "? [y|n]\n";
            std::cin >> greaterThan;
            if (greaterThan == 'y') {
                low = guess + 1;
                lessThan = 'n';
            } else if (greaterThan == 'n') {
                high = guess - 1;
                lessThan = 'y';
            }
        }
        guess = (high + low) / 2;
    }
    std::cout << "I guessed!\n";
    return 0;
}
\$\endgroup\$
0
1
\$\begingroup\$

I don't know, if you can understand all my code, but I would implement the task this way:

#include <iostream>
#include <random>
#include <string>

enum class CompareAnswer { LESS, LESS_OR_EQUAL, GREATER, GREATER_OR_EQUAL };
enum class TruthAnswer { YES, NO };

CompareAnswer ask_user_compare(int compare_with) {
  static auto randfn = []() -> bool {
    static auto dist = std::uniform_int_distribution<>(0, 1);
    static auto gen = std::default_random_engine();
    return static_cast<bool>( dist(gen) );
  };

  char user_input;
  std::cout << "Is your number ";

  if (randfn()) {
    std::cout << "less than " << compare_with << "? [y|n]\n";
    std::cin >> user_input;
    if (user_input == 'y')
      return CompareAnswer::LESS;
    if (user_input == 'n')
      return CompareAnswer::GREATER_OR_EQUAL;
    throw std::runtime_error("invalid answer");
  };

  std::cout << "greater than " << compare_with << "? [y|n]\n";
  std::cin >> user_input;
  if (user_input == 'y')
    return CompareAnswer::GREATER;
  if (user_input == 'n')
    return CompareAnswer::LESS_OR_EQUAL;
  throw std::runtime_error("invalid answer");
};

TruthAnswer ask_user_is(int number) {
  std::cout << "Is your number " << number << "? [y|n]\n";
  char user_input;
  std::cin >> user_input;

  if (user_input == 'y')
    return TruthAnswer::YES;
  if (user_input == 'n')
    return TruthAnswer::NO;
  throw std::runtime_error("invalid answer");
}

int guess_number(const int min, const int max) {
  // std::cout << "\ndebug: min=" << min << " max=" << max << "\n";

  const int median = (min + max) / 2;  // (77+78)/2  =77

  if (median == min) {
    return ask_user_is(min) == TruthAnswer::YES ? min : max;
  };

  switch (ask_user_compare(median)) {
    case CompareAnswer::GREATER:
      return guess_number(median + 1, max);
    case CompareAnswer::GREATER_OR_EQUAL:
      return guess_number(median, max);
    case CompareAnswer::LESS:
      return guess_number(min, median - 1);
    case CompareAnswer::LESS_OR_EQUAL:
      return guess_number(min, median);
    default:
      throw std::logic_error("need case for some of 'enum Answer' ");
  };
};

int main() {
  constexpr int MIN = 0;
  constexpr int MAX = 10000;

  std::cout << "Choose a number from " << MIN << " to " << MAX << "\n";
  int number;
  std::cin >> number;
  if(number < MIN || number > MAX) throw std::runtime_error("Invalid number");

  int guessed = guess_number(MIN, MAX);
  std::cout << "Your number is: " << guessed << "\n";
}

Even though guess_number is recursive function, probability of stack overflow extremely low (cause log(N) complexity). Asking user again instead of throwing exception may be good idea too.

Also: Generally forget about srand, use <random> instead (srand is only for homework)

\$\endgroup\$
0
\$\begingroup\$

A couple points here, first you should always use curly braces { }, even when the code to be executed is 1 line long.

More importantly, you potentially have an infinite loop. Even if you had more than 2 values to choose from, this is a bad approach. A better idea is greaterThan = greaterThan == 'y' ? 'n' : 'y';.

while (greaterThan == lessThan)
    greaterThan = std::rand() % 2 == 0 ? 'y' : 'n';
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.