password_crackers.cpp

#include <iostream>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <iterator>
#include <functional>
#include <string>
#include <random>
#include <list>

using std::cout;
using std::endl;
using std::string;
using std::inner_product;
using std::minmax_element;
using std::accumulate;
using std::generate;
using std::begin;
using std::end;
using std::list;
using std::tuple;

const char symbols[] = " abcdefghijklmnopqrstuvwxyz"
                        "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

typedef std::uniform_int_distribution<string::size_type>
        distribution_position;
typedef std::uniform_real_distribution<float>
        distribution_score;


string::value_type rand_char()
{
    auto size = sizeof(symbols) - 2;
    auto source = std::random_device()();
    auto gen = std::mt19937(source);
    auto dist = distribution_position(0, size);

    auto rand = std::bind(dist, gen);

    return symbols[rand()];
}


class Checker
{
public:
    explicit Checker(string::size_type n): m_secret(n, '\0'),
        m_counter(0)
    {
        generate(begin(m_secret), end(m_secret), rand_char);
    }

    Checker(const char* secret): m_secret(secret),
        m_counter(0)
    {}

    string::size_type operator() (const string& version) const
    {
        m_counter++;

        return inner_product(
                    begin(m_secret), end(m_secret),
                    begin(version),
                    0,
                    std::plus<string::size_type>(),
                    std::not_equal_to<string::value_type>()
                    );
    }

    string::size_type size() const
    {
        return m_secret.size();
    }

    unsigned int counter() const
    {
        return m_counter;
    }

    void reset_counter()
    {
        m_counter = 0;
    }

private:
    string m_secret;
    mutable unsigned int m_counter;
};


string solve_random(const Checker& checker)
{
    string guess(checker.size(), '\0');

    generate(begin(guess), end(guess), rand_char);
    auto errors = checker(guess);

    for (auto& c: guess)
    {
        const auto c_old = c;

        auto errors_new = errors;

        while (errors_new == errors)
        {
            c = c_old;
            while (c == c_old) c = rand_char();
            errors_new = checker(guess);
        }

        if (errors_new > errors)
        {
            c = c_old;
        }
        else
        {
            errors = errors_new;
        }
    }

    return guess;
}


string solve_random1(const Checker& checker)
{
    string answer(checker.size(), '\0');
    string guess(checker.size(), '\0');
    string::size_type correct_symbols = 0;
    string::size_type errors = checker.size();

    while (correct_symbols < checker.size())
    {
        string::size_type errors_new = errors;

        while (errors == errors_new)
        {
            for (string::size_type i=0; i < answer.size(); i++)
            {
                if (answer[i]) continue;
                guess[i] = rand_char();
            }

            errors_new = checker(guess);
        }
        errors = errors_new;

        for (string::size_type i=0;
             i < answer.size() && correct_symbols < answer.size();
             i++)
        {
            if (answer[i]) continue;

            auto c = guess[i];
            while(guess[i] == c) guess[i] = rand_char();

            errors_new = checker(guess);

            if (errors_new == errors) continue;

            if (errors_new < errors)
            {
                answer[i] = guess[i];
            }
            else
            {
                answer[i] = c;
            }

            correct_symbols++;
            errors = errors_new;
        }
    }
    return answer;
}


class ScoredString
{
public:
    ScoredString(string::size_type len, const Checker& checker):
        m_string(len, '\0')
    {
        generate(begin(m_string), end(m_string), rand_char);
        m_value = checker(m_string);
    }

    ScoredString(const string& s, const Checker& checker)
    {
        m_string = s;
        m_value = checker(m_string);
    }

    ScoredString(string::size_type value): m_value(value) {}

    void mutate(const string::size_type where)
    {
        const auto c = m_string[where];
        while(c == m_string[where])
        {
            m_string[where] = rand_char();
        }
    }

    string::size_type mutate(const string::size_type where,
                             const Checker& checker)
    {
        mutate(where);
        m_value = checker(m_string);
        return m_value;
    }

    void cross(const ScoredString& sc,
               const string::size_type where)
    {
        copy(begin(sc.m_string) + where, end(sc.m_string),
             begin(m_string) + where);
    }

    string::size_type cross(const ScoredString &sc,
                            const string::size_type where,
                            const Checker& checker)
    {
        cross(sc, where);
        m_value = checker(m_string);
        return m_value;
    }

    operator string ()
    {
        return m_string;
    }

    operator bool ()
    {
        return m_string.size();
    }

    string::size_type value() const
    {
        return m_value;
    }

    void score(float s)
    {
        m_score = s;
    }

    float score() const
    {
        return m_score;
    }

private:
    string m_string;
    string::size_type m_value;
    float m_score;
};


bool compare_values(const ScoredString& a, const ScoredString& b)
{
    return a.value() < b.value();
}


string solve_ga(const Checker& checker, bool until_found=false)
{
    const unsigned int len = checker.size();
    const unsigned int max_cycles = std::max(len * 10u, 70u);
    const unsigned int def_population = std::max(len, 15u);
    const unsigned int max_population = def_population * 2;

    const unsigned int min_population = def_population - 1;
    const string::size_type abs_min = 0;

    const float delete_score = 0.9;
    const float delete_probs[] = {0.95, 0.01};

    const float mutate_score = 0.95;
    const float mutate_probs[] = {0.05, 0.8};
    const string::size_type mutate_points = 1 + len / 10;

    const float elite_score = 0.95;
    const float elite_probs[] = {0.05, 0.9};

    list<ScoredString> population;
    list<ScoredString> elite;

    ScoredString best(len);

    auto check_best = [& best, abs_min] (const ScoredString& s)
    {
        if (abs_min == s.value())
        {
            best = s;
            return true;
        }
        if (s.value() <= best.value())
        {
            best = s;
        }
        return false;
    };

    auto source = std::random_device()();
    auto gen = std::mt19937(source);
    auto dist_score = distribution_score(0.0, 1.0);
    auto dist_position = distribution_position(0, len);
    auto rand_score = std::bind(dist_score, gen);
    auto rand_position = std::bind(dist_position, gen);

    for (unsigned int population_id = 0;
         until_found || population_id < max_cycles;
         population_id++)
    {
        // estimate how many new elements we need
        float gen_factor = 1.0;
        if (population.size() > min_population)
        {
            gen_factor = float(population.size()) /
                    (population.size() + max_population) /
                    max_population;
        }

        // generate newbies
        for (unsigned int i = 0; i < def_population; i++)
        {
            if (rand_score() > gen_factor) continue;
            population.emplace_back(len, checker);
            if (check_best(population.back())) return best;
        }

        auto minmax = minmax_element(begin(population),
                                     end(population),
                                     compare_values);
        float min_value = minmax.first->value();
        float max_value = minmax.second->value();

        if (min_value == max_value) min_value = abs_min;

        // scores
        for (auto& g: population)
        {
            g.score((float(max_value) - g.value()) /
                    (max_value - min_value));
        }

        // estimate common resources
        float delete_factor = 1.0;
        if (population.size() > max_population)
        {
            delete_factor = float(max_population) /
                    population.size();
        }

        for (auto it = begin(population);
             it != end(population);
             it++)
        {
            auto& g = *it;
            auto score = g.score();

            // mutation
            auto mutate_prob = mutate_probs[score > mutate_score];
            if (mutate_prob > rand_score())
            {
                population.push_front(g);

                for (string::size_type i = 1;
                     i < mutate_points;
                     i++)
                {
                    population.front().mutate(rand_position());
                }
                population.front().mutate(rand_position(),
                                          checker);

                if (check_best(population.front())) return best;
            }

            // elite selection
            auto elite_prob = elite_probs[score > elite_score];
            if (elite_prob > rand_score())
            {
                elite.push_back(g);
            }

            // delete bad
            auto delete_prob = delete_probs[score > delete_score];
            if (delete_prob > rand_score() * delete_factor)
            {
                // tric. fix by using shared_ptrs
                if (it == begin(population)) continue;

                auto prev = it++;
                population.erase(prev, it);
                it--;
            }
        }

        // estimate resources for reproduction
        float cross_factor = 1.0;
        auto required = elite.size() * elite.size() / 2;

        if (required > def_population)
        {
            cross_factor = float(def_population) / required;
        }

        // crossingover
        if (best) elite.push_back(best);
        for (auto it = begin(elite); it != end(elite); it++)
        {
            auto next = it;
            next++;
            for (auto it1 = next; it1 != end(elite); it1++)
            {
                if (rand_score() > cross_factor) continue;

                population.push_front(*it);
                population.front().cross(*it1,
                                         rand_position(),
                                         checker);
                if (check_best(population.front())) return best;
            }
        }

        elite.clear();
    }
    return best;
}


string solve(const Checker& checker)
{
    return solve_ga(checker, false);
}


int main()
{
    string x;

    typedef decltype(&solve) solve_function;
    typedef tuple<const char*, solve_function, list<int>> record;

    record fs[] =
    {
        record("Genetic algorithm", solve, {}),
        record("Random chars", solve_random, {}),
        record("Random chars+strings", solve_random1, {}),
    };

    for (unsigned int len = 5; len < 150; len+=5)
    {
        cout << "len: " << len << endl;

        for (unsigned int j = 0; j < 5; j++)
        {
            Checker checker(len);

            for(auto& p: fs)
            {
                auto func = std::get<1>(p);

                cout << std::get<0>(p) << '\t';
                cout.flush();

                x = func(checker);
                //cout << x << endl;
                std::get<2>(p).push_back(checker.counter());

                cout << checker.counter() << '\t';

                auto result = checker(x);

                if (result)
                {
                    cout << "Not found (" << checker(x) << ')';
                }
                else
                {
                    cout << "Ok";
                }
                cout << endl;

                checker.reset_counter();
            }
        }

        cout << endl << "Average for len " << len << endl;

        for(auto p: fs)
        {
            auto& L = std::get<2>(p);
            auto& name = std::get<0>(p);

            cout << name << '\t'
                 << accumulate(begin(L), end(L), 0) / L.size()
                 << endl;
            L.clear();
        }
        cout << endl;
    }
    return 0;
}