Infinite game of life

main.cpp

#include <set>
#include <climits>
#include <cstdio>
#include <chrono>
#include <functional>

#define RANGE_TEST

typedef std::pair<int,int> position;
typedef std::set<position> arena;

void show(arena& a) {
  if(a.empty()) {
    printf("all dead...\n");
    return;
  }
  int minX = INT_MAX;
  int minY = INT_MAX;
  int maxX = INT_MIN;
  int maxY = INT_MIN;
  for(auto cell : a) {
    if(cell.first < minX) minX = cell.first;
    if(cell.first > maxX) maxX = cell.first;
    if(cell.second < minY) minY = cell.second;
    if(cell.second > maxY) maxY = cell.second;
  }
  printf("%d cells alive in (%d,%d) to (%d,%d):\n",a.size(),minX,minY,maxX,maxY);
  for(int y = minY; y<=maxY; y++) {
    for(int x = minX; x<=maxX; x++) {
      putchar(a.count(std::make_pair(x,y)) ? '@' : ' ' );
    }
    putchar('\n');
  }
}


struct { int x,y; } neighbours[] = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
#define ARRAY_SIZE(x) (sizeof(x)/sizeof(x[0]))

void forNeighbours(const arena& a, position cell, std::function<void(std::pair<int,int>)> cb) {
  int x = cell.first;
  int y = cell.second;
  for(int i = 0; i < ARRAY_SIZE(neighbours); i++) {
    cb(std::make_pair(x+neighbours[i].x,y+neighbours[i].y));
  }
}

int countNeighbours(const arena& a, position cell) {
  int c = 0;
  forNeighbours(a,cell,[&](position pos) {
    c += a.count(pos);
  });
  return c;
}

arena gameOfLive(const arena& a) {
  arena potentiallyAffectedFields;
  for(auto cell : a) {
    potentiallyAffectedFields.insert(cell);
    forNeighbours(a, cell, [&](position pos) {
      potentiallyAffectedFields.insert(pos);
    });
  }
  arena next;
  for(auto cell : potentiallyAffectedFields) {
    int neighbours = countNeighbours(a, cell);
    int alive = a.count(cell);
    if(alive) {
      switch(neighbours) {
        case 2:
        case 3:
          next.insert(cell);
      }
    } else {
      if(neighbours == 3) next.insert(cell);
    }
  }
  return next;
}

int main(int argc, char** argv) {
  arena a;
  a.insert(std::make_pair(0,0));
  a.insert(std::make_pair(0,1));
  a.insert(std::make_pair(0,2));
  a.insert(std::make_pair(1,0));
  a.insert(std::make_pair(2,1));

  printf("INITIAL ARENA:");
  show(a);

  int iteration = 0;
  for(; iteration<4; iteration++) {
    a = gameOfLive(a);
    printf("AFTER %d ITERATIONS:\n",iteration+1);
    show(a);
  }

  for(; iteration<1000; iteration++) {
    a = gameOfLive(a);
  }
  printf("AFTER %d ITERATIONS:\n",iteration+1);
  show(a);
  auto start = std::chrono::system_clock::now();
  for(; iteration<10000; iteration++) {
    a = gameOfLive(a);
  }
  auto end = std::chrono::system_clock::now();
  printf("AFTER %d ITERATIONS:\n",iteration+1);
  show(a);

  std::chrono::duration<double> elapsed_seconds = end-start;
  double millis = elapsed_seconds.count()*1000;
  printf("10000 Iterations in %lf milliseconds - %lf milliseconds per iteration\n",millis,millis/10000);
}