Percolation/Site percolation: Difference between revisions

Content added Content deleted
m (correct D code to match requirements)
m (correct C code to match requirements)
Line 20: Line 20:


=={{header|C}}==
=={{header|C}}==
{{incomplete|C|"p going from 0.0 to 1.0 in 0.1 increments" (not 0.02 increments)}}
{{trans|D}}
{{trans|D}}
<lang c>#include <stdio.h>
<lang c>#include <stdio.h>
Line 27: Line 26:
#include <string.h>
#include <string.h>
#include <stdbool.h>
#include <stdbool.h>

#define N_COLS 15
#define N_COLS 15
#define N_ROWS 15
#define N_ROWS 15

// Probability granularity
// Probability granularity 0.0, 0.1, ... 1.0
#define N_STEPS 50
#define N_STEPS 11

// Simulation tries
// Simulation tries
#define N_TRIES 20000
#define N_TRIES 100

typedef unsigned char Cell;
typedef unsigned char Cell;
enum { EMPTY_CELL = ' ',
enum { EMPTY_CELL = ' ',
Line 42: Line 41:
VISITED_CELL = '.' };
VISITED_CELL = '.' };
typedef Cell Grid[N_ROWS][N_COLS];
typedef Cell Grid[N_ROWS][N_COLS];

void initialize(Grid grid, const double probability) {
void initialize(Grid grid, const double probability) {
for (size_t r = 0; r < N_ROWS; r++)
for (size_t r = 0; r < N_ROWS; r++)
Line 50: Line 49:
}
}
}
}

void show(Grid grid) {
void show(Grid grid) {
char line[N_COLS + 3];
char line[N_COLS + 3];
Line 57: Line 56:
line[N_COLS + 1] = '+';
line[N_COLS + 1] = '+';
line[N_COLS + 2] = '\0';
line[N_COLS + 2] = '\0';

printf("%s\n", line);
printf("%s\n", line);
for (size_t r = 0; r < N_ROWS; r++) {
for (size_t r = 0; r < N_ROWS; r++) {
Line 67: Line 66:
printf("%s\n", line);
printf("%s\n", line);
}
}

bool walk(Grid grid, const size_t r, const size_t c) {
bool walk(Grid grid, const size_t r, const size_t c) {
const size_t bottom = N_ROWS - 1;
const size_t bottom = N_ROWS - 1;
grid[r][c] = VISITED_CELL;
grid[r][c] = VISITED_CELL;

if (r < bottom && grid[r + 1][c] == EMPTY_CELL) { // Down.
if (r < bottom && grid[r + 1][c] == EMPTY_CELL) { // Down.
if (walk(grid, r + 1, c))
if (walk(grid, r + 1, c))
Line 77: Line 76:
} else if (r == bottom)
} else if (r == bottom)
return true;
return true;

if (c && grid[r][c - 1] == EMPTY_CELL) // Left.
if (c && grid[r][c - 1] == EMPTY_CELL) // Left.
if (walk(grid, r, c - 1))
if (walk(grid, r, c - 1))
return true;
return true;

if (c < N_COLS - 1 && grid[r][c + 1] == EMPTY_CELL) // Right.
if (c < N_COLS - 1 && grid[r][c + 1] == EMPTY_CELL) // Right.
if (walk(grid, r, c + 1))
if (walk(grid, r, c + 1))
return true;
return true;

if (r && grid[r - 1][c] == EMPTY_CELL) // Up.
if (r && grid[r - 1][c] == EMPTY_CELL) // Up.
if (walk(grid, r - 1, c))
if (walk(grid, r - 1, c))
return true;
return true;

return false;
return false;
}
}

bool percolate(Grid grid) {
bool percolate(Grid grid) {
const size_t startR = 0;
const size_t startR = 0;
Line 101: Line 100:
return false;
return false;
}
}

typedef struct {
typedef struct {
double prob;
double prob;
size_t count;
size_t count;
} Counter;
} Counter;

int main() {
int main() {
const double probability_step = 1.0 / N_STEPS;
const double probability_step = 1.0 / (N_STEPS - 1);
Counter counters[N_STEPS];
Counter counters[N_STEPS];
for (size_t i = 0; i < N_STEPS; i++)
for (size_t i = 0; i < N_STEPS; i++)
counters[i] = (Counter){ i * probability_step, 0 };
counters[i] = (Counter){ i * probability_step, 0 };

bool sample_shown = false;
bool sample_shown = false;
static Grid grid;
static Grid grid;
srand(time(NULL));
srand(time(NULL));

for (size_t i = 0; i < N_STEPS; i++) {
for (size_t i = 0; i < N_STEPS; i++) {
for (size_t t = 0; t < N_TRIES; t++) {
for (size_t t = 0; t < N_TRIES; t++) {
Line 132: Line 131:
}
}
}
}

printf("\nFraction of %d tries that percolate through:\n", N_TRIES);
printf("\nFraction of %d tries that percolate through:\n", N_TRIES);
for (size_t i = 0; i < N_STEPS; i++)
for (size_t i = 0; i < N_STEPS; i++)
printf("%1.3f %1.3f\n", counters[i].prob,
printf("%1.1f %1.3f\n", counters[i].prob,
counters[i].count / (double)N_TRIES);
counters[i].count / (double)N_TRIES);

return 0;
return 0;
}
}</lang>
</lang>
{{out}}
{{out}}
<pre>Percolating sample (15x15, probability = 0.30):
<pre>Percolating sample (15x15, probability = 0.40):
+---------------+
+---------------+
|######..## ## |
|###. # # # #|
|### ##.# ### #|
|###.. # ##### |
|# # ##..### #|
| #. ###### #|
| ## #.# ###|
|###.... ######|
|## ### #.######|
|######. ### # |
| ## ## .######|
| #####.###### |
| ## # ##..#####|
|#......... ## |
|### ####.# # #|
|...#...##.# ## |
| ##### ...# ##|
|##.#...##.### #|
|### ###.### ###|
| ###..# #. # |
|##### #.### ###|
|# #######. # ##|
|#######.# ## ##|
| # ##...#### |
| ###.. ######|
| ## # .##### |
| #### .# ### #|
|#######.## ###|
|## ##.##### # |
|# ## .## # # |
+---------------+
+---------------+


Fraction of 20000 tries that percolate through:
Fraction of 100 tries that percolate through:
0.000 0.000
0.0 0.000
0.020 0.000
0.1 0.000
0.040 0.000
0.2 0.000
0.060 0.000
0.3 0.000
0.080 0.000
0.4 0.010
0.100 0.000
0.5 0.070
0.120 0.000
0.6 0.630
0.140 0.000
0.7 0.970
0.160 0.000
0.8 1.000
0.180 0.000
0.9 1.000
0.200 0.000
1.0 1.000</pre>
0.220 0.000
0.240 0.000
0.260 0.000
0.280 0.000
0.300 0.000
0.320 0.000
0.340 0.000
0.360 0.000
0.380 0.001
0.400 0.004
0.420 0.007
0.440 0.015
0.460 0.029
0.480 0.056
0.500 0.093
0.520 0.155
0.540 0.226
0.560 0.332
0.580 0.437
0.600 0.564
0.620 0.680
0.640 0.783
0.660 0.862
0.680 0.920
0.700 0.959
0.720 0.981
0.740 0.991
0.760 0.997
0.780 0.999
0.800 1.000
0.820 1.000
0.840 1.000
0.860 1.000
0.880 1.000
0.900 1.000
0.920 1.000
0.940 1.000
0.960 1.000
0.980 1.000
</pre>


=={{header|D}}==
=={{header|D}}==
Retrieved from "https://rosettacode.org/wiki/Percolation/Site_percolation"