Anonymous user
Percolation/Site percolation: Difference between revisions
+ D entry
(→{{header|Python}}: Add link.) |
(+ D entry) |
||
Line 22:
* [[wp:Percolation theory|Percolation theory]]
* [[Percolation/Bond percolation]]
=={{header|D}}==
{{trans|Python}}
<lang d>import std.stdio, std.random, std.array, std.datetime;
enum size_t nCols = 15,
nRows = 15,
nSteps = 50, // Probability granularity.
nTries = 20_000; // Simulation tries.
alias BaseType = char;
enum Cell : BaseType { empty = ' ',
filled = '#',
visited = '.' }
alias Grid = Cell[nCols][nRows];
void initialize(ref Grid grid, in double probability,
ref Xorshift rng) {
foreach (ref row; grid)
foreach (ref cell; row) {
immutable r = rng.front / cast(double)rng.max;
rng.popFront;
cell = r < probability ? Cell.empty : Cell.filled;
}
}
void show(in ref Grid grid) {
immutable static line = '+' ~ "-".replicate(nCols) ~ "+";
line.writeln;
foreach (const ref row; grid)
writeln('|' ~ cast(BaseType[nCols])row ~ '|');
line.writeln;
}
bool percolate(ref Grid grid) pure nothrow {
bool walk(in size_t r, in size_t c) nothrow {
enum bottom = nRows - 1;
grid[r][c] = Cell.visited;
if (r < bottom && grid[r + 1][c] == Cell.empty) { // Down.
if (walk(r + 1, c))
return true;
} else if (r == bottom)
return true;
if (c && grid[r][c - 1] == Cell.empty) // Left.
if (walk(r, c - 1))
return true;
if (c < nCols - 1 && grid[r][c + 1] == Cell.empty) // Right.
if (walk(r, c + 1))
return true;
if (r && grid[r - 1][c] == Cell.empty) // Up.
if (walk(r - 1, c))
return true;
return false;
}
enum startR = 0;
foreach (immutable c; 0 .. nCols)
if (grid[startR][c] == Cell.empty)
if (walk(startR, c))
return true;
return false;
}
void main() {
static struct Counter {
double prob;
size_t count;
}
StopWatch sw;
sw.start;
enum probabilityStep = 1.0 / nSteps;
Counter[nSteps] counters;
foreach (immutable i, ref co; counters)
co.prob = i * probabilityStep;
Grid grid;
bool sampleShown = false;
auto rng = Xorshift(unpredictableSeed);
foreach (ref co; counters) {
foreach (immutable _; 0 .. nTries) {
grid.initialize(co.prob, rng);
if (grid.percolate) {
co.count++;
if (!sampleShown) {
writefln("Percolating sample (%dx%d," ~
" probability =%5.2f):",
nCols, nRows, co.prob);
grid.show;
sampleShown = true;
}
}
}
}
sw.stop;
writefln("\nFraction of %d tries that percolate through:", nTries);
foreach (const co; counters)
writefln("%1.3f %1.3f", co.prob, co.count / cast(double)nTries);
writefln("\nSimulations and grid printing performed" ~
" in %3.2f seconds.", sw.peek.msecs / 1000.0);
}</lang>
{{out}}
<pre>Percolating sample (15x15, probability = 0.30):
+---------------+
|.#####.#### # |
|# ###... #### #|
|## ####. ##### |
|# ### ..# # # |
| # # #.## ## ##|
|## # #..##### #|
|# # ###. # # |
|### ## .# # |
| ##### . #### |
| ## ###..# # #|
| #####. # # |
|#####....## ## |
|#### .### ## #|
| ###.. ## #|
| # ###.###### #|
+---------------+
Fraction of 20000 tries that percolate through:
0.000 0.000
0.020 0.000
0.040 0.000
0.060 0.000
0.080 0.000
0.100 0.000
0.120 0.000
0.140 0.000
0.160 0.000
0.180 0.000
0.200 0.000
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.001
0.380 0.002
0.400 0.004
0.420 0.007
0.440 0.015
0.460 0.029
0.480 0.054
0.500 0.094
0.520 0.152
0.540 0.232
0.560 0.331
0.580 0.445
0.600 0.565
0.620 0.677
0.640 0.782
0.660 0.860
0.680 0.918
0.700 0.959
0.720 0.978
0.740 0.992
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
Simulations and grid printing performed in 5.28 seconds.</pre>
=={{header|Python}}==
| |||