SHARE
TWEET

garect.cpp

a guest Jan 25th, 2016 470 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <stdexcept>
  6.  
  7. #include <random>
  8.  
  9. std::random_device rd;
  10. std::mt19937 gen(rd());
  11. std::uniform_int_distribution<> tetra(0, 3);
  12. std::uniform_real_distribution<> unit(0, 1);
  13.  
  14. struct RGB
  15. {
  16.     int r;
  17.     int g;
  18.     int b;
  19.  
  20.     RGB(int rr = 0, int gg = 0, int bb = 0) : r(rr), g(gg), b(bb) {}
  21.  
  22.     RGB &operator+=(const RGB &right)
  23.     {
  24.         r += right.r;
  25.         g += right.g;
  26.         b += right.b;
  27.         return *this;
  28.     }
  29.  
  30.     RGB operator+(const RGB &right)
  31.     {
  32.         RGB copy(*this);
  33.         return (copy += right);
  34.     }
  35.  
  36.     RGB &operator-=(const RGB &right)
  37.     {
  38.         r -= right.r;
  39.         g -= right.g;
  40.         b -= right.b;
  41.         return *this;
  42.     }
  43.  
  44.     RGB operator-(const RGB &right)
  45.     {
  46.         RGB copy(*this);
  47.         return (copy -= right);
  48.     }
  49.  
  50.     RGB &operator/=(double scalar)
  51.     {
  52.         r /= scalar;
  53.         g /= scalar;
  54.         b /= scalar;
  55.         return *this;
  56.     }
  57. };
  58.  
  59. std::istream &operator>>(std::istream &is, RGB &rgb)
  60. {
  61.     is >> rgb.r >> rgb.g >> rgb.b;
  62.     return is;
  63. }
  64.  
  65. std::ostream &operator<<(std::ostream &os, const RGB &rgb)
  66. {
  67.     // os << rgb.r << ' ' << rgb.g << ' ' << rgb.b;
  68.     os << "C{" << rgb.r << ',' << rgb.g << ',' << rgb.b << '}';
  69.     return os;
  70. }
  71.  
  72. struct Rectangle
  73. {
  74.     int x;
  75.     int y;
  76.     int w;
  77.     int h;
  78.  
  79.     RGB color;
  80.  
  81.     bool Validate(int min_x, int max_x, int min_y, int max_y)
  82.     {
  83.         if ((x >= min_x) &&
  84.             ((x + w) <= max_x) &&
  85.             (y >= min_y) &&
  86.             ((y + h)<= max_y)
  87.             ) {
  88.             return true;
  89.         }
  90.         return false;
  91.     }
  92. };
  93.  
  94. std::ostream &operator<<(std::ostream &os, const Rectangle &r)
  95. {
  96.     os << "{" << r.x << ',' << r.y << ',' << r.w << ',' << r.h << ',' << r.color << '}';
  97.     return os;
  98. }
  99.  
  100. struct Gene
  101. {
  102.     Rectangle rect;
  103.     int min_x;
  104.     int max_x;
  105.     int min_y;
  106.     int max_y;
  107.  
  108.     void Mutate()
  109.     {
  110.         int p = tetra(gen);
  111.         if (p == 0) {
  112.             if ((max_x - rect.w) <= 0) {
  113.                 return;
  114.             }
  115.             std::uniform_int_distribution<> dis(0, max_x - rect.w);
  116.             rect.x = dis(gen);
  117.         } else if (p == 1) {
  118.             if ((max_y - rect.h) <= 0) {
  119.                 return;
  120.             }
  121.             std::uniform_int_distribution<> dis(0, max_y - rect.h);
  122.             rect.y = dis(gen);
  123.         } else if (p == 2) {
  124.             if ((max_x - rect.x) <= 0) {
  125.                 return;
  126.             }
  127.             std::uniform_int_distribution<> dis(0, max_x - rect.x);
  128.             rect.w = dis(gen);
  129.         } else if (p == 3) {
  130.             if ((max_y - rect.y) <= 0) {
  131.                 return;
  132.             }
  133.             std::uniform_int_distribution<> dis(0, max_y - rect.y);
  134.             rect.h = dis(gen);
  135.         }
  136.         return;
  137.     }
  138. };
  139.  
  140. struct Individual
  141. {
  142.     std::vector<Gene> genes;
  143.     static constexpr double mutate_probability = 0.03;
  144.     // double crossover_probability;
  145.     static constexpr double insertion_probability = 0.01;
  146.     static constexpr std::size_t maximum_genome_size = 10;
  147.  
  148.     bool immutable = false;
  149.  
  150.     static constexpr int min_x = 0;
  151.     int max_x;
  152.     static constexpr int min_y = 0;
  153.     int max_y;
  154.  
  155.     Gene background;
  156.  
  157.     void Step()
  158.     {
  159.         if (immutable) {
  160.             return;
  161.         }
  162.  
  163.         for (std::size_t i = 0; i < genes.size(); i++) {
  164.             auto &gene = genes[i];
  165.             double p = unit(gen);
  166.             if (p < mutate_probability) {
  167.                 gene.Mutate();
  168.             /*
  169.             } else if (p < (mutate_probability + crossover_probability)) {
  170.             } else if (p < (mutate_probability + crossover_probability + insertion_probability)) {
  171.             */
  172.             } else if (p < (mutate_probability + insertion_probability)) {
  173.                 if (genes.size() < maximum_genome_size) {
  174.                     Gene g;
  175.                     Rectangle rect{0, 0, 0, 0, RGB{0, 0, 0}};
  176.                     {
  177.                         std::uniform_int_distribution<> dis(0, max_x - rect.w);
  178.                         rect.x = dis(gen);
  179.                     }
  180.                     {
  181.                         std::uniform_int_distribution<> dis(0, max_y - rect.h);
  182.                         rect.y = dis(gen);
  183.                     }
  184.                     {
  185.                         std::uniform_int_distribution<> dis(0, max_x - rect.x);
  186.                         rect.w = dis(gen);
  187.                     }
  188.                     {
  189.                         std::uniform_int_distribution<> dis(0, max_y - rect.y);
  190.                         rect.h = dis(gen);
  191.                     }
  192.                     g.rect = rect;
  193.                     g.min_x = min_x;
  194.                     g.max_x = max_x;
  195.                     g.min_y = min_y;
  196.                     g.max_y = max_y;
  197.                    
  198.                     genes.insert(genes.begin() + i, g);
  199.                 }
  200.             }
  201.         }
  202.  
  203.         if (genes.size() == 0) {
  204.             Gene g;
  205.             g.rect = {0, 0, max_x+1, max_y+1, RGB{0, 0, 0}};
  206.             g.min_x = min_x;
  207.             g.max_x = max_x;
  208.             g.min_y = min_y;
  209.             g.max_y = max_y;
  210.            
  211.             genes.insert(genes.begin(), g);
  212.         }
  213.         return;
  214.     }
  215. };
  216.  
  217. std::ostream &operator<<(std::ostream &os, const Individual &individual)
  218. {
  219.     os << individual.background.rect;
  220.     for (std::size_t i = 0; i < individual.genes.size(); i++) {
  221.         os << '\n' << individual.genes[i].rect;
  222.     }
  223.     return os;
  224. }
  225.  
  226. class PPM
  227. {
  228.     public:
  229.         PPM(int w = 1, int h = 1) : w_(w), h_(h), pixels_(w_*h_) {}
  230.         friend std::istream &operator>>(std::istream &is, PPM &p);
  231.  
  232.         RGB &operator()(int x, int y)
  233.         {
  234.             if ((x < 0 || x >= w_) || (y < 0 || y >= h_)) {
  235.                 throw std::runtime_error("bounds error in ppm access.");
  236.             }
  237.             return pixels_[w_ * y + x];
  238.         }
  239.         RGB operator()(int x, int y) const
  240.         {
  241.             if ((x < 0 || x >= w_) || (y < 0 || y >= h_)) {
  242.                 throw std::runtime_error("bounds error in ppm access.");
  243.             }
  244.             return pixels_[w_ * y + x];
  245.         }
  246.  
  247.         int w() const { return w_; }
  248.         int h() const { return h_; }
  249.  
  250.     private:
  251.         int w_;
  252.         int h_;
  253.         std::vector<RGB> pixels_;
  254. };
  255.  
  256. std::istream &operator>>(std::istream &is, PPM &p)
  257. {
  258.     std::string header;
  259.     is >> header;
  260.     is >> p.w_ >> p.h_;
  261.     p.pixels_.resize(p.w_ * p.h_);
  262.     int depth;
  263.     is >> depth;
  264.     for (int y = 0; y < p.h_; y++) {
  265.         for (int x = 0; x < p.w_; x++) {
  266.             RGB c;
  267.             is >> c;
  268.             p(x, y) = c;
  269.         }
  270.     }
  271.     return is;
  272. }
  273.  
  274. struct Population
  275. {
  276.     std::vector<Individual> individuals;
  277.     PPM target;
  278.     Individual best;
  279.  
  280.     double ObjectiveFunction(Individual &individual)
  281.     {
  282.         std::vector<int> which_display(target.w() * target.h(), -1);
  283.         std::vector<RGB> rectangle_colors(individual.genes.size());
  284.         std::vector<int> rectangle_counts(individual.genes.size());
  285.  
  286.         for (size_t i = 0; i < individual.genes.size(); i++) {
  287.             auto rect = individual.genes[i].rect;
  288.             for (size_t dy = 0; dy < rect.h; dy++) {
  289.                 for (size_t dx = 0; dx < rect.w; dx++) {
  290.                     which_display[(rect.y + dy) * target.w() + (rect.x + dx)] = i;
  291.                 }
  292.             }
  293.         }
  294.  
  295.         RGB bgcolor;
  296.         int bgcount = 0;
  297.  
  298.         for (size_t y = 0; y < target.h(); y++) {
  299.             for (size_t x = 0; x < target.w(); x++) {
  300.                 int id = which_display[y * target.w() + x];
  301.                 // std::cout << id << ' ' << rectangle_colors.size() << '\n';
  302.                 if (id >= 0) {
  303.                     rectangle_colors[id] += target(x, y);
  304.                     rectangle_counts[id]++;
  305.                 } else if (id == -1) {
  306.                     bgcolor += target(x, y);
  307.                     bgcount++;
  308.                 }
  309.             }
  310.         }
  311.  
  312.         if (bgcount > 0) {
  313.             bgcolor /= bgcount;
  314.         }
  315.         // std::cout << bgcount << ": " << bgcolor << '\n';
  316.         individual.background.rect = {0, 0, target.w(), target.h(), bgcolor};
  317.  
  318.         for (size_t i = 0; i < individual.genes.size(); i++) {
  319.             auto count = rectangle_counts[i];
  320.             if (count > 0) {
  321.                 rectangle_colors[i] /= static_cast<double>(count);
  322.                 individual.genes[i].rect.color = rectangle_colors[i];
  323.             } else {
  324.                 individual.genes[i].rect.color = {0, 0, 0};
  325.             }
  326.         }
  327.  
  328.         PPM p(target.w(), target.h());
  329.        
  330.         /*
  331.         for (size_t dy = 0; dy < p.h(); dy++) {
  332.             for (size_t dx = 0; dx < p.w(); dx++) {
  333.                 p((0 + dx), (0 + dy)) = bgcolor;
  334.             }
  335.         }
  336.         */
  337.         {
  338.             auto rect = individual.background.rect;
  339.             for (size_t dy = 0; dy < rect.h; dy++) {
  340.                 for (size_t dx = 0; dx < rect.w; dx++) {
  341.                     p((rect.x + dx), (rect.y + dy)) = rect.color;
  342.                 }
  343.             }
  344.         }
  345.         for (size_t i = 0; i < individual.genes.size(); i++) {
  346.             auto rect = individual.genes[i].rect;
  347.             for (size_t dy = 0; dy < rect.h; dy++) {
  348.                 for (size_t dx = 0; dx < rect.w; dx++) {
  349.                     p((rect.x + dx), (rect.y + dy)) = rect.color;
  350.                 }
  351.             }
  352.         }
  353.  
  354.         double score = 0;
  355.         for (size_t y = 0; y < target.h(); y++) {
  356.             for (size_t x = 0; x < target.w(); x++) {
  357.                 auto diff = target(x, y) - p(x, y);
  358.                 score += diff.r*diff.r;
  359.                 score += diff.g*diff.g;
  360.                 score += diff.b*diff.b;
  361.             }
  362.         }
  363.         score /= (255.0 * 255.0);
  364.         // std::cout << score << '\n';
  365.         return score;
  366.     }
  367.    
  368.     void Step()
  369.     {
  370.         for (std::size_t i = 0; i < individuals.size(); i++) {
  371.             auto &individual = individuals[i];
  372.             individual.Step();
  373.         }
  374.  
  375.         std::vector<double> scores(individuals.size());
  376.         std::transform(individuals.begin(), individuals.end(), scores.begin(), [&](Individual &x) { return ObjectiveFunction(x); } );
  377.         size_t min_i = 0;
  378.         double min_score = scores[min_i];
  379.         for (size_t i = 0; i < individuals.size(); i++) {
  380.             if (scores[i] < min_score) {
  381.                 min_i = i;
  382.                 min_score = scores[min_i];
  383.             }
  384.         }
  385.  
  386.         std::vector<double> probabilities(individuals.size());
  387.         std::transform(scores.begin(), scores.end(), probabilities.begin(), [&](double x) { if (x != 0) { return 1.0 / x; }  return 1.0; });
  388.         double sum = 0;
  389.         for (auto p : probabilities) {
  390.             sum += p;
  391.         }
  392.         for (auto &p : probabilities) {
  393.             p /= sum;
  394.         }
  395.         for (std::size_t i = 1; i < probabilities.size(); i++) {
  396.             probabilities[i] += probabilities[i-1];
  397.         }
  398.  
  399.         best = individuals[min_i];
  400.         std::cout << min_score << '\n' << individuals[min_i] << "\n\n";
  401.  
  402.         std::vector<Individual> next_round;
  403.         next_round.push_back(best);
  404.         next_round.push_back(best);
  405.         while(next_round.size() < individuals.size()) {
  406.             double pick = unit(gen);
  407.             std::size_t idx = 0;
  408.             if (pick >= probabilities[probabilities.size()-1]) {
  409.                 idx = probabilities.size() - 1;
  410.             } else if (pick <= probabilities[0]) {
  411.                 idx = 0;
  412.             } else {
  413.                 for (std::size_t i = 1; i < probabilities.size(); i++) {
  414.                     if ((pick <= probabilities[i]) && (pick > probabilities[i-1])) {
  415.                         idx = i-1;
  416.                         break;
  417.                     }
  418.                 }
  419.             }
  420.             next_round.push_back(individuals[idx]);
  421.         }
  422.  
  423.         for (auto &i : next_round) {
  424.             i.immutable = false;
  425.         }
  426.         next_round[0].immutable = true;
  427.         individuals = next_round;
  428.  
  429.         return;
  430.     }
  431. };
  432.  
  433. int main()
  434. {
  435.     std::ifstream ifs("ORIGINAL.ppm");
  436.     PPM p(1, 1);
  437.     ifs >> p;
  438.  
  439.     /*
  440.     std::cout << "P3\n" << p.w() << ' ' << p.h() << "\n255\n";
  441.     for (int y = 0; y < p.h(); y++) {
  442.         for (int x = 0; x < p.w(); x++) {
  443.             std::cout << p(x, y) << '\n';
  444.         }
  445.     }
  446.     */
  447.  
  448.     Population pop;
  449.     Individual indiv;
  450.     indiv.max_x = p.w() - 1;
  451.     indiv.max_y = p.h() - 1;
  452.     size_t population_size = 20;
  453.     for (std::size_t i = 0; i < population_size; i++) {
  454.         pop.individuals.push_back(indiv);
  455.     }
  456.     pop.target = PPM(p);
  457.     for (int i = 0; i < 1e4; i++) {
  458.         pop.Step();
  459.     }
  460.  
  461.     return 0;
  462. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top