Advertisement
mister_wardrop

Set Iteration Failure

Apr 24th, 2014
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.72 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<iostream>
  4. #include<list>
  5. #include<set>
  6. #include<vector>
  7. #include<string>
  8. #include<math.h>
  9. #include <algorithm>
  10. using namespace std;
  11.  
  12. class Position {
  13.  
  14. public:
  15.     int x;
  16.     int y;
  17.  
  18.     Position(int x,int y) {
  19.             this->x = x;
  20.             this->y = y;
  21.         }
  22.  
  23.     int distance(Position other) const {
  24.         return this->distance(other.x,other.y);
  25.     }
  26.  
  27.     int distance(int x, int y) const {
  28.         return abs(this->x - x) + abs(this->y - y);
  29.     }
  30.  
  31.     /*bool operator== (Position other) const {
  32.         if (other.x == this->x && other.y == this->y) {
  33.             return true;
  34.         }
  35.         return false;
  36.     }*/
  37.  
  38.     bool operator< (Position other) const {
  39.         return other.x - x + 100*(other.y - y);
  40.     }
  41.  
  42.     /*~Position() {
  43.         cout << "D" << x << y;
  44.     }*/
  45.  
  46.  
  47.  
  48. };
  49.  
  50. class Cluster {
  51.  
  52. public:
  53.     set<Position> c;
  54.     void merge(Cluster other) {
  55.         cout << "\nTO MERGE:\n";
  56.         cout << *this;
  57.         cout << other;
  58.         this->c.insert(other.c.begin(),other.c.end());
  59.         cout << "MERGED: " << this << *this << "\n\n";
  60.     }
  61.  
  62.     void add(Position p) {
  63.         c.insert(p);
  64.     }
  65.  
  66.     int distance(Cluster other) {
  67.         int min = 10000;
  68.         for (set<Position>::iterator pos = c.begin(); pos != c.end(); ++pos) {
  69.             Position p = *pos;
  70.             int distance = other.distance(p);
  71.             if (min == -1 || min > distance) {
  72.                 min = distance;
  73.             }
  74.         }
  75.         return min;
  76.     }
  77.  
  78.     int distance(Position other) {
  79.         return this->distance(other.x,other.y);
  80.     }
  81.  
  82.     int distance(int x, int y) {
  83.         int min = 10000;
  84.         for (set<Position>::iterator pos = c.begin(); pos != c.end(); ++pos) {
  85.             Position p = *pos;
  86.             if (min == -1 || min > p.distance(x,y)) {
  87.                 min = p.distance(x,y);
  88.             }
  89.         }
  90.         return min;
  91.     }
  92.  
  93.     int size() {
  94.         return this->c.size();
  95.     }
  96.  
  97.     operator const char* () const {
  98.         string output = "";
  99.         char* buffer = (char*) calloc (50,sizeof(char));
  100.         sprintf(buffer,"Cluster of size %d: ",(int)this->c.size());
  101.         output = output.append(buffer);
  102.         for (set<Position>::iterator i = this->c.begin(); i!=this->c.end(); ++i) {
  103.             Position pos = *i;
  104.             sprintf(buffer,"[%d,%d], ",pos.x,pos.y);
  105.             output = output.append(buffer);
  106.         }
  107.         output = output.append("\n");
  108.  
  109.         return output.c_str();
  110.     }
  111.  
  112. };
  113.  
  114.  
  115. enum Direction {
  116.         UP,
  117.         DOWN,
  118.         LEFT,
  119.         RIGHT
  120.     };
  121.  
  122. class Move {
  123. public:
  124.     Move(int x, int y, Direction direction) {
  125.         this->x = x;
  126.         this->y = y;
  127.         this->direction = direction;
  128.     }
  129.     int x;
  130.     int y;
  131.     Direction direction;
  132. };
  133.  
  134. typedef vector< vector<int> > Board;
  135.  
  136. vector<Cluster> clusters(Board board, int color, int distance = 1) {
  137.     vector<Cluster> clusters;
  138.     for (int i=0; i < board.size(); i++) {
  139.         for (int j=0; j < board[i].size(); j++) {
  140.             if (board[i][j] == color) {
  141.                 vector<int> tested;
  142.                 for (int k=0; k<clusters.size(); k++) {
  143.                     Cluster cluster = clusters[k];
  144.                     if (cluster.distance(i,j) <= distance) {
  145.                         tested.push_back(k);
  146.                     }
  147.                 }
  148.                 Cluster newCluster;
  149.                 newCluster.add(Position(i,j));
  150.                 if (tested.size() > 0 ) {
  151.                     for (int k=0; k<tested.size(); k++) {
  152.                         int l = tested[k];
  153.                         Cluster m = clusters[l];
  154.                         newCluster.merge(m);
  155.                     }
  156.                     for (int k=tested.size()-1; k>=0; k--) {
  157.                         clusters.erase(clusters.begin()+tested[k]);
  158.                     }
  159.                 }
  160.                 cout << "NEW CLUSTER " << newCluster;
  161.                 clusters.push_back(newCluster);
  162.             }
  163.             list<int> test;
  164.         }
  165.     }
  166.  
  167.     return clusters;
  168. }
  169.  
  170. vector<Cluster> processClusters(vector<Cluster> clusters, int distance=2, int desiredSize = 4) {
  171.     vector<Cluster> desired;
  172.     while (desired.size() == 0) {
  173.         for (int i=0; i<clusters.size(); i++) {
  174.             cout << clusters[i] << &clusters[i];
  175.         }
  176.         vector<Cluster> newClusters;
  177.         for(int i=0; i<clusters.size(); i++) {
  178.             vector<int> local;
  179.             for(int j=0; j<newClusters.size(); j++) {
  180.                 if (clusters[i].distance(newClusters[j])<=distance) {
  181.                     local.push_back(j);
  182.                 }
  183.             }
  184.             if (local.size() > 0) {
  185.                 Cluster newCluster;
  186.                 newCluster.merge(clusters[i]);
  187.                 for (int j=0; j<local.size(); j++) {
  188.                     newCluster.merge(newClusters[local[j]]);
  189.                 }
  190.                 for (int j=local.size()-1; j>=0; j--) {
  191.                     newClusters.erase(newClusters.begin()+j);
  192.                 }
  193.                 newClusters.push_back(newCluster);
  194.             } else {
  195.                 newClusters.push_back(clusters[i]);
  196.             }
  197.         }
  198.         clusters = newClusters;
  199.  
  200.         for(int i=0; i<clusters.size(); i++) {
  201.             //cout << clusters[i].size() << '\n';
  202.             for (int k=0; k<clusters[i].c.size(); k++) {
  203.                 Position pos =  *(clusters[i].c.begin());
  204.                 //cout << k << " " << pos.x << " " << pos.y  << '\n';
  205.             }
  206.             if (clusters[i].size() >= desiredSize) {
  207.                 desired.push_back(clusters[i]);
  208.             }
  209.         }
  210.  
  211.         distance++;
  212.     }
  213.     cout << "DESIRED\n";
  214.     for (int i=0; i<desired.size(); i++) {
  215.         cout << desired[i] << &desired[i];
  216.     }
  217.     return desired;
  218. }
  219.  
  220.  
  221. /* Function declarations */
  222.  
  223. long getNextColour(int colours);
  224. Move generate_move(int colors, Board board);
  225. int* playIt(int colours, Board board, long startSeed);
  226.  
  227.  
  228. long current_seed;
  229.  
  230. int main() {
  231.  
  232.     /*
  233.  
  234.         Read integer colors.
  235.         Read integer N.
  236.         Read N strings board[0], board[1], ..., board[N-1].
  237.         Read integer startSeed.
  238.         Call playIt(colors, board, startSeed). Let ret be the return value.
  239.         Print integers ret[0], ret[1], ..., ret[29999]. Flush standard output stream.
  240.  
  241.     */
  242.    
  243.     /*list<int> test;
  244.     test.push_back(0);
  245.     list<int>::iterator i;
  246.     for(i=test.begin(); i != test.end(); ++i) cout << *i << " ";
  247.     cout << endl;
  248.     */
  249.    
  250.     int colors,N;
  251.     long startSeed;
  252.     Board board;
  253.    
  254.     if (false) {
  255.         //cout << "Number of colours: ";
  256.         cin >> colors;
  257.         //cout << "Length of board-side: ";
  258.         cin >> N;
  259.         board.resize(N);
  260.         for(int i=0; i < N; i++) {
  261.             board[i].resize(N);
  262.             for (int j=0; j<N; j++) {
  263.                 scanf("%1d",&board[i][j]);
  264.             }
  265.         }
  266.  
  267.         cin >> startSeed;
  268.     } else {
  269.         colors = 2;
  270.         N = 3;
  271.         board.resize(N);
  272.         for(int i=0; i < N; i++) {
  273.             board[i].resize(N);
  274.         }
  275.         board[0][0] = 0;
  276.         board[0][1] = 1;
  277.         board[0][2] = 1;
  278.         board[1][0] = 0;
  279.         board[1][1] = 1;
  280.         board[1][2] = 0;
  281.         board[2][0] = 0;
  282.         board[2][1] = 0;
  283.         board[2][2] = 1;
  284.  
  285.         startSeed = 1;
  286.     }
  287.  
  288.     flush(cout);
  289.     int *ret = playIt(colors, board, startSeed);
  290.    
  291.     for (int i=0; i<3; i++) {
  292.         cout << ret[i] << '\n';
  293.     }
  294. }
  295.  
  296. long getNextColour(int colours) {
  297.     long last_seed = current_seed;
  298.     current_seed = (current_seed * 48271) % 2147483647;
  299.     return last_seed % colours;
  300. }
  301.  
  302. Move generate_move(int colors, Board board) {
  303.     vector<Cluster> cs = clusters(board,1);
  304.     Position p = *cs[0].c.begin();
  305.     return Move(p.x,p.y,UP);
  306. }
  307.  
  308. int* playIt(int colors, Board board, long startSeed) {
  309.  
  310.     int *moves = (int*) calloc (3,sizeof(int));
  311.  
  312.     // Setup
  313.     current_seed = startSeed;
  314.  
  315.     for (int i = 0; i<1; i=i+3) {
  316.         Move move = generate_move(colors, board);
  317.         moves[i]= move.x;
  318.         moves[i+1] = move.y;
  319.         moves[i+2] = move.direction;
  320.     }
  321.  
  322.     return moves;
  323. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement