Anonymous user
Percolation/Mean cluster density: Difference between revisions
+ D entry
(New draft task and Python solution.) |
(+ D entry) |
||
Line 31:
;See:
* [http://mathworld.wolfram.com/s-Cluster.html s-Cluster] on Wolfram mathworld.
=={{header|D}}==
{{trans|python}}
<lang d>import std.stdio, std.algorithm, std.random, std.math, std.array,
std.range, std.ascii;
alias Cell = uint;
alias Grid = Cell[][];
enum Cell notClustered = 1; // Filled cell, but not in in a cluster.
Grid initialize(Grid grid, in double prob) /*nothrow*/ {
foreach (row; grid)
foreach (ref cell; row)
cell = uniform(cast(Cell)0, cast(Cell)2);
return grid;
}
void show(in Grid grid) {
immutable static cell2char = " #" ~ letters;
writeln('+', std.array.replicate("-", grid.length), '+');
foreach (row; grid) {
write('|');
row.map!(c => c < cell2char.length ? cell2char[c] : '@').write;
writeln('|');
}
writeln('+', std.array.replicate("-", grid.length), '+');
}
size_t countClusters(Grid grid) pure nothrow {
immutable side = grid.length;
Cell clusterID = 1;
void walk(in size_t r, in size_t c) nothrow {
grid[r][c] = clusterID;
if (r < side - 1 && grid[r + 1][c] == notClustered) // Down.
walk(r + 1, c);
if (c < side - 1 && grid[r][c + 1] == notClustered) // Right.
walk(r, c + 1);
if (c > 0 && grid[r][c - 1] == notClustered) // Left.
walk(r, c - 1);
if (r > 0 && grid[r - 1][c] == notClustered) // Up.
walk(r - 1, c);
}
foreach (immutable r; 0 .. side)
foreach (immutable c; 0 .. side)
if (grid[r][c] == notClustered) {
clusterID++;
walk(r, c);
}
return clusterID - 1;
}
double clusterDensity(Grid grid, in double prob) {
return grid.initialize(prob).countClusters /
cast(double)(grid.length ^^ 2);
}
void showDemo(in size_t side, in double prob) {
auto grid = new Grid(side, side);
grid.initialize(prob);
writefln("Found %d clusters in this %d by %d grid:\n",
grid.countClusters, side, side);
grid.show;
}
void main() {
immutable prob = 0.5;
immutable nIters = 5;
showDemo(15, prob);
writeln;
foreach (immutable i; iota(4, 14, 2)) {
immutable side = 2 ^^ i;
auto grid = new Grid(side, side);
immutable density = nIters
.iota
.map!(_ => grid.clusterDensity(prob))
//.sum / nIters;
.reduce!q{a + b} / nIters;
writefln("n_iters=%3d, p=%4.2f, n=%5d, sim=%7.8f",
nIters, prob, side, density);
}
}</lang>
{{out}}
<pre>Found 26 clusters in this 15 by 15 grid:
+---------------+
| AA B CCCC |
|AA D E F CC G |
| DDD FF CC H|
| I D FF J K |
| L FF JJJJ |
|L LLL J M|
|LLLLLL JJJ MM|
|L LL L N J M|
|LL O P J M|
|LLL QQ R JJ S |
|LL T RR J SSS|
| L U V JJ S|
| WW XX JJ YY |
| XXX JJ YY|
|ZZ XXX JJ |
+---------------+
n_iters= 5, p=0.50, n= 16, sim=0.09765625
n_iters= 5, p=0.50, n= 64, sim=0.07260742
n_iters= 5, p=0.50, n= 256, sim=0.06679993
n_iters= 5, p=0.50, n= 1024, sim=0.06609497
n_iters= 5, p=0.50, n= 4096, sim=0.06580237</pre>
Increasing the maximum index i to 16 (the grid takes about 1 GB):
<pre>n_iters= 5, p=0.50, n= 16, sim=0.07343750
n_iters= 5, p=0.50, n= 64, sim=0.07290039
n_iters= 5, p=0.50, n= 256, sim=0.06653748
n_iters= 5, p=0.50, n= 1024, sim=0.06601048
n_iters= 5, p=0.50, n= 4096, sim=0.06586764
n_iters= 5, p=0.50, n=16384, sim=0.06579554</pre>
=={{header|Python}}==
| |||