//

// The "game of life", cellular automaton as John Horton Conway thought it.

//

// Programming challenge 17.

// http://cplus.about.com/od/programmingchallenges/a/challenge17.htm

//

//

//

// Straight forward solution using C++ with no profiling or any other

// optimization work.

//

// Peter Jansson   http://peter.jansson.net

//

// 2008-09-09

//

//

//-----------------------------------------------------------------------------

// Timing code declaration.

#include <windows.h>

typedef struct {

   LARGE_INTEGER start;

   LARGE_INTEGER stop;

} stopWatch;

class CStopWatch {

   private:

      stopWatch timer;

      LARGE_INTEGER frequency;

      double LIToSecs( LARGE_INTEGER & L);

   public:

      CStopWatch();

      void startTimer( );

      void stopTimer( );

      double getElapsedTime();

};

//-----------------------------------------------------------------------------



// A point on the grid of life.

class point

{

   private:

      // The point is 2D on a grid.

      unsigned int x,y;

   public:

      // Constructor.

      point(const unsigned int& x=0,const unsigned int& y=0):x(x),y(y) {};

      // Sorting order between points.

      const bool operator<(const point& p) const

      {

         return (x<p.x || (x==p.x && y<p.y));

      };

      // Get the 8 neighbours around this point.

      // Numbered according to:

      //   0    1     2

      //   7   this   3

      //   6    5     4

      inline void GetNeighbours(point neighbours[8]) const

      {

         neighbours[0].x = (x>0?x-1:999);

         neighbours[0].y = (y>0?y-1:999);

         neighbours[1].x = x;

         neighbours[1].y = neighbours[0].y;

         neighbours[2].x = (x<999?x+1:0);

         neighbours[2].y = neighbours[0].y;

         neighbours[3].x = neighbours[2].x;

         neighbours[3].y = y;

         neighbours[4].x = neighbours[2].x;

         neighbours[4].y = (y<999?y+1:0);

         neighbours[5].x = x;

         neighbours[5].y = neighbours[4].y;

         neighbours[6].x = neighbours[0].x;

         neighbours[6].y = neighbours[4].y;

         neighbours[7].x = neighbours[0].x;

         neighbours[7].y = y;

      };

};



//-----------------------------------------------------------------------------



#include <fstream>

#include <set>



int main()

{



   // The code was faster than 1 second on my machine so we loop the whole

   // process a few times and calculate the average time for 1000

   // generation per loop.

   const unsigned int num_of_runs(7);

   double sum_of_elapsed_times(0.0);

   for( unsigned int run_count(num_of_runs);

         run_count > 0;

         run_count-- )

   {





      // The collection of set points, where life live.

      std::set<point> life;







      // Set the initial F-Pentomino pattern.

      life.insert( point(499,500) );

      life.insert( point(500,499) );

      life.insert( point(500,500) );

      life.insert( point(500,501) );

      life.insert( point(501,499) );









      // Let's live for 1000 generations.

      std::set<point>::const_iterator i,e;

      point neighbours[8], near_neighbours[8];

      unsigned int num_of_set_neighbours,num_of_set_near_neighbours;

      int n,m;



      CStopWatch s;

      s.startTimer();

      

      for( int generation(0); generation<1000; ++generation )

      {

         // The next generation of life.

         std::set<point> next_life;



         // Count the number of set neighbours to each set point.

         // Count also the number of set points besides each

         // clear point. The clear point gets set if it has exactly 3

         // set neighbours so it must have at least one, i.e. it is

         // enough to look at the clear points around each set point.

         for( i=life.begin(),e=life.end(); i != e; ++i )

         {

            num_of_set_neighbours = 0;

            i->GetNeighbours( neighbours );

            for( n=0; n<8; ++n )

            {

               if( e != life.find( neighbours[n] ) ) // neighbour is set

               {

                  num_of_set_neighbours++;

               }

               else

                  // neighbour is clear, count set points around this neighbour

               {

                  neighbours[n].GetNeighbours(near_neighbours);

                  num_of_set_near_neighbours = 0;

                  for( m=0; m<8 && num_of_set_near_neighbours<4; ++m )

                  {

                     if( e != life.find( near_neighbours[m] ) )

                        // near neighbour is set

                     {

                        num_of_set_near_neighbours++;

                     }

                  }

                  if( num_of_set_near_neighbours == 3 )

                  {

                     // this neighbour is brough to life.

                     next_life.insert( neighbours[n] );

                  }

               }

            }

            // Will this set point survive?

            if( num_of_set_neighbours>1 && num_of_set_neighbours<4 )

            {

               next_life.insert( *i );

            }

         }



         // Life evolves to the next generation.

         life.swap( next_life );

      }

      

      s.stopTimer();

      sum_of_elapsed_times += s.getElapsedTime();





      // Write the results on the last iteration.

      if( run_count == 1 )

      {

         // Write the result.

         std::ofstream f("life.txt");

         e = life.end();

         for( unsigned int y=0; y<1000; ++y )

         {

            for( unsigned int x=0; x<1000; ++x )

            {

               // Output '1' if point is set, '0' otherwise.

               f << ( e == life.find(point(x,y)) ? 0 : 1 );

            }

            f << '\n';

         }

         f << "Average time for 1000 generations in "

            << num_of_runs << " runs: "

            << sum_of_elapsed_times/num_of_runs

            << " seconds per run\n";

         f.close();

      }

   }

}

//-----------------------------------------------------------------------------

// Timing code implementation.

double CStopWatch::LIToSecs( LARGE_INTEGER & L) {

   return ((double)L.QuadPart /(double)frequency.QuadPart);

}

CStopWatch::CStopWatch(){

   timer.start.QuadPart=0;

   timer.stop.QuadPart=0;	

   QueryPerformanceFrequency( &frequency );

}

void CStopWatch::startTimer( ) {

   QueryPerformanceCounter(&timer.start);

}

void CStopWatch::stopTimer( ) {

   QueryPerformanceCounter(&timer.stop);

}

double CStopWatch::getElapsedTime() {

   LARGE_INTEGER time;

   time.QuadPart = timer.stop.QuadPart - timer.start.QuadPart;

   return LIToSecs( time) ;

}