Percolation/Site percolation: Difference between revisions
m
→{{header|11l}}: Void
m (→{{header|Phix}}: syntax coloured) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (8 intermediate revisions by 4 users not shown) | |||
Line 22:
{{trans|Python}}
<
F nonrandom()
:seed = 1664525 * :seed + 1013904223
Line 48:
print(‘!) ’(‘ ’ * where)‘’:cell2char[cell[:nn - 1][where]])
F walk_maze(m, n, &cell, indx) X(PercolatedException) ->
cell[n][m] = indx
I n < :nn - 1 & cell[n + 1][m] == :NOT_VISITED
Line 63:
F check_from_top(&cell) -> (Int, Int)?
V (n, walk_index) = (0, 1)
walk_maze(m, n, &cell, walk_index
X.handle PercolatedException ex
R ex.t
R N
Line 89 ⟶ 88:
L(p, c) sorted(pcount.items())
print(‘#.1: #.’.format(p, c / Float(t)))</
{{out}}
Line 129 ⟶ 128:
=={{header|C}}==
<
#include <stdlib.h>
#include <string.h>
Line 193 ⟶ 192:
return 0;
}</
{{out}}
<pre>
Line 227 ⟶ 226:
</pre>
{{trans|D}}
<
#include <stdlib.h>
#include <time.h>
Line 345 ⟶ 344:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>Percolating sample (15x15, probability = 0.40):
Line 378 ⟶ 377:
0.9 1.000
1.0 1.000</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <iostream>
#include <vector>
#include <string>
#include <random>
#include <iomanip>
std::random_device random;
std::mt19937 generator(random());
std::uniform_real_distribution<double> distribution(0.0F, 1.0F);
class Grid {
public:
Grid(const int32_t row_count, const int32_t col_count, const double probability) {
create_table(row_count, col_count, probability);
}
bool percolate() {
for ( int32_t x = 0; x < (int32_t) table[0].size(); ++x ) {
if ( path_exists(x, 0) ) {
return true;
}
}
return false;
}
void display() const {
for ( uint64_t col = 0; col < table.size(); ++col ) {
for ( uint64_t row = 0; row < table[0].size(); ++row ) {
std::cout << " " << table[col][row];
}
std::cout << std::endl;
}
std::cout << std::endl;
}
private:
bool path_exists(const int32_t x, const int32_t y) {
if ( y < 0 || x < 0 || x >= (int32_t) table[0].size() || table[y][x].compare(FILLED) != 0 ) {
return false;
}
table[y][x] = PATH;
if ( y == (int32_t) table.size() - 1 ) {
return true;
}
return path_exists(x, y + 1) || path_exists(x + 1, y) || path_exists(x - 1, y) || path_exists(x, y - 1);
}
void create_table(const int32_t row_count, const int32_t col_count, const double probability) {
table.assign(row_count, std::vector<std::string>(col_count, EMPTY));
for ( int32_t col = 0; col < row_count; ++col ) {
for ( int32_t row = 0; row < col_count; ++row ) {
table[col][row] = ( distribution(generator) < probability ) ? FILLED: EMPTY;
}
}
}
std::vector<std::vector<std::string>> table;
inline static const std::string EMPTY = " ";
inline static const std::string FILLED = ".";
inline static const std::string PATH = "#";
};
int main() {
const int32_t row_count = 15;
const int32_t col_count = 15;
const int32_t test_count = 1'000;
Grid grid(row_count, col_count, 0.5);
grid.percolate();
grid.display();
std::cout << "Proportion of " << test_count << " tests that percolate through the grid:" << std::endl;
for ( double probable = 0.0; probable <= 1.0; probable += 0.1 ) {
double percolation_count = 0.0;
for ( int32_t test = 0; test < test_count; ++test ) {
Grid test_grid(row_count, col_count, probable);
if ( test_grid.percolate() ) {
percolation_count += 1.0;
}
}
const double percolation_proportion = percolation_count / test_count;
std::cout << " p = " << std::setprecision(1) <<std::fixed << probable << " : "
<< std::setprecision(4) << percolation_proportion << std::endl;
}
}
</syntaxhighlight>
{{ out }}
<pre>
# . . . . . . . . .
# . . . . . . .
# . . . . . . . . . .
# # . . . . . . .
# . . . . . . . .
# # . . . . .
. # # . . . . .
. . # . . . . . . .
. # # . . . . .
. # . . .
# . . . . . . .
. # # # . . . . .
# # # . . . . .
# # . .
# . . . . . .
Proportion of 1000 tests that percolate through the grid:
p = 0.0: 0.0000
p = 0.1: 0.0000
p = 0.2: 0.0000
p = 0.3: 0.0000
p = 0.4: 0.0020
p = 0.5: 0.0930
p = 0.6: 0.5330
p = 0.7: 0.9750
p = 0.8: 0.9990
p = 0.9: 1.0000
p = 1.0: 1.0000
</pre>
=={{header|D}}==
{{trans|Python}}
<
enum size_t nCols = 15,
Line 475 ⟶ 594:
writefln("\nSimulations and grid printing performed" ~
" in %3.2f seconds.", sw.peek.msecs / 1000.0);
}</
{{out}}
<pre>Percolating sample (15x15, probability = 0.40):
Line 510 ⟶ 629:
=={{header|Factor}}==
<
fry generalizations io kernel math math.matrices math.order
math.ranges math.vectors prettyprint random sequences ;
Line 564 ⟶ 683:
] each ;
MAIN: site-percolation</
{{out}}
<pre>
Line 600 ⟶ 719:
Please see sample compilation and program execution in comments at top of program. Thank you. This example demonstrates recursion and integer constants of a specific kind.
<
! loosely translated from python.
! compilation: gfortran -Wall -std=f2008 thisfile.f08
Line 724 ⟶ 843:
end program percolation_site
</syntaxhighlight>
=={{header|FreeBASIC}}==
{{trans|Phix}}
<
#define EMPTY " "
#define WET "v"
Line 783 ⟶ 902:
Print Using "p=#.#: #.####"; p; cont/10000
Next ip
Sleep</
=={{header|Go}}==
<
import (
Line 899 ⟶ 1,018:
g.use(x-1, y) ||
g.use(x, y-1)
}</
{{out}}
<pre>+---------------+
Line 932 ⟶ 1,051:
=={{header|Haskell}}==
<
import Control.Monad
import Control.Monad.Random
Line 1,026 ⟶ 1,145:
let v = fromIntegral density / fromIntegral densityCount ]
results = zip densities (evalRand tests g2)
mapM_ print [format ("p=" % int % "/" % int % " -> " % fixed 4) density densityCount x | (density,x) <- results]</
{{out}}
Line 1,084 ⟶ 1,203:
One approach:
<
ooze=: [ >. [ +&* [ * [: ; groups@[ <@(* * 2 < >./)/. +
percolate=: ooze/\.@|.^:2^:_@(* (1 + # {. 1:))
trial=: percolate@([ >: ]?@$0:)
simulate=: %@[ * [: +/ (2 e. {:)@trial&15 15"0@#</
Example Statistics:
<
┌────────┐
│ P THRU│
Line 1,107 ⟶ 1,226:
│0.9 1│
│ 1 1│
└────────┘</
Worked sample:
<
# # # # # # # #
# # # # # # # # # # # #
Line 1,126 ⟶ 1,245:
. . . # . # # #
. . . . . . . # # .
. . . . . . . . # # </
An [[Percolation/Site_percolation/J|explanation with examples]] would be somewhat longer than the implementation.
Line 1,132 ⟶ 1,251:
Alternative implementation (with an incompatible internal API):
<syntaxhighlight lang="j">
any =: +./
all =: *./
Line 1,175 ⟶ 1,294:
simulate =: 100&$: : ([ %~ [: +/ [: percolate"0 #) NB. return fraction of connected cases. Use: T simulate P
</syntaxhighlight>
<pre>
Line 1,239 ⟶ 1,358:
· · · · · · · · · ·
· · · · · · · · · · · ·
</pre>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.concurrent.ThreadLocalRandom;
public final class PercolationSite {
public static void main(String[] aArgs) {
final int rowCount = 15;
final int colCount = 15;
final int testCount = 1_000;
Grid grid = new Grid(rowCount, colCount, 0.5);
grid.percolate();
grid.display();
System.out.println("Proportion of " + testCount + " tests that percolate through the grid:");
for ( double probable = 0.0; probable <= 1.0; probable += 0.1 ) {
int percolationCount = 0;
for ( int test = 0; test < testCount; test++) {
Grid testGrid = new Grid(rowCount, colCount, probable);
if ( testGrid.percolate() ) {
percolationCount += 1;
}
}
double percolationProportion = (double) percolationCount / testCount;
System.out.println(String.format("%s%.1f%s%.4f", " p = ", probable, ": ", percolationProportion));
}
}
}
final class Grid {
public Grid(int aRowCount, int aColCount, double aProbability) {
createGrid(aRowCount, aColCount, aProbability);
}
public boolean percolate() {
for ( int x = 0; x < table[0].length; x++ ) {
if ( pathExists(x, 0) ) {
return true;
}
}
return false;
}
public void display() {
for ( int col = 0; col < table.length; col++ ) {
for ( int row = 0; row < table[0].length; row++ ) {
System.out.print(" " + table[col][row]);
}
System.out.println();
}
System.out.println();
}
private boolean pathExists(int aX, int aY) {
if ( aY < 0 || aX < 0 || aX >= table[0].length || table[aY][aX].compareTo(FILLED) != 0 ) {
return false;
}
table[aY][aX] = PATH;
if ( aY == table.length - 1 ) {
return true;
}
return pathExists(aX, aY + 1) || pathExists(aX + 1, aY) || pathExists(aX - 1, aY) || pathExists(aX, aY - 1);
}
private void createGrid(int aRowCount, int aColCount, double aProbability) {
table = new String[aRowCount][aColCount];
for ( int col = 0; col < aRowCount; col++ ) {
for ( int row = 0; row < aColCount; row++ ) {
table[col][row] = ( RANDOM.nextFloat(1.0F) < aProbability ) ? FILLED: EMPTY;
}
}
}
private String[][] table;
private static final String EMPTY = " ";
private static final String FILLED = ".";
private static final String PATH = "#";
private static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current();
}
</syntaxhighlight>
{{ out }}
<pre>
# . .
. . # # . .
. . . # # . . . . .
. . . # # # . . . .
. . # # . . .
. . . # # . . . . .
. . # # # # . . . .
. . # . . . . .
. . . # # . . . . . .
. # . . . .
. . # . . . .
. # # . . . . .
# . . . . . .
. . # . . . . . . .
. . # . . . . . . .
Proportion of 1000 tests that percolate through the grid:
p = 0.0: 0.0000
p = 0.1: 0.0000
p = 0.2: 0.0000
p = 0.3: 0.0000
p = 0.4: 0.0060
p = 0.5: 0.1040
p = 0.6: 0.5670
p = 0.7: 0.9480
p = 0.8: 1.0000
p = 0.9: 1.0000
p = 1.0: 1.0000
</pre>
=={{header|Julia}}==
{{trans|Python}}
<
newgrid(p::Float64, M::Int=15, N::Int=15) = rand(Bernoulli(p), M, N)
Line 1,317 ⟶ 1,554:
for (pi, fi) in zip(p, f)
@printf("p = %.1f ⇛ f = %.3f\n", pi, fi)
end</
{{out}}
Line 1,355 ⟶ 1,592:
=={{header|Kotlin}}==
{{trans|C}}
<
import java.util.Random
Line 1,421 ⟶ 1,658:
println("p = %.1f: %.4f".format(p, cnt / 10000.0))
}
}</
Sample output:
Line 1,458 ⟶ 1,695:
=={{header|Nim}}==
{{trans|Go}}
<
type Grid = seq[string] # Row first, i.e. [y][x].
Line 1,535 ⟶ 1,772:
if grid.percolate(): inc count
echo &"p = {p:.2f}: {count / T:.4f}"
p += ΔP</
{{out}}
Line 1,570 ⟶ 1,807:
=={{header|Perl}}==
{{trans|Raku}}
<
my $water = '+';
my $pore = ' ';
Line 1,642 ⟶ 1,879:
}
print "$_\n" for @table;</
{{out}}
<pre>Sample percolation at 0.65
Line 1,677 ⟶ 1,914:
=={{header|Phix}}==
{{trans|C}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">grid</span>
Line 1,726 ⟶ 1,963:
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</
{{out}}
<pre>
Line 1,761 ⟶ 1,998:
=={{header|Python}}==
<
import string
from pprint import pprint as pp
Line 1,831 ⟶ 2,068:
print('\n p: Fraction of %i tries that percolate through\n' % t )
pp({p:c/float(t) for p, c in pcount.items()})</
{{out}}
Line 1,872 ⟶ 2,109:
=={{header|Racket}}==
<
(require racket/require (only-in racket/fixnum for*/fxvector))
(require (filtered-in (lambda (name) (regexp-replace #rx"unsafe-" name ""))
Line 1,952 ⟶ 2,189:
((i (in-range (t))) #:when (perc-15x15-grid?! (make-15x15-grid p))) 1))
(define proportion-percolated (/ n-percolated-grids (t)))
(printf "p=~a\t->\t~a~%" p (real->decimal-string proportion-percolated 4)))</
{{out}}
Line 1,988 ⟶ 2,225:
{{works with|Rakudo|2017.02}}
<syntaxhighlight lang="raku"
my $water = '+';
my $pore = ' ';
Line 2,051 ⟶ 2,288:
[$x, $y]
}
}</
{{out}}
<pre>Sample percolation at .6
Line 2,088 ⟶ 2,325:
=={{header|Sidef}}==
{{trans|Raku}}
<
has block = '▒'
Line 2,153 ⟶ 2,390:
for p in (0.1..1 `by` 0.1) {
printf("p = %0.1f: %0.3f\n", p, tests.of { obj.percolate(p) }.sum / tests)
}</
{{out}}
<pre>
Line 2,190 ⟶ 2,427:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<
oo::class create SitePercolation {
Line 2,266 ⟶ 2,503:
puts [format "p=%.2f: %2.1f%%" $p [expr {$tot*100./$tries}]]
}
}}</
{{out}}
<pre>
Line 2,305 ⟶ 2,542:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var rand = Random.new()
Line 2,369 ⟶ 2,606:
}
Fmt.print("p = $.1f: $.4f", p, cnt / 10000)
}</
{{out}}
Line 2,407 ⟶ 2,644:
=={{header|zkl}}==
{{trans|C}}
<
grid:=Data((m+1)*(n+1)); // first row and right edges are buffers
grid.write(" "*m); grid.write("\r");
Line 2,435 ⟶ 2,672:
cnt:=0.0; do(10000){ cnt+=percolate(makeGrid(15,15,p),15); }
"p=%.1f: %.4f".fmt(p, cnt/10000).println();
}</
{{out}}
<pre>
| |||