#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
struct params_t{
int world_size; // size of the world (side of the square world)
double initial_proportion; // initial proportion of living cells
int max_t; // maximum time for simulation
int delay; // period in terms of the number of time steps before
// each display of the world (to make more efficient
// outputs)
int num_runs; // number of runs to execute
int display; // turn on the display-world feature (yes=1, no=0)
};
struct stats_t {
int num_steps; // the number of time steps
vector<int> num_living; // the number of living cells (at a time)
vector<int> num_dead; // the number of dead cells (at a time)
vector<int> num_changed; // the number of changed cells (at a time)
};
void initialize_world(vector< vector<int> > &world, double p)
{
int i, j, n;
n = world.size();
// generate each cell to be alive with probability p
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
if (drand48()<p)
world[i][j] = 1;
else
world[i][j] = 0;
}
}
int count_neighbors(vector< vector<int> > &world,
int i,
int j,
int n)
{
int di, dj;
int num_neighbors=0;
// note that this assumes wrap-around world, in which
// the last cell in any row is a neighbor of the very
// first cell in the row; similarly for the columns
for (di = -1; di <= 1; di++)
for (dj = -1; dj <= 1; dj++)
if ((di!=0)||(dj!=0))
num_neighbors += world[(i+di+n)%n][(j+dj+n)%n];
// return the number of neighbors
return num_neighbors;
}
void process_world(vector< vector<int> > &new_world,
vector< vector<int> > &world)
{
int i, j;
int n = world.size();
// count neighbors of every cell, and generate the new
// world using the basic rules of the game of life
// - living cell dies if less than 2 living neighbors
// - living cell dies if more than 3 living neighbors
// - dead cell changes to living if exactly 3 neighbors
// - otherwise, no change
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
int num_neighbors = count_neighbors(world, i, j, n);
// these conditions implement the rules
if (world[i][j]==1) // living cell
{
if (num_neighbors<2)
new_world[i][j] = 0; // died because of underpopulation
else
if (num_neighbors>3)
new_world[i][j] = 0; // died because of overcrowding
else
new_world[i][j] = 1; // cell goes on living
}
else
if (num_neighbors==3) // dead cell
new_world[i][j] = 1; // reproduction (new cell)
else
new_world[i][j] = 0; // remains empty cell
}
}
void display_world(vector< vector<int> > &world)
{
int i, j;
int n = world.size();
int num_living = 0;
int num_dead = 0;
// show the content of each cell in a reasonably readable format
// (as a matrix with * denoting a living cell)
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
if (world[i][j]==1)
{
cout << "* ";
num_living++;
}
else
{
cout << " ";
num_dead++;
}
cout << endl;
}
cout << endl;
cout << "num_living = " << num_living << endl;
cout << "num_dead = " << num_dead << endl;
cout << endl;
}
void compute_statistics(vector< vector<int> > &world,
vector< vector<int> > &old_world,
stats_t &stats,
int t)
{
int i,j;
int n = world.size();
// the number of living and dead cells is 0 initially,
// and so is the number of changed cells
stats.num_living[t] = 0;
stats.num_dead[t] = 0;
stats.num_changed[t] = 0;
// do the counts
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
if (world[i][j]==1)
stats.num_living[t]++;
else
stats.num_dead[t]++;
if (world[i][j]!=old_world[i][j])
stats.num_changed[t]++;
}
}
void run_simulation(params_t ¶ms, stats_t &stats)
{
int i, t = 0;
vector< vector<int> > world(params.world_size);
vector< vector<int> > new_world(params.world_size);
// store the number of steps and make sure that there
// is enough space to store the statistics
stats.num_steps=params.max_t;
stats.num_living.resize(params.max_t+1);
stats.num_dead.resize(params.max_t+1);
stats.num_changed.resize(params.max_t+1);
// runs the simulation
for (i=0; i<params.world_size; i++)
{
world[i].resize(params.world_size);
new_world[i].resize(params.world_size);
}
// initialize the world
initialize_world(world, params.initial_proportion);
// compute statistics for the current time step (now t=0)
compute_statistics(world, world, stats, t);
// print out the initial world
if (params.display)
{
cout << "----------------------------------------------------------" << endl;
cout << "INITIAL WORLD" << endl << endl;
display_world(world);
}
for (t=1; t<=params.max_t; t++)
{
// create new world using the old world and the rules
process_world(new_world, world);
// new world becomes current world
swap(world, new_world);
// compute the statistics
compute_statistics(world, new_world, stats, t);
// print out the world (once in each params.delay steps)
if (((t-1)%params.delay==0)&&(params.display))
{
cout << "----------------------------------------------------------" << endl;
cout << "WORLD AT TIME " << t << endl << endl;
display_world(world);
}
}
}
void process_statistics(vector<stats_t> stats)
{
int run;
int t;
int num_runs = stats.size();
int max_t = stats[0].num_steps;
cout << "Final statistics over " << num_runs << " runs:" << endl;
// process statistics for all time steps and runs
// (averaging the numbers for each time step over
// the runs)
for (t=0; t<=max_t; t++)
{
double avg_num_living = 0;
double avg_num_dead = 0;
double avg_num_changed = 0;
for (run=0; run<num_runs; run++)
{
avg_num_living += stats[run].num_living[t];
avg_num_dead += stats[run].num_dead[t];
avg_num_changed += stats[run].num_changed[t];
}
avg_num_living /= num_runs;
avg_num_dead /= num_runs;
avg_num_changed /= num_runs;
cout << t << " " << avg_num_living << " " << avg_num_dead << " ";
cout << " " << avg_num_living*100/(avg_num_living+avg_num_dead) << " ";
cout << " " << avg_num_dead*100/(avg_num_living+avg_num_dead) << " ";
cout << " " << avg_num_changed*100/(avg_num_living+avg_num_dead) << " ";
cout << endl;
}
}
int main()
{
int run;
params_t params;
vector<stats_t> stats;
// initialize random number generator
srand48(123);
// read user parameters
cin >> params.world_size;
cin >> params.initial_proportion;
cin >> params.max_t;
cin >> params.delay;
cin >> params.num_runs;
cin >> params.display;
// adjust parameters if necessary
if (params.world_size<1)
params.world_size=1;
if (params.initial_proportion<0)
params.initial_proportion=0;
if (params.initial_proportion>1)
params.initial_proportion=1;
if (params.max_t<1)
params.max_t=1;
if (params.delay<1)
params.delay=1;
if (params.num_runs<1)
params.num_runs=1;
// print out parameters
cout << "World size: " << params.world_size << endl;
cout << "Initial proportion: " << params.initial_proportion << endl;
cout << "Maximum time steps: " << params.max_t << endl;
cout << "Reporting period: " << params.delay << endl;
cout << "Number of runs: " << params.num_runs << endl;
cout << "Display world: " << params.display << endl;
cout << endl;
// run the game of life simulation
stats.resize(params.num_runs); // resize the vector for statistics
for (run=0; run<params.num_runs; run++)
{
cout << "Executing run " << run << endl;
run_simulation(params, stats[run]); // execute one run
}
cout << endl;
// process statistics
process_statistics(stats);
// return 0 from main
return 0;
}