1. #include <iostream>
2. #include <vector>
3. #include <stdlib.h>
4.
5. using namespace std;
6.
7. struct params_t{
8. int world_size; // size of the world (side of the square world)
9. double initial_proportion; // initial proportion of living cells
10. int max_t; // maximum time for simulation
11. int delay; // period in terms of the number of time steps before
12. // each display of the world (to make more efficient
13. // outputs)
14. int num_runs; // number of runs to execute
15. int display; // turn on the display-world feature (yes=1, no=0)
16. };
17.
18. struct stats_t {
19. int num_steps; // the number of time steps
20. vector<int> num_living; // the number of living cells (at a time)
21. vector<int> num_dead; // the number of dead cells (at a time)
22. vector<int> num_changed; // the number of changed cells (at a time)
23. };
24.
25. void initialize_world(vector< vector<int> > &world, double p)
26. {
27. int i, j, n;
28.
29. n = world.size();
30.
31. // generate each cell to be alive with probability p
32.
33. for (i=0; i<n; i++)
34. for (j=0; j<n; j++)
35. {
36. if (drand48()<p)
37. world[i][j] = 1;
38. else
39. world[i][j] = 0;
40. }
41. }
42.
43. int count_neighbors(vector< vector<int> > &world,
44. int i,
45. int j,
46. int n)
47. {
48. int di, dj;
49. int num_neighbors=0;
50.
51. // note that this assumes wrap-around world, in which
52. // the last cell in any row is a neighbor of the very
53. // first cell in the row; similarly for the columns
54.
55. for (di = -1; di <= 1; di++)
56. for (dj = -1; dj <= 1; dj++)
57. if ((di!=0)||(dj!=0))
58. num_neighbors += world[(i+di+n)%n][(j+dj+n)%n];
59.
60. // return the number of neighbors
61.
62. return num_neighbors;
63. }
64.
65. void process_world(vector< vector<int> > &new_world,
66. vector< vector<int> > &world)
67. {
68. int i, j;
69. int n = world.size();
70.
71. // count neighbors of every cell, and generate the new
72. // world using the basic rules of the game of life
73. // - living cell dies if less than 2 living neighbors
74. // - living cell dies if more than 3 living neighbors
75. // - dead cell changes to living if exactly 3 neighbors
76. // - otherwise, no change
77.
78. for (i=0; i<n; i++)
79. for (j=0; j<n; j++)
80. {
81. int num_neighbors = count_neighbors(world, i, j, n);
82.
83. // these conditions implement the rules
84.
85. if (world[i][j]==1) // living cell
86. {
87. if (num_neighbors<2)
88. new_world[i][j] = 0; // died because of underpopulation
89. else
90. if (num_neighbors>3)
91. new_world[i][j] = 0; // died because of overcrowding
92. else
93. new_world[i][j] = 1; // cell goes on living
94. }
95. else
96. if (num_neighbors==3) // dead cell
97. new_world[i][j] = 1; // reproduction (new cell)
98. else
99. new_world[i][j] = 0; // remains empty cell
100. }
101. }
102.
103. void display_world(vector< vector<int> > &world)
104. {
105. int i, j;
106. int n = world.size();
107. int num_living = 0;
109.
110. // show the content of each cell in a reasonably readable format
111. // (as a matrix with * denoting a living cell)
112.
113. for (i=0; i<n; i++)
114. {
115. for (j=0; j<n; j++)
116. if (world[i][j]==1)
117. {
118. cout << "* ";
119. num_living++;
120. }
121. else
122. {
123. cout << " ";
125. }
126. cout << endl;
127. }
128.
129. cout << endl;
130. cout << "num_living = " << num_living << endl;
132. cout << endl;
133. }
134.
135. void compute_statistics(vector< vector<int> > &world,
136. vector< vector<int> > &old_world,
137. stats_t &stats,
138. int t)
139. {
140. int i,j;
141. int n = world.size();
142.
143. // the number of living and dead cells is 0 initially,
144. // and so is the number of changed cells
145.
146. stats.num_living[t] = 0;
148. stats.num_changed[t] = 0;
149.
150. // do the counts
151.
152. for (i=0; i<n; i++)
153. for (j=0; j<n; j++)
154. {
155. if (world[i][j]==1)
156. stats.num_living[t]++;
157. else
159.
160. if (world[i][j]!=old_world[i][j])
161. stats.num_changed[t]++;
162. }
163. }
164.
165. void run_simulation(params_t &params, stats_t &stats)
166. {
167. int i, t = 0;
168. vector< vector<int> > world(params.world_size);
169. vector< vector<int> > new_world(params.world_size);
170.
171. // store the number of steps and make sure that there
172. // is enough space to store the statistics
173.
174. stats.num_steps=params.max_t;
175. stats.num_living.resize(params.max_t+1);
177. stats.num_changed.resize(params.max_t+1);
178.
179. // runs the simulation
180.
181. for (i=0; i<params.world_size; i++)
182. {
183. world[i].resize(params.world_size);
184. new_world[i].resize(params.world_size);
185. }
186.
187. // initialize the world
188.
189. initialize_world(world, params.initial_proportion);
190.
191. // compute statistics for the current time step (now t=0)
192.
193. compute_statistics(world, world, stats, t);
194.
195. // print out the initial world
196.
197. if (params.display)
198. {
199. cout << "----------------------------------------------------------" << endl;
200. cout << "INITIAL WORLD" << endl << endl;
201. display_world(world);
202. }
203.
204. for (t=1; t<=params.max_t; t++)
205. {
206. // create new world using the old world and the rules
207.
208. process_world(new_world, world);
209.
210. // new world becomes current world
211.
212. swap(world, new_world);
213.
214. // compute the statistics
215.
216. compute_statistics(world, new_world, stats, t);
217.
218. // print out the world (once in each params.delay steps)
219.
220. if (((t-1)%params.delay==0)&&(params.display))
221. {
222. cout << "----------------------------------------------------------" << endl;
223. cout << "WORLD AT TIME " << t << endl << endl;
224. display_world(world);
225. }
226. }
227. }
228.
229. void process_statistics(vector<stats_t> stats)
230. {
231. int run;
232. int t;
233. int num_runs = stats.size();
234. int max_t = stats[0].num_steps;
235.
236. cout << "Final statistics over " << num_runs << " runs:" << endl;
237.
238. // process statistics for all time steps and runs
239. // (averaging the numbers for each time step over
240. // the runs)
241.
242. for (t=0; t<=max_t; t++)
243. {
244. double avg_num_living = 0;
246. double avg_num_changed = 0;
247.
248. for (run=0; run<num_runs; run++)
249. {
250. avg_num_living += stats[run].num_living[t];
252. avg_num_changed += stats[run].num_changed[t];
253. }
254.
255. avg_num_living /= num_runs;
257. avg_num_changed /= num_runs;
258.
259. cout << t << " " << avg_num_living << " " << avg_num_dead << " ";
260. cout << " " << avg_num_living*100/(avg_num_living+avg_num_dead) << " ";
262. cout << " " << avg_num_changed*100/(avg_num_living+avg_num_dead) << " ";
263. cout << endl;
264. }
265. }
266.
267. int main()
268. {
269. int run;
270. params_t params;
271. vector<stats_t> stats;
272.
273. // initialize random number generator
274.
275. srand48(123);
276.
278.
279. cin >> params.world_size;
280. cin >> params.initial_proportion;
281. cin >> params.max_t;
282. cin >> params.delay;
283. cin >> params.num_runs;
284. cin >> params.display;
285.
286. // adjust parameters if necessary
287.
288. if (params.world_size<1)
289. params.world_size=1;
290. if (params.initial_proportion<0)
291. params.initial_proportion=0;
292. if (params.initial_proportion>1)
293. params.initial_proportion=1;
294. if (params.max_t<1)
295. params.max_t=1;
296. if (params.delay<1)
297. params.delay=1;
298. if (params.num_runs<1)
299. params.num_runs=1;
300.
301. // print out parameters
302.
303. cout << "World size: " << params.world_size << endl;
304. cout << "Initial proportion: " << params.initial_proportion << endl;
305. cout << "Maximum time steps: " << params.max_t << endl;
306. cout << "Reporting period: " << params.delay << endl;
307. cout << "Number of runs: " << params.num_runs << endl;
308. cout << "Display world: " << params.display << endl;
309. cout << endl;
310.
311. // run the game of life simulation
312.
313. stats.resize(params.num_runs); // resize the vector for statistics
314. for (run=0; run<params.num_runs; run++)
315. {
316. cout << "Executing run " << run << endl;
317. run_simulation(params, stats[run]); // execute one run
318. }
319. cout << endl;
320.
321. // process statistics
322.
323. process_statistics(stats);
324.
325. // return 0 from main
326.
327. return 0;
328. }
329.
Success #stdin #stdout 1.06s 2876KB
stdin
20
0.2
100
1
100
0
stdout
World size:         20
Initial proportion: 0.2
Maximum time steps: 100
Reporting period:   1
Number of runs:     100
Display world:      0

Executing run 0
Executing run 1
Executing run 2
Executing run 3
Executing run 4
Executing run 5
Executing run 6
Executing run 7
Executing run 8
Executing run 9
Executing run 10
Executing run 11
Executing run 12
Executing run 13
Executing run 14
Executing run 15
Executing run 16
Executing run 17
Executing run 18
Executing run 19
Executing run 20
Executing run 21
Executing run 22
Executing run 23
Executing run 24
Executing run 25
Executing run 26
Executing run 27
Executing run 28
Executing run 29
Executing run 30
Executing run 31
Executing run 32
Executing run 33
Executing run 34
Executing run 35
Executing run 36
Executing run 37
Executing run 38
Executing run 39
Executing run 40
Executing run 41
Executing run 42
Executing run 43
Executing run 44
Executing run 45
Executing run 46
Executing run 47
Executing run 48
Executing run 49
Executing run 50
Executing run 51
Executing run 52
Executing run 53
Executing run 54
Executing run 55
Executing run 56
Executing run 57
Executing run 58
Executing run 59
Executing run 60
Executing run 61
Executing run 62
Executing run 63
Executing run 64
Executing run 65
Executing run 66
Executing run 67
Executing run 68
Executing run 69
Executing run 70
Executing run 71
Executing run 72
Executing run 73
Executing run 74
Executing run 75
Executing run 76
Executing run 77
Executing run 78
Executing run 79
Executing run 80
Executing run 81
Executing run 82
Executing run 83
Executing run 84
Executing run 85
Executing run 86
Executing run 87
Executing run 88
Executing run 89
Executing run 90
Executing run 91
Executing run 92
Executing run 93
Executing run 94
Executing run 95
Executing run 96
Executing run 97
Executing run 98
Executing run 99

Final statistics over 100 runs:
0 80.46 319.54  20.115  79.885  0
1 83.54 316.46  20.885  79.115  23.015
2 71.89 328.11  17.9725  82.0275  19.2875
3 72.41 327.59  18.1025  81.8975  16.09
4 68.92 331.08  17.23  82.77  16.0475
5 67.03 332.97  16.7575  83.2425  15.0875
6 67.02 332.98  16.755  83.245  14.7075
7 65.92 334.08  16.48  83.52  14.195
8 65.16 334.84  16.29  83.71  14.16
9 63.51 336.49  15.8775  84.1225  13.9775
10 63.55 336.45  15.8875  84.1125  13.545
11 62.57 337.43  15.6425  84.3575  13.415
12 62.17 337.83  15.5425  84.4575  13.07
13 61.5 338.5  15.375  84.625  13.2825
14 60.67 339.33  15.1675  84.8325  13.1025
15 59.41 340.59  14.8525  85.1475  12.825
16 59.32 340.68  14.83  85.17  12.6925
17 58.48 341.52  14.62  85.38  12.535
18 56.89 343.11  14.2225  85.7775  11.8975
19 56.7 343.3  14.175  85.825  11.8475
20 56.29 343.71  14.0725  85.9275  11.7925
21 56.18 343.82  14.045  85.955  11.6075
22 55.22 344.78  13.805  86.195  11.885
23 54.78 345.22  13.695  86.305  11.27
24 53.61 346.39  13.4025  86.5975  11.2975
25 53.82 346.18  13.455  86.545  11.2175
26 54 346  13.5  86.5  11.025
27 52.74 347.26  13.185  86.815  11.145
28 52.47 347.53  13.1175  86.8825  10.8875
29 51.48 348.52  12.87  87.13  10.8825
30 50.79 349.21  12.6975  87.3025  10.5025
31 51.01 348.99  12.7525  87.2475  10.345
32 51.11 348.89  12.7775  87.2225  10.37
33 51.2 348.8  12.8  87.2  10.5075
34 51.35 348.65  12.8375  87.1625  10.3975
35 51.45 348.55  12.8625  87.1375  10.385
36 50.69 349.31  12.6725  87.3275  10.515
37 51.03 348.97  12.7575  87.2425  10.485
38 49.79 350.21  12.4475  87.5525  10.615
39 48.92 351.08  12.23  87.77  10.4175
40 48.71 351.29  12.1775  87.8225  10.0425
41 48.41 351.59  12.1025  87.8975  10.005
42 47.08 352.92  11.77  88.23  9.9425
43 47.21 352.79  11.8025  88.1975  9.6225
44 46.87 353.13  11.7175  88.2825  9.415
45 46.46 353.54  11.615  88.385  9.3425
46 46.95 353.05  11.7375  88.2625  9.3975
47 45.63 354.37  11.4075  88.5925  9.375
48 47.67 352.33  11.9175  88.0825  9.295
49 46.69 353.31  11.6725  88.3275  9.94
50 46.21 353.79  11.5525  88.4475  9.665
51 46.62 353.38  11.655  88.345  9.4475
52 45.38 354.62  11.345  88.655  9.445
53 45.21 354.79  11.3025  88.6975  9.2225
54 44.83 355.17  11.2075  88.7925  9.225
55 45.5 354.5  11.375  88.625  8.9475
56 45.67 354.33  11.4175  88.5825  9.0775
57 46.16 353.84  11.54  88.46  9.1525
58 45.4 354.6  11.35  88.65  9.16
59 45.2 354.8  11.3  88.7  9.045
60 46.12 353.88  11.53  88.47  9.075
61 45.67 354.33  11.4175  88.5825  9.1875
62 44.62 355.38  11.155  88.845  9.1275
63 45.1 354.9  11.275  88.725  8.725
64 45.03 354.97  11.2575  88.7425  9.1925
65 44.26 355.74  11.065  88.935  9.0625
66 43.62 356.38  10.905  89.095  8.825
67 42.25 357.75  10.5625  89.4375  8.6575
68 42.1 357.9  10.525  89.475  8.4825
69 42.98 357.02  10.745  89.255  8.21
70 42.34 357.66  10.585  89.415  7.955
71 41.59 358.41  10.3975  89.6025  8.1475
72 42.77 357.23  10.6925  89.3075  7.79
73 43.22 356.78  10.805  89.195  8.1975
74 43.33 356.67  10.8325  89.1675  8.0575
75 42.35 357.65  10.5875  89.4125  8.305
76 41.93 358.07  10.4825  89.5175  8.095
77 41.14 358.86  10.285  89.715  8.0625
78 40.7 359.3  10.175  89.825  8.02
79 40.44 359.56  10.11  89.89  7.59
80 40.25 359.75  10.0625  89.9375  7.6125
81 39.73 360.27  9.9325  90.0675  7.52
82 40.06 359.94  10.015  89.985  7.2275
83 39.18 360.82  9.795  90.205  7.575
84 39.29 360.71  9.8225  90.1775  7.3075
85 39.53 360.47  9.8825  90.1175  7.515
86 40.77 359.23  10.1925  89.8075  7.45
87 38.92 361.08  9.73  90.27  7.9125
88 39.7 360.3  9.925  90.075  7.52
89 39.34 360.66  9.835  90.165  7.52
90 39.44 360.56  9.86  90.14  7.52
91 39.09 360.91  9.7725  90.2275  7.6225
92 38.77 361.23  9.6925  90.3075  7.38
93 37.45 362.55  9.3625  90.6375  7.32
94 37.22 362.78  9.305  90.695  7.0675
95 37.43 362.57  9.3575  90.6425  6.9525
96 37.43 362.57  9.3575  90.6425  6.715
97 36.34 363.66  9.085  90.915  6.7375
98 35.49 364.51  8.8725  91.1275  6.6175
99 35.52 364.48  8.88  91.12  6.3525
100 34.8 365.2  8.7  91.3  6.35