Percolation/Mean cluster density: Difference between revisions
Content added Content deleted
(New draft task and Python solution.) |
(+ D entry) |
||
Line 31: | Line 31: | ||
;See: |
;See: |
||
* [http://mathworld.wolfram.com/s-Cluster.html s-Cluster] on Wolfram mathworld. |
* [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}}== |
=={{header|Python}}== |