Interactor with classes

interact.cpp

// Пример применения иерархии классов для отладки интерактивной задачи
// (C) Петр Калинин, GNU GPL :)

// Достоинства подхода, приведенного ниже, состоят в следующем:
// - Для использования другого "интерактора" надо просто закомментировать
//   одну и раскомментировать другую строчку
// - Можно в одной программе иметь много "интеракторов" и переключаться между ними как надо,
//   не боясь запутаться
// - Все переменные, относящиеся к внутренностям "интерактора", можно держать внутри
//   класса и не захламлять глобальное пространство
// - Один из "интеракторов" реазлизует требуемый протокол взаимодействия с проверяющей программой,
//   поэтому перед сдачей программы на проверку надо просто сменить "интерактор"

// Предположим, задача:
// пользователь загадал целое число от 1 до N включительно
// программа должна его угадать, делая запросы пользователю
// один запрос --- это число X
// если X меньше загаданного числа, то пользователь вводит -1
// если X больше, то 1
// если X равно, то 0, и на этом выполнение программ должно завершиться
// Перед тем, как начать угадывать, пользователь вводит число N
// Пример сессии (ввод пользователя показан как >, вывод программы как <)
// > 5
// < 3
// > -1
// < 4
// > -1
// < 5
// > 0

#include <iostream>

using namespace std;

// общий интерфейс класса для взаимодействия с пользователем или "проверяющей" частью программы
class Interactor {
public:
    Interactor() {}
    virtual ~Interactor() {}
    virtual int init() = 0; // сообщает программе N
    virtual int make_guess(int x) = 0; // возвращает 0, 1, или -1
};

// для работы с клавиатурой и для сдачи программы на проверку
class KeyboardInteractor : public Interactor {
public:
    KeyboardInteractor() : Interactor() {}
    virtual int init() { 
        int n;
        cin >> n;
        return n;
    }
    virtual int make_guess(int x) {
        cout << x << endl; // endl вроде делает flush
        int res;
        cin >> res;
        return res;
    }
};

// для простого тестирования
class TestingInteractor : public Interactor {
public:
    int n, y;
    TestingInteractor() : Interactor() {
        cout << "Initializing TestingInteractor, please input N and Y" << endl;
        cin >> n >> y; 
    }
    virtual int init() { 
        cout << "Initialized with n=" << n << endl;
        return n; 
    }
    virtual int make_guess(int x) {
        cout << "Guess attempt " << x << endl;
        if (x == y) return 0;
        else if (x < y) return -1;
        else return 1;
    }
};

// можно сделать еще каких-нибудь наследников от Interactor,
// например чтобы реализовывать сложные стратегии:

// Например, всегда возвращаем тот интервал, который больше
class GreedyInteractor : public Interactor {
public:
    int n, l, r;
    bool guessed;
    GreedyInteractor() : Interactor() {
        cout << "Initializing GreedyInteractor, please input N" << endl;
        cin >> n;
        // l is the minimal possible value, r in the maximal possible
        l = 1;
        r = n;
        guessed = false;
    }
    virtual ~GreedyInteractor() {
        if (!guessed) cout << "Not guessed!" << endl;
    }
    virtual int init() { 
        cout << "Initialized with n=" << n << endl;
        return n; 
    }
    virtual int make_guess(int x) {
        cout << "Guess attempt " << x << endl;
        if (x < l) return -1;
        if (x > r) return 1;
        if (l == r) // then definetly x == l && x == r
        {
            guessed = true;
            return 0; 
        }
        if (x - l > r - x) {
            r = x - 1;
            return 1;
        } else {
            l = x + 1;
            return -1;
        }
    }
};

// основная программа

Interactor* in; // глобальная переменная, чтобы можно было получать доступ из функций, если надо

int main() {
    // Ниже --- ключевое место, где выбирается интерактор
    // чтобы сменит интерактор, надо просто выбрать нужную строчку
    // нигде больше ничего менять не надо!
    KeyboardInteractor theIn; // для отправки на проверку
    //TestingInteractor theIn; // для тестирования
    //GreedyInteractor theIn; //  для тестирования
    
    in = &theIn; // эта строка должна быть всегда
    // переменная theIn больше не используется!
     
    // решение
    int n = in->init(); // все взаимодействие идет через переменную in
    int l = 0, r = n + 1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        int res = in->make_guess(m);
        if (res == 0) break;
        if (res < 0) l = m;
        else r = m;
    }
}