Genetic algorithm for puzzle optimization

// g++ -std=c++11
#include <string>
#include <cstdio>
#include <cstring>
#include <vector>
#include <random>
#include <unordered_map>
#include <algorithm>

#define MAX_CODE_LENGTH (100)

typedef unsigned char word;
#define WORD_SIZE (256)

bool balanced(const std::string& code)
{
    unsigned int level = 0;
    for (const char &c : code)
    {
        if (c == '[')
        {
            level++;
        }
        else if (c == ']')
        {
            if (level == 0)
            {
                return false;
            }
            level--;
        }
    }
    return level == 0;
}

bool evaluate(const std::string& code, size_t steps, word *result, std::vector<word>& data)
{
    size_t dp = 0, ip = 0;
    size_t step = 0;
    size_t length;

    *result = -1; // initialize, in case we have to error out
    if (!balanced(code))
    {
        return false;
    }

    length = code.length();

    data.clear();
    data.push_back(0);

    while (ip < length && step < steps)
    {
        char instruction = code[ip];
        switch (instruction)
        {
            case '>':
                // Increment data pointer.
                // If this is a new memory cell, add a zero.
                dp++;
                if (dp >= data.size())
                {
                    data.push_back(0);
                }
                break;
            case '<':
                // Decrement data pointer.
                // Fail if this would go negative.
                if (dp == 0)
                {
                    return false;
                }
                dp--;
                break;
            case '+':
                // Increment the data value at the current cell, mod 256.
                data[dp] = (data[dp] + 1) % WORD_SIZE;
                break;
            case '-':
                // Increment the data value at the current cell, mod 256.
                data[dp] = (data[dp] + WORD_SIZE - 1) % WORD_SIZE;
                break;
            case '.':
                // "Print out this character." Really, just return.
                *result = data[dp];
                return true;
            case ',':
                // "Get input." Really, just set to zero.
                data[dp] = 0;
                break;
            case '[':
                // If the data is zero, then go to the matching ']'.
                // The code has already been tested to be balanced,
                // so this will be guaranteed to terminate nicely.
                if (data[dp] == 0)
                {
                    unsigned int level = 1;
                    while (level > 0)
                    {
                        ip++;
                        if (code[ip] == '[')
                        {
                            level++;
                        }
                        else if (code[ip] == ']')
                        {
                            level--;
                        }
                    }
                }
                break;
            case ']':
                // If the data is non-zero, then go to the matching '['.
                // The code has already been tested to be balanced,
                // so this will be guaranteed to terminate nicely.
                if (data[dp] != 0)
                {
                    unsigned int level = 1;
                    while (level > 0)
                    {
                        ip--;
                        if (code[ip] == '[')
                        {
                            level--;
                        }
                        else if (code[ip] == ']')
                        {
                            level++;
                        }
                    }
                }
                break;
            default:
                // All other characters ignored.
                break;
        }
        ip++;
        step++;
    }

    // If we get here, we terminated with no output.
    return false;
}

int compute_score(const std::string& code, size_t steps, std::vector<word>& data)
{
    bool outputs[WORD_SIZE];
    size_t i;
    size_t length = code.length();
    int score = 0;
    std::string mini(code, 1);

    memset(outputs, false, WORD_SIZE);
    for (i = 0; i < length; i++)
    {
        size_t j;
        word result;
        bool success;

        // Construct the string with one character removed.
        for (j = 0; j < length - 1; j++)
        {
            mini[j] = (j >= i) ? code[j + 1] : code[j];
        }

        success = evaluate(mini, steps, &result, data);
        if (success)
        {
            if (!outputs[result])
            {
                score++;
                outputs[result] = true;
            }
        }
    }
    return score;
}

template <class RNG>
void mutate(RNG& rng, std::string& code, double p = 0.002)
{
    // All the possible characters,
    // and a distribution to pick an index thence.
    static const std::string possibilities = "><+-.,[]X";
    static std::uniform_int_distribution<size_t>
        char_choice(0, possibilities.length() - 1);

    size_t length = code.length();
    size_t i;

    // Consider mutating each character (with probability p).
    for (i = 0; i < length; i++)
    {
        double random = std::generate_canonical
            <double, std::numeric_limits<double>::digits>(rng);
        if (random < p)
        {
            size_t index = char_choice(rng);
            code[i] = possibilities[index];
        }
    }
}

template <class RNG>
const std::string* evolve_population(RNG& rng, std::vector<std::string>& population, size_t steps, std::vector<word>& data, size_t nterminal)
{
    size_t i;
    std::uniform_int_distribution<size_t>
        parent_choice(0, nterminal - 1);
    size_t count = population.size();
    const std::string *best = NULL;
    int bestScore = 0;

    // Compute the scores first.
    std::unordered_map<std::string, int> scores;
    for (const std::string& element : population)
    {
        int score = compute_score(element, steps, data);
        if (score >= bestScore)
        {
            bestScore = score;
            best = &element;
        }
        scores[element] = score;
    }

    // Sort the population by score, descending.
    std::sort(population.begin(), population.end(),
        [&scores](const std::string& a, const std::string& b)
        {
            // Check b < a for reverse order.
            return scores[b] < scores[a];
        }
    );

    // We would kill off the unfit ones,
    // but we don't want to deallocate them.
    // Instead, just overwrite them.
    for (i = count - nterminal; i < count; i++)
    {
        // Pick parents.
        const std::string& parent1 = population[parent_choice(rng)];
        const std::string& parent2 = population[parent_choice(rng)];

        // Bias toward the fitter parent.
        double f1 = scores[parent1] + 1;
        double f2 = scores[parent2] + 1;
        double p = f1 / (f1 + f2);
        std::bernoulli_distribution choice(p);

        // Mix and match the characters ("chromosomes").
        std::string& child = population[i];
        size_t j;
        for (j = 0; j < child.length(); j++)
        {
            child[j] = (choice(rng) ? parent1 : parent2)[j];
        }

        // Finally, mutate the child.
        mutate(rng, child);
    }

    return best;
}

template <class RNG>
void go(RNG& rng, const std::string& base, size_t steps, std::vector<word>& data, size_t npopulation, size_t nterminal)
{
    std::vector<std::string> population;
    size_t i;
    for (i = 0; i < npopulation; i++)
    {
        std::string str(base);
        if (i > npopulation / 2) // mutate the second half only
        {
            mutate(rng, str, 0.1);
        }
        population.push_back(str);
    }

    while (1)
    {
        const std::string *best = evolve_population(rng, population, steps, data, nterminal);
        printf("Best: %s (%d)\n", best->c_str(), compute_score(*best, steps, data));
    }
}

int main()
{
    char *code = new char[MAX_CODE_LENGTH + 1];
    std::vector<word> data;
    //word result;
    //bool success;
    const size_t steps = 100000;

    std::random_device rd;
    std::mt19937 rng(rd());

    memset(code, 0, MAX_CODE_LENGTH + 1);
    scanf("%100[^\n]", code);
    printf("%s\n", code);


    printf("Score: %d.\n", compute_score(std::string(code), steps, data));

    go(rng, std::string(code), steps, data, 100, 15);

    delete code;

    return 0;
}