garect.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stdexcept>

#include <random>

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> tetra(0, 3);
std::uniform_real_distribution<> unit(0, 1);

struct RGB
{
    int r;
    int g;
    int b;

    RGB(int rr = 0, int gg = 0, int bb = 0) : r(rr), g(gg), b(bb) {}

    RGB &operator+=(const RGB &right)
    {
        r += right.r;
        g += right.g;
        b += right.b;
        return *this;
    }

    RGB operator+(const RGB &right)
    {
        RGB copy(*this);
        return (copy += right);
    }

    RGB &operator-=(const RGB &right)
    {
        r -= right.r;
        g -= right.g;
        b -= right.b;
        return *this;
    }

    RGB operator-(const RGB &right)
    {
        RGB copy(*this);
        return (copy -= right);
    }

    RGB &operator/=(double scalar)
    {
        r /= scalar;
        g /= scalar;
        b /= scalar;
        return *this;
    }
};

std::istream &operator>>(std::istream &is, RGB &rgb)
{
    is >> rgb.r >> rgb.g >> rgb.b;
    return is;
}

std::ostream &operator<<(std::ostream &os, const RGB &rgb)
{
    // os << rgb.r << ' ' << rgb.g << ' ' << rgb.b;
    os << "C{" << rgb.r << ',' << rgb.g << ',' << rgb.b << '}';
    return os;
}

struct Rectangle
{
    int x;
    int y;
    int w;
    int h;

    RGB color;

    bool Validate(int min_x, int max_x, int min_y, int max_y)
    {
        if ((x >= min_x) &&
            ((x + w) <= max_x) &&
            (y >= min_y) &&
            ((y + h)<= max_y)
            ) {
            return true;
        }
        return false;
    }
};

std::ostream &operator<<(std::ostream &os, const Rectangle &r)
{
    os << "{" << r.x << ',' << r.y << ',' << r.w << ',' << r.h << ',' << r.color << '}';
    return os;
}

struct Gene
{
    Rectangle rect;
    int min_x;
    int max_x;
    int min_y;
    int max_y;

    void Mutate()
    {
        int p = tetra(gen);
        if (p == 0) {
            if ((max_x - rect.w) <= 0) {
                return;
            }
            std::uniform_int_distribution<> dis(0, max_x - rect.w);
            rect.x = dis(gen);
        } else if (p == 1) {
            if ((max_y - rect.h) <= 0) {
                return;
            }
            std::uniform_int_distribution<> dis(0, max_y - rect.h);
            rect.y = dis(gen);
        } else if (p == 2) {
            if ((max_x - rect.x) <= 0) {
                return;
            }
            std::uniform_int_distribution<> dis(0, max_x - rect.x);
            rect.w = dis(gen);
        } else if (p == 3) {
            if ((max_y - rect.y) <= 0) {
                return;
            }
            std::uniform_int_distribution<> dis(0, max_y - rect.y);
            rect.h = dis(gen);
        }
        return;
    }
};

struct Individual
{
    std::vector<Gene> genes;
    static constexpr double mutate_probability = 0.03;
    // double crossover_probability;
    static constexpr double insertion_probability = 0.01;
    static constexpr std::size_t maximum_genome_size = 10;

    bool immutable = false;

    static constexpr int min_x = 0;
    int max_x;
    static constexpr int min_y = 0;
    int max_y;

    Gene background;

    void Step()
    {
        if (immutable) {
            return;
        }

        for (std::size_t i = 0; i < genes.size(); i++) {
            auto &gene = genes[i];
            double p = unit(gen);
            if (p < mutate_probability) {
                gene.Mutate();
            /*
            } else if (p < (mutate_probability + crossover_probability)) {
            } else if (p < (mutate_probability + crossover_probability + insertion_probability)) {
            */
            } else if (p < (mutate_probability + insertion_probability)) {
                if (genes.size() < maximum_genome_size) {
                    Gene g;
                    Rectangle rect{0, 0, 0, 0, RGB{0, 0, 0}};
                    {
                        std::uniform_int_distribution<> dis(0, max_x - rect.w);
                        rect.x = dis(gen);
                    }
                    {
                        std::uniform_int_distribution<> dis(0, max_y - rect.h);
                        rect.y = dis(gen);
                    }
                    {
                        std::uniform_int_distribution<> dis(0, max_x - rect.x);
                        rect.w = dis(gen);
                    }
                    {
                        std::uniform_int_distribution<> dis(0, max_y - rect.y);
                        rect.h = dis(gen);
                    }
                    g.rect = rect;
                    g.min_x = min_x;
                    g.max_x = max_x;
                    g.min_y = min_y;
                    g.max_y = max_y;

                    genes.insert(genes.begin() + i, g);
                }
            }
        }

        if (genes.size() == 0) {
            Gene g;
            g.rect = {0, 0, max_x+1, max_y+1, RGB{0, 0, 0}};
            g.min_x = min_x;
            g.max_x = max_x;
            g.min_y = min_y;
            g.max_y = max_y;

            genes.insert(genes.begin(), g);
        }
        return;
    }
};

std::ostream &operator<<(std::ostream &os, const Individual &individual)
{
    os << individual.background.rect;
    for (std::size_t i = 0; i < individual.genes.size(); i++) {
        os << '\n' << individual.genes[i].rect;
    }
    return os;
}

class PPM
{
    public:
        PPM(int w = 1, int h = 1) : w_(w), h_(h), pixels_(w_*h_) {}
        friend std::istream &operator>>(std::istream &is, PPM &p);

        RGB &operator()(int x, int y)
        {
            if ((x < 0 || x >= w_) || (y < 0 || y >= h_)) {
                throw std::runtime_error("bounds error in ppm access.");
            }
            return pixels_[w_ * y + x];
        }
        RGB operator()(int x, int y) const
        {
            if ((x < 0 || x >= w_) || (y < 0 || y >= h_)) {
                throw std::runtime_error("bounds error in ppm access.");
            }
            return pixels_[w_ * y + x];
        }

        int w() const { return w_; }
        int h() const { return h_; }

    private:
        int w_;
        int h_;
        std::vector<RGB> pixels_;
};

std::istream &operator>>(std::istream &is, PPM &p)
{
    std::string header;
    is >> header;
    is >> p.w_ >> p.h_;
    p.pixels_.resize(p.w_ * p.h_);
    int depth;
    is >> depth;
    for (int y = 0; y < p.h_; y++) {
        for (int x = 0; x < p.w_; x++) {
            RGB c;
            is >> c;
            p(x, y) = c;
        }
    }
    return is;
}

struct Population
{
    std::vector<Individual> individuals;
    PPM target;
    Individual best;

    double ObjectiveFunction(Individual &individual)
    {
        std::vector<int> which_display(target.w() * target.h(), -1);
        std::vector<RGB> rectangle_colors(individual.genes.size());
        std::vector<int> rectangle_counts(individual.genes.size());

        for (size_t i = 0; i < individual.genes.size(); i++) {
            auto rect = individual.genes[i].rect;
            for (size_t dy = 0; dy < rect.h; dy++) {
                for (size_t dx = 0; dx < rect.w; dx++) {
                    which_display[(rect.y + dy) * target.w() + (rect.x + dx)] = i;
                }
            }
        }

        RGB bgcolor;
        int bgcount = 0;

        for (size_t y = 0; y < target.h(); y++) {
            for (size_t x = 0; x < target.w(); x++) {
                int id = which_display[y * target.w() + x];
                // std::cout << id << ' ' << rectangle_colors.size() << '\n';
                if (id >= 0) {
                    rectangle_colors[id] += target(x, y);
                    rectangle_counts[id]++;
                } else if (id == -1) {
                    bgcolor += target(x, y);
                    bgcount++;
                }
            }
        }

        if (bgcount > 0) {
            bgcolor /= bgcount;
        }
        // std::cout << bgcount << ": " << bgcolor << '\n';
        individual.background.rect = {0, 0, target.w(), target.h(), bgcolor};

        for (size_t i = 0; i < individual.genes.size(); i++) {
            auto count = rectangle_counts[i];
            if (count > 0) {
                rectangle_colors[i] /= static_cast<double>(count);
                individual.genes[i].rect.color = rectangle_colors[i];
            } else {
                individual.genes[i].rect.color = {0, 0, 0};
            }
        }

        PPM p(target.w(), target.h());

        /*
        for (size_t dy = 0; dy < p.h(); dy++) {
            for (size_t dx = 0; dx < p.w(); dx++) {
                p((0 + dx), (0 + dy)) = bgcolor;
            }
        }
        */
        {
            auto rect = individual.background.rect;
            for (size_t dy = 0; dy < rect.h; dy++) {
                for (size_t dx = 0; dx < rect.w; dx++) {
                    p((rect.x + dx), (rect.y + dy)) = rect.color;
                }
            }
        }
        for (size_t i = 0; i < individual.genes.size(); i++) {
            auto rect = individual.genes[i].rect;
            for (size_t dy = 0; dy < rect.h; dy++) {
                for (size_t dx = 0; dx < rect.w; dx++) {
                    p((rect.x + dx), (rect.y + dy)) = rect.color;
                }
            }
        }

        double score = 0;
        for (size_t y = 0; y < target.h(); y++) {
            for (size_t x = 0; x < target.w(); x++) {
                auto diff = target(x, y) - p(x, y);
                score += diff.r*diff.r;
                score += diff.g*diff.g;
                score += diff.b*diff.b;
            }
        }
        score /= (255.0 * 255.0);
        // std::cout << score << '\n';
        return score;
    }

    void Step()
    {
        for (std::size_t i = 0; i < individuals.size(); i++) {
            auto &individual = individuals[i];
            individual.Step();
        }

        std::vector<double> scores(individuals.size());
        std::transform(individuals.begin(), individuals.end(), scores.begin(), [&](Individual &x) { return ObjectiveFunction(x); } );
        size_t min_i = 0;
        double min_score = scores[min_i];
        for (size_t i = 0; i < individuals.size(); i++) {
            if (scores[i] < min_score) {
                min_i = i;
                min_score = scores[min_i];
            }
        }

        std::vector<double> probabilities(individuals.size());
        std::transform(scores.begin(), scores.end(), probabilities.begin(), [&](double x) { if (x != 0) { return 1.0 / x; }  return 1.0; });
        double sum = 0;
        for (auto p : probabilities) {
            sum += p;
        }
        for (auto &p : probabilities) {
            p /= sum;
        }
        for (std::size_t i = 1; i < probabilities.size(); i++) {
            probabilities[i] += probabilities[i-1];
        }

        best = individuals[min_i];
        std::cout << min_score << '\n' << individuals[min_i] << "\n\n";

        std::vector<Individual> next_round;
        next_round.push_back(best);
        next_round.push_back(best);
        while(next_round.size() < individuals.size()) {
            double pick = unit(gen);
            std::size_t idx = 0;
            if (pick >= probabilities[probabilities.size()-1]) {
                idx = probabilities.size() - 1;
            } else if (pick <= probabilities[0]) {
                idx = 0;
            } else {
                for (std::size_t i = 1; i < probabilities.size(); i++) {
                    if ((pick <= probabilities[i]) && (pick > probabilities[i-1])) {
                        idx = i-1;
                        break;
                    }
                }
            }
            next_round.push_back(individuals[idx]);
        }

        for (auto &i : next_round) {
            i.immutable = false;
        }
        next_round[0].immutable = true;
        individuals = next_round;

        return;
    }
};

int main()
{
    std::ifstream ifs("ORIGINAL.ppm");
    PPM p(1, 1);
    ifs >> p;

    /*
    std::cout << "P3\n" << p.w() << ' ' << p.h() << "\n255\n";
    for (int y = 0; y < p.h(); y++) {
        for (int x = 0; x < p.w(); x++) {
            std::cout << p(x, y) << '\n';
        }
    }
    */

    Population pop;
    Individual indiv;
    indiv.max_x = p.w() - 1;
    indiv.max_y = p.h() - 1;
    size_t population_size = 20;
    for (std::size_t i = 0; i < population_size; i++) {
        pop.individuals.push_back(indiv);
    }
    pop.target = PPM(p);
    for (int i = 0; i < 1e4; i++) {
        pop.Step();
    }

    return 0;
}