|
</pre>
=={{header|D}}==
{{trans|C}}
{{incorrect|D| Results from p=0.3 to p=0.6 are statistically implausible, please check code. }}
<lang d>import std.stdio, std.random, std.array, std.range, std.algorithm;
{{trans|Python}}
Compared to the Python entry, the <code>initialize</code> function is a performance optimization useful when nTries is high.
<lang d>import std.stdio, std.random, std.array, std.algorithm, std.range,
std.typecons;
struct Grid {
// Not enforced by runtime and type system:
immutable int nr, nc;
// a Cell must contain only the flags bits.
bool[][] hWalls, vWalls, cells;
alias MaybeColCell = Nullable!(int, int.min)uint;
Xorshift rng;
enum : Cell { // Cell states (bit flags).
empty = 0,
filled = 1,
rightWall = 2,
bottomWall = 4
}
const size_t nc, nr;
Cell[] cells;
this(in uintsize_t nRows, in uintsize_t nCols, in uint seed) pure nothrow {
nr = nRows;
nc = nCols;
hWalls = new typeof(hWalls)(nr + 1, nc);
vWalls = new typeof(vWalls)(nr, nc + 1);
cells = new typeof(cells)(nr, nc);
rng.seed = seed;
}
// Allocate two addition rows to avoid checking bounds.
void initialize(in double probability) {
foreach// (refBottom row; hWalls)is also required by drippage.
cells = new Cell[nc foreach* (refnr x;+ row2)];
x = uniform(0.0, 1.0, rng) < probability;
foreach (ref row; vWalls)
foreach (immutable c, ref x; row)
x = (c == 0 || c == nc) ?
true :
(uniform(0.0, 1.0, rng) < probability);
foreach (ref row; cells)
row[] = false;
}
void showinitialize(in MaybeColdouble percolatedCol)prob, constref Xorshift rng) {
cells[0 .. nc] = bottomWall | rightWall; // First row.
// Horiz, vert, fill chars.
static immutable h = ["+ ", "+-"],
v = [" ", "|"],
f = [" ", "#", "X"];
foreachuint (immutablepos r= nc; 0 .. nr) {
foreach (immutable r; 1 .. nr + 1) {
writefln("%-(%s%)+", nc.iota.map!(c => h[hWalls[r][c]]));
writefln("%-(%s%)",foreach iota(ncimmutable +c; 1 .. nc)
.map!(c => vcells[vWalls[r][c]pos++] ~=
(uniform(0.0, 1.0, rng) < f[c<ncprob ? cells[r][c] : 0]));
bottomWall :
empty) |
(uniform(0.0, 1.0, rng) < prob ?
rightWall :
empty);
cells[pos++] = rightWall |
(uniform(0.0, 1.0, rng) < prob ?
bottomWall :
empty);
}
writefln("%-(%s%)+", nc.iota.map!(c => h[hWalls[nr][c]]));
cells[$ - nc .. $] = empty; // Last row.
if (!percolatedCol.isNull)
writeln(" ".replicate(percolatedCol), " ",f[2]);
}
MaybeColbool pourOnToppercolate() pure nothrow {
MaybeColbool floodFillfill(in intsize_t r, in int ci) pure nothrow {
if (cells[ri][c] = true; // Fill& cell.filled)
return false;
//cells[i] Bottom.|= filled;
if (r < nr - 1 && !hWalls[r + 1][c] && !cells[r + 1][c])
return floodFill(r + 1, c);
else if (r == nr - 1 && !hWalls[r + 1][c]) // The bottom.
return MaybeCol(c);
//if Left(i >= cells.length - nc)
if (c && !vWalls[r][c] &&return !cells[r][ctrue; -// 1])Success: reached bottom row.
return floodFill(r, c - 1);
return (!(cells[i] & bottomWall) && fill(i + nc)) ||
// Right.
if (c < nc - 1 && (!vWalls(cells[ri][c + 1] & rightWall) && !cells[r][cfill(i + 1])) ||
return floodFill (r,!(cells[i c- +1] & rightWall) && fill(i - 1);) ||
(!(cells[i - nc] & bottomWall) && fill(i - nc));
}
return iota(nc, nc + // Topnc).any!fill;
}
if (r && !hWalls[r][c] && !cells[r - 1][c])
return floodFill(r - 1, c);
void show() const {
return MaybeCol();
writeln("+-".replicate(nc), '+');
}
foreach (immutable r; =1 0;.. //nr From+ top.2) {
foreach write(immutabler c;== 0nr ..+ nc1 ? ' ' : '|');
ifforeach (!hWalls[r][immutable c]; 0 .. nc) {
immutable percolatedColcell = floodFill(cells[r, * nc + c)];
ifwrite((cell & filled) ? (!percolatedCol.isNullr <= nr ? '#' : 'X') : ' ');
write((cell & rightWall) ? return'|' percolatedCol: ' ');
}
return MaybeCol() writeln;
if (r == nr + 1)
return;
foreach (immutable c; 0 .. nc)
write((cells[r * nc + c] & bottomWall) ? "+-" : "+ ");
'+'.writeln;
}
}
}
void main() {
enum intuint nr = 10, nc = 10; // N. rows and columns of the grid.
enum intuint nTries = 1_00010_000; // N. simulations for each probability.
enum intuint nStepsProb = 10; // N. steps of probability.
boolauto sampleShownrng = falseXorshift(2);
aliasauto Pairg = Tuple!Grid(double,"prob"nr, uint,"co"nc);
g.initialize(0.5, rng);
Pair[] results;
g.percolate;
g.show;
writefln("\nRunning %dx%d grids %d times for each p:",
foreach (immutable i; 0 .. nStepsProb + 1) {
// Count down so sample printnr, isnc, interesting.nTries);
foreach (immutable p; 0 immutable.. probability = (nStepsProb - i) /{
immutable probability = p / cast(double)nStepsProb;
autouint gridnPercolated = Grid(nr, nc, unpredictableSeed)0;
uintforeach lastCount(immutable =i; 0; .. nTries) {
g.initialize(probability, rng);
foreach (immutable _; 0 ..nPercolated nTries)+= {g.percolate;
grid.initialize(probability);
immutable percolatedCol = grid.pourOnTop;
if (!percolatedCol.isNull) {
lastCount++;
if (!sampleShown) {
writefln("Percolating sample %dx%d grid," ~
" probability=%1.1f:", nc,nr,probability);
grid.show(percolatedCol);
sampleShown = true;
}
}
}
resultswritefln("p ~= Pair(probability,%0.2f: lastCount);%.4f",
probability, nPercolated / cast(double)nTries);
}
writefln("\nFraction of %d tries that percolate," ~
" varying probability p:", nTries);
foreach (const r; results)
writefln("p=%1.2f: %1.3f", r.prob, r.co / cast(double)nTries);
}</lang>
{{out}}
<pre>+-+-+-+-+-+-+-+-+-+-+
<pre>Percolating sample 10x10 grid, probability=0.6:
|#|#|#|#| | | |
+ + + + + +-+-+-+-+-+
+ +-+-+ +-+-+-+ +-+-+
|#|# # # #| | | |
+|#| +| + +# + +| +| +| +-+-+ | |
+ +-+-+ + +-+-+ + +-+
|# #|# #|# #| | | | |
|#|# #|#| | | |
+ + + +-+-+ +-+ +-+ +
|#+ #|#|+-+ |+ |#|+-+ + + +-+ | +
|#|# #|#| | | | |
+-+ +-+ +-+ +-+ + +-+
+-+ + + + +-+-+-+-+-+
| |#| # # # | | |
|# # # # # | | | |
+-+-+ + +-+-+-+ + + +
|+ |+ |+ |#+ #|+ |+ + +-+ | | | +-+
+-+|#|# +# +-+#|# +-+# +# +-+-+ | |
|+-+ + + |+-+-+ |#+ #|+ + | | | | +
| |#|# #| | |# |
+-+-+-+ +-+ + +-+ + +
+-+-+-+-+ +-+ +-+-+-+
| | | |# | | |
| | | # #| |
+-+-+ + +-+-+-+-+-+-+
+-+-+-+ +-+ +-+-+-+ +
| |# | | | |
+| +-+-+| +| +-+ + + + + # # # |
+ + +-+ +-+-+-+ +-+ +
| #| | | | | |
+-+| + + +-+ + +-+| + + | |# |
|+ +-+ + |+ + #|+-+ + + | | | +
X
+ + + + +-+-+-+ +-+ +
X
Running 10x10 grids 10000 times for each p:
Fraction of 1000 tries that percolate, varying probability p:
p =1 0.00: 01.0000000
p = 0.9010: 01.0000000
p = 0.8020: 01.0000000
p = 0.7030: 0.0009973
p = 0.6040: 0.0079177
p = 0.50: 0.1425050
p = 0.4060: 0.5730880
p = 0.3070: 0.9290035
p = 0.2080: 0.9980001
p = 0.1090: 10.0000000</pre>
With LDC2 compiler this code is almost three times slower than the C entry.
p=0.00: 1.000</pre>
=={{header|Python}}==
| 