binarysearchguessgame.cpp

// GuessNumber.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <functional>

typedef unsigned long Numero;
typedef unsigned long Tentativa;

enum class Estado
{
    Nenhum,
    Menor,
    Maior,
    Igual,
};

struct Faixa
{
    Numero min, max;
};

class IEstrategia
{
public:
    virtual Numero primeira(Faixa&) = 0;
    virtual Numero maior(Faixa&, Numero) = 0;
    virtual Numero menor(Faixa&, Numero) = 0;
    virtual Numero processa(Faixa& faixa, const Estado& estado, Tentativa Tentativa) = 0;
};

class EstrategiaBinaria : public IEstrategia
{
public:
    Numero primeira(Faixa& faixa) override
    {
        return (faixa.max - faixa.min) / 2;
    }

    Numero maior(Faixa& faixa, Numero ultimo) override
    {
        faixa.min = ultimo;
        return (faixa.max - ultimo) / 2 + ultimo;
    }

    Numero menor(Faixa& faixa, Numero ultimo) override
    {
        faixa.max = ultimo;
        return (ultimo - faixa.min) / 2 + faixa.min;
    }

    Numero processa(Faixa& faixa, const Estado& estado, Tentativa Tentativa) override
    {
        switch (estado)
        {
        case Estado::Nenhum:
            return primeira(faixa);
        case Estado::Maior:
            return maior(faixa, Tentativa);
        case Estado::Menor:
            return menor(faixa, Tentativa);
        default:
            return Tentativa;
        }
    }
};

class IAdvinha
{
public:
    virtual Tentativa advinha() = 0;
};

class ComDica : public IAdvinha
{
    const Numero _sorteado;
    const Tentativa _tentativa;
    Faixa& _faixa;
    IEstrategia& _estrategia;

public:
    ComDica(const Numero sorteado, const Tentativa tentativa, IEstrategia& estrategia, Faixa& faixa) :
        _estrategia(estrategia),
        _sorteado(sorteado),
        _tentativa(tentativa),
        _faixa(faixa)
    {
    }    

    Tentativa advinha() override
    {
        auto estado = Estado::Nenhum;
        Numero entrada = _estrategia.primeira(_faixa);
        for (Tentativa i = 0; i < _tentativa; ++i)
        {
            entrada = _estrategia.processa(_faixa, estado, entrada);
            if (_sorteado == entrada)
                return i;

            estado = _sorteado > entrada ?
                Estado::Maior :
                Estado::Menor;
        }
        return _tentativa;
    }
};

int main()
{
    const Numero sorteado = 500;
    const Tentativa tentativaPermitidas = 100;

    Faixa faixa;
    faixa.min = 0;
    faixa.max = 999999;

    EstrategiaBinaria estrategia;

    ComDica comDica(sorteado, tentativaPermitidas, estrategia, faixa);
    auto tentativasUtilizadas(comDica.advinha());

    std::cout << tentativasUtilizadas << "/" << tentativaPermitidas << "\n";
}