Rosetta Code

Percolation/Bond percolation: Difference between revisions

Page Discussion

Percolation/Bond percolation (view source)

Revision as of 09:11, 7 April 2024

54,245 bytes added ,  1 month ago
m
→‎{{header|11l}}: X.throw
m (→‎{{header|Perl 6}}: Remove some superstitious parenthesis, minor code tweaks)
(25 intermediate revisions by 12 users not shown)
Line 23:
Show all output on this page.
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">UInt32 seed = 0
F nonrandom()
:seed = 1664525 * :seed + 1013904223
R Int(:seed >> 16) / Float(FF'FF)
 
T Grid
[[Int]] cell, hwall, vwall
F (cell, hwall, vwall)
.cell = cell
.hwall = hwall
.vwall = vwall
 
V (M, nn, t) = (10, 10, 100)
 
T PercolatedException
(Int, Int) t
F (t)
.t = t
 
V HVF = ([‘ .’, ‘ _’], [‘:’, ‘|’], [‘ ’, ‘#’])
 
F newgrid(p)
V hwall = (0 .. :nn).map(n -> (0 .< :M).map(m -> Int(nonrandom() < @@p)))
V vwall = (0 .< :nn).map(n -> (0 .. :M).map(m -> (I m C (0, :M) {1} E Int(nonrandom() < @@p))))
V cell = (0 .< :nn).map(n -> (0 .< :M).map(m -> 0))
R Grid(cell, hwall, vwall)
 
F pgrid(grid, percolated)
V (cell, hwall, vwall) = grid
V (h, v, f) = :HVF
L(n) 0 .< :nn
print(‘ ’(0 .< :M).map(m -> @h[@hwall[@n][m]]).join(‘’))
print(‘#.) ’.format(n % 10)‘’(0 .. :M).map(m -> @v[@vwall[@n][m]]‘’@f[I m < :M {@cell[@n][m]} E 0]).join(‘’)[0 .< (len)-1])
V n = :nn
print(‘ ’(0 .< :M).map(m -> @h[@hwall[@n][m]]).join(‘’))
I percolated != (-1, -1)
V where = percolated[0]
print(‘!) ’(‘ ’ * where)‘ ’f[1])
 
F flood_fill(m, n, &cell, hwall, vwall) -> N
cell[n][m] = 1
I n < :nn - 1 & !hwall[n + 1][m] & !cell[n + 1][m]
flood_fill(m, n + 1, &cell, hwall, vwall)
E I n == :nn - 1 & !hwall[n + 1][m]
X.throw PercolatedException((m, n + 1))
I m & !vwall[n][m] & !cell[n][m - 1]
flood_fill(m - 1, n, &cell, hwall, vwall)
I m < :M - 1 & !vwall[n][m + 1] & !cell[n][m + 1]
flood_fill(m + 1, n, &cell, hwall, vwall)
I n != 0 & !hwall[n][m] & !cell[n - 1][m]
flood_fill(m, n - 1, &cell, hwall, vwall)
 
F pour_on_top(Grid &grid) -> (Int, Int)?
V n = 0
X.try
L(m) 0 .< :M
I grid.hwall[n][m] == 0
flood_fill(m, n, &grid.cell, grid.hwall, grid.vwall)
X.catch PercolatedException ex
R ex.t
R N
 
V sample_printed = 0B
[Float = Int] pcount
L(p10) 11
V p = (10 - p10) / 10.0
pcount[p] = 0
L(tries) 0 .< t
V grid = newgrid(p)
(Int, Int)? percolated = pour_on_top(&grid)
I percolated != N
pcount[p]++
I !sample_printed
print("\nSample percolating #. x #. grid".format(M, nn))
pgrid(grid, percolated ? (-1, -1))
sample_printed = 1B
print("\n p: Fraction of #. tries that percolate through".format(t))
 
L(p, c) sorted(pcount.items())
print(‘#.1: #.’.format(p, c / Float(t)))</syntaxhighlight>
 
{{out}}
<pre>
 
Sample percolating 10 x 10 grid
. _ _ _ . _ . _ _ _
0) |#:#:#| |#:#|#:#:#| |
. _ . _ _ _ _ _ . _
1) |#|#:#| | | | |#:#:#|
_ _ . _ . _ _ _ _ .
2) | |#:#| : : : | | |#|
. _ _ . _ _ _ _ . .
3) | | | : | : | | | :#|
_ . . _ _ _ . . _ .
4) | | : : | | |#:#| |#|
. _ _ _ _ _ . . . .
5) | : | | | : |#|#:#:#|
_ _ _ _ _ _ . _ _ _
6) | | | | | : :#: : | |
_ _ _ _ . . . . . .
7) | | | | | | |#:#:#| |
_ _ . . . _ _ _ . _
8) | : | | | | : | |#: |
. . . . _ . _ _ . .
9) | | | : | | | : |#| |
_ . _ _ . _ . . . .
!) #
 
p: Fraction of 100 tries that percolate through
0.0: 1
0.1: 1
0.2: 1
0.3: 0.99
0.4: 0.89
0.5: 0.49
0.6: 0.06
0.7: 0
0.8: 0
0.9: 0
1.0: 0
</pre>
 
=={{header|C}}==
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 123 ⟶ 249:
free(start);
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 163 ⟶ 289:
=={{header|C++}}==
{{trans|D}}
<langsyntaxhighlight lang="cpp">#include <cstdlib>
#include <cstring>
#include <iostream>
Line 265 ⟶ 391:
 
return EXIT_SUCCESS;
}</langsyntaxhighlight>
 
=={{header|D}}==
{{trans|C}}
<langsyntaxhighlight lang="d">import std.stdio, std.random, std.array, std.range, std.algorithm;
 
struct Grid {
Line 374 ⟶ 500:
probability, nPercolated / double(nTries));
}
}</langsyntaxhighlight>
{{out}}
<pre>+-+-+-+-+-+-+-+-+-+-+
Line 414 ⟶ 540:
=={{header|Go}}==
{{trans|C}}<!-- sort of ended up like the C version, not an actual translation -->
<langsyntaxhighlight lang="go">package main
 
import (
"bytes"
"fmt"
"math/rand"
"strings"
"time"
)
Line 483 ⟶ 609:
 
func (g *grid) String() string {
var buf bytesstrings.BufferBuilder
// Don't really need to call Grow but it helps avoid multiple
// reallocations if the size is large.
Line 545 ⟶ 671:
}
return false
}</langsyntaxhighlight>
{{out}}
<pre>
Line 581 ⟶ 707:
</pre>
 
=={{header|Perl 6Haskell}}==
<syntaxhighlight lang="haskell">{-# LANGUAGE OverloadedStrings #-}
{{works with|Rakudo|2017.02}}
import Control.Monad
Starts "filling" from the top left. Fluid flow favours directions in Down, Left, Right, Up order. I interpreted p to be porosity, so small p mean low permeability, large p means high permeability.
import Control.Monad.Random
import Data.Array.Unboxed
import Data.List
import Formatting
data Field = Field { f :: UArray (Int, Int) Char
, hWall :: UArray (Int, Int) Bool
, vWall :: UArray (Int, Int) Bool
}
-- Start percolating some seepage through a field.
-- Recurse to continue percolation with new seepage.
percolateR :: [(Int, Int)] -> Field -> (Field, [(Int,Int)])
percolateR [] (Field f h v) = (Field f h v, [])
percolateR seep (Field f h v) =
let ((xLo,yLo),(xHi,yHi)) = bounds f
validSeep = filter (\p@(x,y) -> x >= xLo
&& x <= xHi
&& y >= yLo
&& y <= yHi
&& f!p == ' ') $ nub $ sort seep
 
north (x,y) = if v ! (x ,y ) then [] else [(x ,y-1)]
<lang perl6>my @bond;
south (x,y) = if v ! (x ,y+1) then [] else [(x ,y+1)]
my $grid = 10;
west (x,y) = if h ! (x ,y ) then [] else [(x-1,y )]
my $geom = $grid - 1;
east (x,y) = if h ! (x+1,y ) then [] else [(x+1,y )]
my $water = '▒';
neighbors (x,y) = north(x,y) ++ south(x,y) ++ west(x,y) ++ east(x,y)
 
in percolateR
enum Direction <DeadEnd Up Right Down Left>;
(concatMap neighbors validSeep)
(Field (f // map (\p -> (p,'.')) validSeep) h v)
-- Percolate a field; Return the percolated field.
percolate :: Field -> Field
percolate start@(Field f _ _) =
let ((_,_),(xHi,_)) = bounds f
(final, _) = percolateR [(x,0) | x <- [0..xHi]] start
in final
-- Generate a random field.
initField :: Int -> Int -> Double -> Rand StdGen Field
initField width height threshold = do
let f = listArray ((0,0), (width-1, height-1)) $ repeat ' '
 
hrnd <- fmap (<threshold) <$> getRandoms
say 'Sample percolation at .6';
let h0 = listArray ((0,0),(width, height-1)) hrnd
percolate .6;
h1 = h0 // [((0,y), True) | y <- [0..height-1]] -- close left
.join.say for @bond;
h2 = h1 // [((width,y), True) | y <- [0..height-1]] -- close right
say "\n";
 
vrnd <- fmap (<threshold) <$> getRandoms
my $tests = 100;
let v0 = listArray ((0,0),(width-1, height)) vrnd
say "Doing $tests trials at each porosity:";
v1 = v0 // [((x,0), True) | x <- [0..width-1]] -- close top
for .1, .2 ... 1 -> $p {
 
printf "p = %0.1f: %0.2f\n", $p, (sum percolate($p) xx $tests) / $tests
return $ Field f h2 v1
-- Assess whether or not percolation reached bottom of field.
leaks :: Field -> [Bool]
leaks (Field f _ v) =
let ((xLo,_),(xHi,yHi)) = bounds f
in [f!(x,yHi)=='.' && not (v!(x,yHi+1)) | x <- [xLo..xHi]]
 
-- Run test once; Return bool indicating success or failure.
oneTest :: Int -> Int -> Double -> Rand StdGen Bool
oneTest width height threshold =
or.leaks.percolate <$> initField width height threshold
-- Run test multple times; Return the number of tests that pass.
multiTest :: Int -> Int -> Int -> Double -> Rand StdGen Double
multiTest testCount width height threshold = do
results <- replicateM testCount $ oneTest width height threshold
let leakyCount = length $ filter id results
return $ fromIntegral leakyCount / fromIntegral testCount
 
-- Helper function for display
alternate :: [a] -> [a] -> [a]
alternate [] _ = []
alternate (a:as) bs = a : alternate bs as
-- Display a field with walls and leaks.
showField :: Field -> IO ()
showField field@(Field a h v) = do
let ((xLo,yLo),(xHi,yHi)) = bounds a
fLines = [ [ a!(x,y) | x <- [xLo..xHi]] | y <- [yLo..yHi]]
hLines = [ [ if h!(x,y) then '|' else ' ' | x <- [xLo..xHi+1]] | y <- [yLo..yHi]]
vLines = [ [ if v!(x,y) then '-' else ' ' | x <- [xLo..xHi]] | y <- [yLo..yHi+1]]
lattice = [ [ '+' | x <- [xLo..xHi+1]] | y <- [yLo..yHi+1]]
 
hDrawn = zipWith alternate hLines fLines
vDrawn = zipWith alternate lattice vLines
mapM_ putStrLn $ alternate vDrawn hDrawn
 
let leakLine = [ if l then '.' else ' ' | l <- leaks field]
putStrLn $ alternate (repeat ' ') leakLine
 
main :: IO ()
main = do
g <- getStdGen
let threshold = 0.45
(startField, g2) = runRand (initField 10 10 threshold) g
 
putStrLn ("Unpercolated field with " ++ show threshold ++ " threshold.")
putStrLn ""
showField startField
putStrLn ""
putStrLn "Same field after percolation."
putStrLn ""
showField $ percolate startField
 
let testCount = 10000
densityCount = 10
putStrLn ""
putStrLn ("Results of running percolation test " ++ show testCount ++ " times with thresholds ranging from 0/" ++ show densityCount ++ " to " ++ show densityCount ++ "/" ++ show densityCount ++ " .")
let densities = [0..densityCount]
let tests = sequence [multiTest testCount 10 10 v
| density <- densities,
let v = fromIntegral density / fromIntegral densityCount ]
let results = zip densities (evalRand tests g2)
mapM_ print [format ("p=" % int % "/" % int % " -> " % fixed 4) density densityCount x | (density,x) <- results]</syntaxhighlight>
 
{{out}}
<pre>
Unpercolated field with 0.45 threshold.
 
+-+-+-+-+-+-+-+-+-+-+
| | | | | | | |
+-+-+ +-+ + + + + +-+
| | | | | | | |
+ + +-+-+ + +-+-+ + +
| | | |
+ +-+-+-+ +-+-+ +-+ +
| | | | | |
+ +-+ + + +-+-+ + +-+
| | | | | |
+-+-+ + + + + +-+ + +
| | | | | | | |
+-+ + + + + + + +-+-+
| | | | |
+ + + + + +-+ +-+ + +
| | | | | | | | |
+ + + +-+-+-+-+-+ + +
| | | | |
+ +-+ +-+ +-+ + + +-+
| | | | | |
+ + + + +-+ +-+-+-+ +
 
Same field after percolation.
 
+-+-+-+-+-+-+-+-+-+-+
|. . . .|.|.|.|.|.|.|
+-+-+ +-+ + + + + +-+
| |.|. . . .|.|.|.|.|
+ + +-+-+ + +-+-+ + +
| |. . . . .|. . . .|
+ +-+-+-+ +-+-+ +-+ +
| |. . .|.|. . . .|.|
+ +-+ + + +-+-+ + +-+
| |. . .|. . . .|.|.|
+-+-+ + + + + +-+ + +
| |.|. .|.|.|.|. . .|
+-+ + + + + + + +-+-+
|. . . . .|. .|. .|.|
+ + + + + +-+ +-+ + +
|.|.|.|.|. . .| |.|.|
+ + + +-+-+-+-+-+ + +
|.|. . . .|. . .|. .|
+ +-+ +-+ +-+ + + +-+
|.| |.|. . . . . .| |
+ + + + +-+ +-+-+-+ +
. . . .
 
Results of running percolation test 10000 times with thresholds ranging from 0/10 to 10/10 .
"p=0/10 -> 1.0000"
"p=1/10 -> 1.0000"
"p=2/10 -> 1.0000"
"p=3/10 -> 0.9969"
"p=4/10 -> 0.9171"
"p=5/10 -> 0.5026"
"p=6/10 -> 0.0901"
"p=7/10 -> 0.0025"
"p=8/10 -> 0.0000"
"p=9/10 -> 0.0000"
"p=10/10 -> 0.0000"
</pre>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;
 
public final class PercolationBond {
 
public static void main(String[] aArgs) {
System.out.println("Sample percolation with a " + COL_COUNT + " x " + ROW_COUNT + " grid:");
makeGrid(0.5);
percolate();
showGrid();
System.out.println("Using 10,000 repetitions for each probability p:");
for ( int p = 1; p <= 9; p++ ) {
int percolationCount = 0;
double probability = p / 10.0;
for ( int i = 0; i < 10_000; i++ ) {
makeGrid(probability);
if ( percolate() ) {
percolationCount += 1;
}
}
final double percolationProportion = (double) percolationCount / 10_000;
System.out.println(String.format("%s%.1f%s%.4f", "p = ", probability, ": ", percolationProportion));
}
}
private static void makeGrid(double aProbability) {
Arrays.fill(grid, 0);
for ( int i = 0; i < COL_COUNT; i++ ) {
grid[i] = LOWER_WALL | RIGHT_WALL;
}
 
endOfRow = COL_COUNT;
for ( int i = 0; i < ROW_COUNT; i++ ) {
for ( int j = COL_COUNT - 1; j >= 1; j-- ) {
final boolean chance1 = RANDOM.nextDouble() < aProbability;
final boolean chance2 = RANDOM.nextDouble() < aProbability;
grid[endOfRow++] = ( chance1 ? LOWER_WALL : 0 ) | ( chance2 ? RIGHT_WALL : 0 );
}
final boolean chance3 = RANDOM.nextDouble() < aProbability;
grid[endOfRow++] = RIGHT_WALL | ( chance3 ? LOWER_WALL : 0 );
}
}
private static void showGrid() {
for ( int j = 0; j < COL_COUNT; j++ ) {
System.out.print("+--");
}
System.out.println("+");
for ( int i = 0; i < ROW_COUNT; i++ ) {
System.out.print("|");
for ( int j = 0; j < COL_COUNT; j++ ) {
System.out.print( ( ( grid[i * COL_COUNT + j + COL_COUNT] & FILL ) != 0 ) ? "[]" : " " );
System.out.print( ( ( grid[i * COL_COUNT + j + COL_COUNT] & RIGHT_WALL ) != 0 ) ? "|" : " " );
}
System.out.println();
for ( int j = 0; j < COL_COUNT; j++ ) {
System.out.print( ( ( grid[i * COL_COUNT + j + COL_COUNT] & LOWER_WALL) != 0 ) ? "+--" : "+ " );
}
System.out.println("+");
}
System.out.print(" ");
for ( int j = 0; j < COL_COUNT; j++ ) {
System.out.print( ( ( grid[ROW_COUNT * COL_COUNT + j + COL_COUNT] & FILL ) != 0 ) ? "[]" : " " );
System.out.print( ( ( grid[ROW_COUNT * COL_COUNT + j + COL_COUNT] & RIGHT_WALL ) != 0 ) ? "|" : " " );
}
System.out.println(System.lineSeparator());
}
private static boolean fill(int aGridIndex) {
if ( ( grid[aGridIndex] & FILL ) != 0 ) {
return false;
}
grid[aGridIndex] |= FILL;
if ( aGridIndex >= endOfRow ) {
return true;
}
return ( ( ( grid[aGridIndex] & LOWER_WALL ) == 0 ) && fill(aGridIndex + COL_COUNT) ) ||
( ( ( grid[aGridIndex] & RIGHT_WALL ) == 0 ) && fill(aGridIndex + 1) ) ||
( ( ( grid[aGridIndex - 1] & RIGHT_WALL ) == 0 ) && fill(aGridIndex - 1) ) ||
( ( ( grid[aGridIndex - COL_COUNT] & LOWER_WALL ) == 0 ) && fill(aGridIndex - COL_COUNT) );
}
 
private static boolean percolate() {
int i = 0;
while ( i < COL_COUNT && ! fill(COL_COUNT + i) ) {
i++;
}
return i < COL_COUNT;
}
private static final int ROW_COUNT = 10;
private static final int COL_COUNT = 10;
private static int endOfRow = COL_COUNT;
private static int[] grid = new int[COL_COUNT * ( ROW_COUNT + 2 )];
 
private static final int FILL = 1;
private static final int RIGHT_WALL = 2;
private static final int LOWER_WALL = 4;
 
private static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current();
}
</syntaxhighlight>
{{ out }}
<pre>
Sample percolation with a 10 x 10 grid:
+--+--+--+--+--+--+--+--+--+--+
|[] []|[]| | | |
+--+--+ +--+--+ +--+ +--+--+
| | |[] | | |
+ + + +--+ + +--+ + + +
| | []| | | |
+ +--+ +--+--+ + +--+--+--+
| |[] | | |
+ +--+ +--+--+--+ +--+--+--+
| | []| | | | | | |
+--+ + + +--+--+ + +--+ +
| |[] | | | | |
+--+ + + + +--+--+ + +--+
| [] []| | | |
+ + +--+--+ +--+--+--+ +--+
| |[] | | | | |
+ + +--+ +--+ + +--+ + +
| []| | | | | |
+ + +--+ +--+--+--+--+ + +
| |[] [] | |
+ +--+ +--+--+ +--+ +--+--+
[]
 
Using 10,000 repetitions for each probability p:
sub percolate ( $prob ) {
p = 0.1: 1.0000
generate $prob;
p = 0.2: 0.9999
my @stack;
p = 0.3: 0.9973
my $current = [1;0];
p = 0.4: 0.9223
$current.&fill;
p = 0.5: 0.5011
p = 0.6: 0.0872
p = 0.7: 0.0022
p = 0.8: 0.0000
p = 0.9: 0.0000
</pre>
 
=={{header|Julia}}==
loop {
{{trans|Python}}
if my $dir = direction( $current ) {
<syntaxhighlight lang="julia">using Printf, Distributions
@stack.push: $current;
 
$current = move $dir, $current
struct Grid
cells::BitArray{2}
hwall::BitArray{2}
vwall::BitArray{2}
end
function Grid(p::AbstractFloat, m::Integer=10, n::Integer=10)
cells = fill(false, m, n)
hwall = rand(Bernoulli(p), m + 1, n)
vwall = rand(Bernoulli(p), m, n + 1)
vwall[:, 1] = true
vwall[:, end] = true
return Grid(cells, hwall, vwall)
end
 
function Base.show(io::IO, g::Grid)
H = (" .", " _")
V = (":", "|")
C = (" ", "#")
ind = findfirst(g.cells[end, :] .& .!g.hwall[end, :])
percolated = !iszero(ind)
println(io, "$(size(g.cells, 1))×$(size(g.cells, 2)) $(percolated ? "Percolated" : "Not percolated") grid")
for r in 1:size(g.cells, 1)
println(io, " ", join(H[w+1] for w in g.hwall[r, :]))
println(io, " $(r % 10)) ", join(V[w+1] * C[c+1] for (w, c) in zip(g.vwall[r, :], g.cells[r, :])))
end
println(io, " ", join(H[w+1] for w in g.hwall[end, :]))
if percolated
println(io, " !) ", " " ^ (ind - 1), '#')
end
end
 
function floodfill!(m::Integer, n::Integer, cells::AbstractMatrix{<:Integer},
hwall::AbstractMatrix{<:Integer}, vwall::AbstractMatrix{<:Integer})
# fill cells
cells[m, n] = true
percolated = false
# bottom
if m < size(cells, 1) && !hwall[m+1, n] && !cells[m+1, n]
percolated = percolated || floodfill!(m + 1, n, cells, hwall, vwall)
# The Bottom
elseif m == size(cells, 1) && !hwall[m+1, n]
return true
end
# left
if n > 1 && !vwall[m, n] && !cells[m, n-1]
percolated = percolated || floodfill!(m, n - 1, cells, hwall, vwall)
end
# right
if n < size(cells, 2) && !vwall[m, n+1] && !cells[m, n+1]
percolated = percolated || floodfill!(m, n + 1, cells, hwall, vwall)
end
# top
if m > 1 && !hwall[m, n] && !cells[m-1, n]
percolated = percolated || floodfill!(m - 1, n, cells, hwall, vwall)
end
return percolated
end
function pourontop!(g::Grid)
m, n = 1, 1
percolated = false
while !percolated && n ≤ size(g.cells, 2)
percolated = !g.hwall[m, n] && floodfill!(m, n, g.cells, g.hwall, g.vwall)
n += 1
end
return percolated
end
 
function main(probs, nrep::Integer=1000)
sampleprinted = false
pcount = zeros(Int, size(probs))
for (i, p) in enumerate(probs), _ in 1:nrep
g = Grid(p)
percolated = pourontop!(g)
if percolated
pcount[i] += 1
if !sampleprinted
println(g)
sampleprinted = true
end
end
end
return pcount ./ nrep
end
 
probs = collect(10:-1:0) ./ 10
percprobs = main(probs)
 
println("Fraction of 1000 tries that percolate through:")
for (pr, pp) in zip(probs, percprobs)
@printf("\tp = %.3f ⇒ freq. = %5.3f\n", pr, pp)
end</syntaxhighlight>
 
{{out}}
<pre>10×10 Percolated grid
_ . . _ _ _ . _ . .
1) | |#:#| | : | : | :
_ _ . _ _ _ _ _ . _
2) | | |#| : : | : | |
_ _ . _ _ _ _ _ _ .
3) | | |#:#| : | : | :
. _ _ . _ _ _ . _ _
4) | | | :#: : | | | |
. _ _ . _ _ _ . _ _
5) | | : |#| | : | | :
_ . _ . _ _ . . . _
6) | | | |#| | | | | |
. . _ . _ _ _ . . .
7) | |#:#:#: | | : | |
_ . . _ . . . . _ _
8) | |#|#| | | : | | |
_ . . _ _ _ . _ _ _
9) |#:#|#| : : | : | |
. _ _ _ _ . _ _ _ .
0) |#: | : | | | : : |
. . _ _ _ _ . _ _ _
!) #
 
Fraction of 1000 tries that percolate through:
p = 1.000 ⇒ freq. = 0.000
p = 0.900 ⇒ freq. = 0.000
p = 0.800 ⇒ freq. = 0.000
p = 0.700 ⇒ freq. = 0.001
p = 0.600 ⇒ freq. = 0.064
p = 0.500 ⇒ freq. = 0.470
p = 0.400 ⇒ freq. = 0.895
p = 0.300 ⇒ freq. = 0.997
p = 0.200 ⇒ freq. = 1.000
p = 0.100 ⇒ freq. = 1.000
p = 0.000 ⇒ freq. = 1.000</pre>
 
=={{header|Kotlin}}==
{{trans|C}}
<syntaxhighlight lang="scala">// version 1.2.10
 
import java.util.Random
 
val rand = Random()
const val RAND_MAX = 32767
 
// cell states
const val FILL = 1
const val RWALL = 2 // right wall
const val BWALL = 4 // bottom wall
 
val x = 10
val y = 10
var grid = IntArray(x * (y + 2))
var cells = 0
var end = 0
var m = 0
var n = 0
 
fun makeGrid(p: Double) {
val thresh = (p * RAND_MAX).toInt()
m = x
n = y
grid.fill(0) // clears grid
for (i in 0 until m) grid[i] = BWALL or RWALL
cells = m
end = m
for (i in 0 until y) {
for (j in x - 1 downTo 1) {
val r1 = rand.nextInt(RAND_MAX + 1)
val r2 = rand.nextInt(RAND_MAX + 1)
grid[end++] = (if (r1 < thresh) BWALL else 0) or
(if (r2 < thresh) RWALL else 0)
}
elseval {r3 = rand.nextInt(RAND_MAX + 1)
grid[end++] = RWALL or return(if 0(r3 unless< @stack;thresh) BWALL else 0)
}
$current = @stack.pop
}
 
fun showGrid() {
for (j in 0 until m) print("+--")
println("+")
 
for (i in 0..n) {
print(if (i == n) " " else "|")
for (j in 0 until m) {
print(if ((grid[i * m + j + cells] and FILL) != 0) "[]" else " ")
print(if ((grid[i * m + j + cells] and RWALL) != 0) "|" else " ")
}
println()
if (i == n) return
for (j in 0 until m) {
print(if ((grid[i * m + j + cells] and BWALL) != 0) "+--" else "+ ")
}
println("+")
return 1 if $current[1] == +@bond - 1
}
}
 
fun fill(p: Int): Boolean {
sub direction( [$x, $y] ) {
if ((grid[p] and FILL) != 0) return false
( Down if @bond[$y + 1][$x].contains: ' ' ) ||
grid[p] = grid[p] or FILL
( Left if @bond[$y][$x - 1].contains: ' ' ) ||
if (p >= end) return true // success: reached bottom row
( Right if @bond[$y][$x + 1].contains: ' ' ) ||
return (((grid[p + 0] and BWALL) == 0) && fill(p + m)) ||
( Up if @bond[$y - 1][$x].defined && @bond[$y - 1][$x].contains: ' ' ) ||
(((grid[p + 0] and RWALL) == 0) && fill(p + 1)) ||
DeadEnd
(((grid[p - 1] and RWALL) == 0) && fill(p - 1)) ||
(((grid[p - m] and BWALL) == 0) && fill(p - m))
}
 
fun percolate(): Boolean {
var i = 0
while (i < m && !fill(cells + i)) i++
return i < m
}
 
fun main(args: Array<String>) {
makeGrid(0.5)
percolate()
showGrid()
 
println("\nrunning $x x $y grids 10,000 times for each p:")
for (p in 1..9) {
var cnt = 0
val pp = p / 10.0
for (i in 0 until 10_000) {
makeGrid(pp)
if (percolate()) cnt++
}
println("p = %3g: %.4f".format(pp, cnt.toDouble() / 10_000))
}
}</syntaxhighlight>
 
Sample output:
sub move ( $dir, @cur ) {
<pre>
my ( $x, $y ) = @cur;
+--+--+--+--+--+--+--+--+--+--+
given $dir {
|[]|[] [] [] [] []| | | | |
when Up { [$x,--$y].&fill xx 2 }
+--+--+--+--+--+ +--+ + + +
when Down { [$x,++$y].&fill xx 2 }
| | | | []| when Left { [--$x,$y].&fill xx 2 }|
+--+--+--+--+--+ + +--+ + +
when Right { [++$x,$y].&fill xx 2 }
| | | | |[] []| |
+ + + + + +--+--+--+--+--+
| | | [] [] []| | |
+--+--+ + +--+--+--+--+--+ +
| | |[] []| | | |
+--+--+ + + + +--+ +--+--+
| | | |[]|[]| | | |
+--+ +--+--+ +--+--+ + + +
| | | []| | | | |
+--+ + + + +--+--+ + + +
| | |[] []| | |
+ +--+--+ +--+ +--+ + +--+
| | [] | | | |
+ + +--+ + +--+--+--+--+ +
| [] | | | |
+ +--+--+ + +--+--+ +--+ +
[]
 
running 10 x 10 grids 10,000 times for each p:
p = 0.100000: 1.0000
p = 0.200000: 1.0000
p = 0.300000: 0.9968
p = 0.400000: 0.9184
p = 0.500000: 0.5047
p = 0.600000: 0.0828
p = 0.700000: 0.0034
p = 0.800000: 0.0000
p = 0.900000: 0.0000
</pre>
 
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim">import random, sequtils, strformat, tables
 
type
 
Cell = object
full: bool
right, down: bool # True if open to the right (x+1) or down (y+1).
 
Grid = seq[seq[Cell]] # Row first, i.e. [y][x].
 
 
proc newGrid(p: float; xsize, ysize: Positive): Grid =
 
result = newSeqWith(ysize, newSeq[Cell](xsize))
for row in result.mitems:
for x in 0..(xsize - 2):
if rand(1.0) > p: row[x].right = true
if rand(1.0) > p: row[x].down = true
if rand(1.0) > p: row[xsize - 1].down = true
 
 
const
Full = {false: " ", true: "()"}.toTable
HOpen = {false: "--", true: " "}.toTable
VOpen = {false: "|", true: " "}.toTable
 
proc `$`(grid: Grid): string =
 
# Preallocate result to avoid multiple reallocations.
result = newStringOfCap((grid.len + 1) * grid[0].len * 7)
 
for _ in 0..grid[0].high:
result.add '+'
result.add HOpen[false]
result.add "+\n"
 
for row in grid:
result.add VOpen[false]
for cell in row:
result.add Full[cell.full]
result.add VOpen[cell.right]
result.add '\n'
for cell in row:
result.add '+'
result.add HOpen[cell.down]
result.add "+\n"
 
for cell in grid[^1]:
result.add ' '
result.add Full[cell.down and cell.full]
 
 
proc fill(grid: var Grid; x, y: Natural): bool =
 
if y >= grid.len: return true # Out the bottom.
if grid[y][x].full: return false # Already filled.
grid[y][x].full = true
 
if grid[y][x].down and grid.fill(x, y + 1): return true
if grid[y][x].right and grid.fill(x + 1, y): return true
if x > 0 and grid[y][x - 1].right and grid.fill(x - 1, y): return true
if y > 0 and grid[y - 1][x].down and grid.fill(x, y - 1): return true
 
 
proc percolate(grid: var Grid): bool =
for x in 0..grid[0].high:
if grid.fill(x, 0): return true
 
 
const
M = 10
N = 10
T = 1000
MinP = 0.1
MaxP = 0.99
ΔP = 0.1
 
# Purposely don't seed for a repeatable example grid.
var grid = newGrid(0.4, M, N)
discard grid.percolate()
echo grid
echo ""
 
randomize()
var p = MinP
while p < MaxP:
var count = 0
for _ in 1..T:
var grid = newGrid(p, M, N)
if grid.percolate(): inc count
echo &"p = {p:.2f}: {count / T:.3f}"
p += ΔP</syntaxhighlight>
 
{{out}}
<pre>+--+--+--+--+--+--+--+--+--+--+
|()|()|() () () () ()|()|() |
+ + +--+--+ + + +--+ +--+
|() ()| |() () ()|() ()|() |
+ +--+--+ + +--+ +--+ +--+
|() ()| |() ()|() ()| () |
+ + + +--+--+--+ +--+ +--+
|() ()| |() ()| () |
+ +--+--+--+ +--+--+--+ + +
|()| | ()| |
+--+ + +--+ + +--+--+ + +
| | | () ()| |
+--+--+ +--+ + + + +--+ +
| | |()| |
+--+--+--+ + + + + + +--+
| | |() () ()| |
+ +--+--+ + + +--+ + + +
| | () ()|()|()| | |
+--+ +--+ + +--+ + +--+ +
| | () |() ()| |
+ + +--+--+ + +--+--+ +--+
()
 
p = 0.10: 1.000
p = 0.20: 0.999
p = 0.30: 0.996
p = 0.40: 0.905
p = 0.50: 0.497
p = 0.60: 0.077
p = 0.70: 0.004
p = 0.80: 0.000
p = 0.90: 0.000</pre>
 
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">my @bond;
my $grid = 10;
my $water = '▒';
$D{$_} = $i++ for qw<DeadEnd Up Right Down Left>;
 
sub percolate {
generate(shift || 0.6);
fill(my $x = 1,my $y = 0);
my @stack;
 
while () {
if (my $dir = direction($x,$y)) {
push @stack, [$x,$y];
($x,$y) = move($dir, $x, $y)
} else {
return 0 unless @stack;
($x,$y) = @{pop @stack}
}
[$x,return 1 if $y] == $#bond;
}
}
 
sub direction {
sub fill ( [$x, $y] ) { @bond[$y;$x].=subst(' ', $water, :g) }
my($x, $y) = @_;
return $D{Down} if $bond[$y+1][$x ] =~ / /;
return $D{Left} if $bond[$y ][$x-1] =~ / /;
return $D{Right} if $bond[$y ][$x+1] =~ / /;
return $D{Up} if defined $bond[$y-1][$x ] && $bond[$y-1][$x] =~ / /;
return $D{DeadEnd}
}
 
sub generate ( $prob = .5 )move {
my($dir,$x,$y) = @_;
fill( $x,--$y), fill( $x,--$y) if $dir == $D{Up};
fill( $x,++$y), fill( $x,++$y) if $dir == $D{Down};
fill(--$x, $y), fill(--$x, $y) if $dir == $D{Left};
fill(++$x, $y), fill(++$x, $y) if $dir == $D{Right};
$x, $y
}
 
sub fill {
my($x, $y) = @_;
$bond[$y][$x] =~ s/ /$water/g
}
 
sub generate {
our($prob) = shift || 0.5;
@bond = ();
myour $sp = ' ';
appendpush @bond, [flat '│', ($sp, ' ') xxx ($geomgrid-1), $sp, '│'],
[flat '├', hx(h(), '┬') xx $geom, h(), '┤'];
appendpush @bond, [flat '│', vx($sp, v()) xx $geom), $sp, '│'],
[flat '├', hx(h(), '┼') xx $geom, h(), '┤'] for ^1..$geomgrid-1;
appendpush @bond, [flat '│', vx($sp, v()) xx $geom), $sp, '│'],
[flat '├', hx(h(), '┴') xx $geom, h(), '┤'],
[flat '│', ($sp, ' ') xxx ($geomgrid-1), $sp, '│'];
 
sub hhx { my($c)=@_; {my rand@l; <push @l, (h(),$probc) ??for 1..$spgrid-1; !!return '───'@l; }
sub v ()vx { rand < $prob ?? ' ' !! '│' my @l; push @l, $sp, v() for 1..$grid-1; return @l; }
sub h { rand() < $prob ? $sp : '───' }
}</lang>
sub v { rand() < $prob ? ' ' : '│' }
{{out}}
}
<pre>Sample percolation at .6
│▒▒▒ │
├▒▒▒┬ ┬───┬ ┬ ┬ ┬ ┬ ┬───┬ ┤
│▒▒▒▒▒▒▒ │ │ │
├───┼▒▒▒┼ ┼ ┼ ┼ ┼ ┼───┼ ┼ ┤
│▒▒▒▒▒▒▒▒▒▒▒│ │ │ │ │ │ │
├▒▒▒┼───┼▒▒▒┼ ┼───┼ ┼───┼ ┼ ┼ ┤
│▒▒▒│▒▒▒▒▒▒▒▒▒▒▒ │ │ │
├▒▒▒┼───┼───┼▒▒▒┼ ┼ ┼───┼ ┼ ┼ ┤
│▒▒▒│ ▒▒▒│ │ │ │ │
├───┼ ┼ ┼▒▒▒┼───┼ ┼ ┼ ┼ ┼───┤
│ │▒▒▒ │ │
├ ┼───┼ ┼▒▒▒┼───┼───┼───┼───┼ ┼───┤
│ │▒▒▒│ │
├───┼ ┼───┼▒▒▒┼───┼───┼───┼───┼ ┼───┤
│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ │ │ │
├▒▒▒┼▒▒▒┼───┼▒▒▒┼───┼ ┼───┼ ┼ ┼ ┤
│▒▒▒│▒▒▒▒▒▒▒│▒▒▒▒▒▒▒│ │
├▒▒▒┼───┼───┼───┼───┼───┼ ┼ ┼ ┼ ┤
│▒▒▒▒▒▒▒ │ │ │ │
├▒▒▒┼▒▒▒┼───┼───┼ ┼───┼───┼ ┼ ┼ ┤
│▒▒▒│▒▒▒ │ │ │
├───┴▒▒▒┴ ┴ ┴ ┴───┴ ┴ ┴ ┴───┤
│ ▒▒▒ │
 
print "Sample percolation at .6\n";
percolate(.6);
for my $row (@bond) {
my $line = '';
$line .= join '', $_ for @$row;
print "$line\n";
}
 
my $tests = 100;
print "Doing $tests trials at each porosity:\n";
my @table;
for my $p (1 .. 10) {
$p = $p/10;
my $total = 0;
$total += percolate($p) for 1..$tests;
printf "p = %0.1f: %0.2f\n", $p, $total / $tests
}</syntaxhighlight>
{{out}}
<pre>Sample percolation at .6
│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ │
├───┬───┬───┬▒▒▒┬ ┬ ┬ ┬───┬ ┬───┤
│ ▒▒▒▒▒▒▒ │ │ │
├───┼───┼▒▒▒┼───┼───┼ ┼───┼───┼ ┼ ┤
│ │▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒│ │ │ │
├───┼───┼───┼───┼▒▒▒┼▒▒▒┼ ┼───┼───┼───┤
│ │ │▒▒▒│▒▒▒▒▒▒▒ │
├───┼───┼ ┼───┼───┼───┼▒▒▒┼ ┼ ┼ ┤
│ │ ▒▒▒▒▒▒▒ │ │
├───┼───┼───┼ ┼ ┼▒▒▒┼───┼ ┼ ┼───┤
│ │ │▒▒▒ │ │
├───┼ ┼───┼ ┼───┼▒▒▒┼ ┼ ┼───┼ ┤
│ │ ▒▒▒▒▒▒▒│ │ │
├ ┼ ┼ ┼ ┼▒▒▒┼───┼ ┼───┼───┼ ┤
│ │ ▒▒▒│ │ │
├ ┼ ┼ ┼ ┼▒▒▒┼───┼ ┼ ┼───┼ ┤
│ │ ▒▒▒│ │ │
├───┼ ┼───┼ ┼▒▒▒┼ ┼ ┼ ┼ ┼ ┤
│ │ │▒▒▒ │ │ │ │
├───┼───┼ ┼ ┼▒▒▒┼───┼ ┼ ┼ ┼───┤
│ │ ▒▒▒│ │ │ │
├ ┴───┴ ┴ ┴▒▒▒┴ ┴───┴ ┴ ┴───┤
│ ▒▒▒ │
Doing 100 trials at each porosity:
p = 0.1: 0.00
p = 0.2: 0.00
p = 0.3: 0.00
p = 0.4: 0.0503
p = 0.5: 0.4238
p = 0.6: 0.9283
p = 0.7: 10.0099
p = 0.8: 1.00
p = 0.9: 1.00
p = 1.0: 1.00</pre>
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wall</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"---"</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">cell</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"|"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">grid</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">new_grid</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wall</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">cell</span><span style="color: #0000FF;">),</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- now knock down some walls</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">jstart</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">jlimit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])-</span><span style="color: #000000;">3</span>
<span style="color: #000080;font-style:italic;">-- (ie 2..38 on odd lines, 5..37 on even)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">jstart</span> <span style="color: #008080;">to</span> <span style="color: #000000;">jlimit</span> <span style="color: #008080;">by</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">rnd</span><span style="color: #0000FF;">()></span><span style="color: #000000;">p</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">..</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" "</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">percolate</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])-</span><span style="color: #000000;">2</span> <span style="color: #008080;">by</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">and</span> <span style="color: #000000;">percolate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'*'</span>
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">and</span> <span style="color: #000000;">percolate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">></span><span style="color: #000000;">6</span> <span style="color: #008080;">and</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">and</span> <span style="color: #000000;">percolate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;"><</span><span style="color: #000000;">36</span> <span style="color: #008080;">and</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">and</span> <span style="color: #000000;">percolate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">4</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">and</span> <span style="color: #000000;">percolate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">LIM</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1000</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">LIM</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">new_grid</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">percolate</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"p=%.1f: %5.3f\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">/</span><span style="color: #000000;">LIM</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"sample grid for p=0.6:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">new_grid</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0.6</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">percolate</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
p=0.0: 1.000
p=0.1: 1.000
p=0.2: 1.000
p=0.3: 0.997
p=0.4: 0.897
p=0.5: 0.434
p=0.6: 0.067
p=0.7: 0.003
p=0.8: 0.000
p=0.9: 0.000
p=1.0: 0.000
sample grid for p=0.6:
+---+---+ * +---+ * + * +---+---+ * + * +
| * * * | | * * | * | | * * |
+---+---+ * + +---+ * + * +---+---+ * +
| * * | * | | | * | * | * * * |
+---+ * + * +---+---+---+ * +---+ * +---+
| | * | * | * | * | * * * * * |
+ + * + * + * + * + * +---+ * + * +---+
| | * * * * | * * | * * * |
+ + * + * +---+ * +---+ * +---+ * + * +
| | * | * * * | * * | * * | * |
+---+ * +---+ * +---+---+---+---+ * + * +
| | * | | * * * * | * * | * |
+ +---+ +---+ * +---+---+---+---+ * +
| | | | | * | | | * |
+ +---+---+ +---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+ + +---+ + +---+---+
| | | | | | | | |
+ +---+ +---+---+ +---+---+---+---+
| | | | | | | | | |
+---+---+ + + +---+---+---+---+ +
</pre>
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">from collections import namedtuple
from random import random
from pprint import pprint as pp
Line 779 ⟶ 1,737:
print('\n p: Fraction of %i tries that percolate through' % t )
pp({p:c/float(t) for p, c in pcount.items()})</langsyntaxhighlight>
 
{{out}}
Line 827 ⟶ 1,785:
=={{header|Racket}}==
 
<langsyntaxhighlight lang="racket">#lang racket
 
(define has-left-wall? (lambda (x) (bitwise-bit-set? x 0)))
Line 943 ⟶ 1,901:
(make/display/flood/display-bonded-grid 10 10 .25 20)
(make/display/flood/display-bonded-grid 10 10 .50 20)
(make/display/flood/display-bonded-grid 10 10 .75 20000))</langsyntaxhighlight>
 
{{out}}
Line 1,052 ⟶ 2,010:
proportion of grids that percolate p=9/10 : 0 (0.00000)
proportion of grids that percolate p=1 : 0 (0.00000)</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2017.02}}
Starts "filling" from the top left. Fluid flow favours directions in Down, Left, Right, Up order. I interpreted p to be porosity, so small p mean low permeability, large p means high permeability.
 
<syntaxhighlight lang="raku" line>my @bond;
my $grid = 10;
my $geom = $grid - 1;
my $water = '▒';
 
enum Direction <DeadEnd Up Right Down Left>;
 
say 'Sample percolation at .6';
percolate .6;
.join.say for @bond;
say "\n";
 
my $tests = 100;
say "Doing $tests trials at each porosity:";
for .1, .2 ... 1 -> $p {
printf "p = %0.1f: %0.2f\n", $p, (sum percolate($p) xx $tests) / $tests
}
 
sub percolate ( $prob ) {
generate $prob;
my @stack;
my $current = [1;0];
$current.&fill;
 
loop {
if my $dir = direction( $current ) {
@stack.push: $current;
$current = move $dir, $current
}
else {
return False unless @stack;
$current = @stack.pop
}
return True if $current[1] == +@bond - 1
}
 
sub direction( [$x, $y] ) {
( Down if @bond[$y + 1][$x].contains: ' ' ) ||
( Left if @bond[$y][$x - 1].contains: ' ' ) ||
( Right if @bond[$y][$x + 1].contains: ' ' ) ||
( Up if @bond[$y - 1][$x].defined && @bond[$y - 1][$x].contains: ' ' ) ||
DeadEnd
}
 
sub move ( $dir, @cur ) {
my ( $x, $y ) = @cur;
given $dir {
when Up { [$x,--$y].&fill xx 2 }
when Down { [$x,++$y].&fill xx 2 }
when Left { [--$x,$y].&fill xx 2 }
when Right { [++$x,$y].&fill xx 2 }
}
[$x, $y]
}
 
sub fill ( [$x, $y] ) { @bond[$y;$x].=subst(' ', $water, :g) }
}
 
sub generate ( $prob = .5 ) {
@bond = ();
my $sp = ' ';
append @bond, [flat '│', ($sp, ' ') xx $geom, $sp, '│'],
[flat '├', (h(), '┬') xx $geom, h(), '┤'];
append @bond, [flat '│', ($sp, v()) xx $geom, $sp, '│'],
[flat '├', (h(), '┼') xx $geom, h(), '┤'] for ^$geom;
append @bond, [flat '│', ($sp, v()) xx $geom, $sp, '│'],
[flat '├', (h(), '┴') xx $geom, h(), '┤'],
[flat '│', ($sp, ' ') xx $geom, $sp, '│'];
 
sub h () { rand < $prob ?? $sp !! '───' }
sub v () { rand < $prob ?? ' ' !! '│' }
}</syntaxhighlight>
{{out}}
<pre>Sample percolation at .6
│▒▒▒ │
├▒▒▒┬ ┬───┬ ┬ ┬ ┬ ┬ ┬───┬ ┤
│▒▒▒▒▒▒▒ │ │ │
├───┼▒▒▒┼ ┼ ┼ ┼ ┼ ┼───┼ ┼ ┤
│▒▒▒▒▒▒▒▒▒▒▒│ │ │ │ │ │ │
├▒▒▒┼───┼▒▒▒┼ ┼───┼ ┼───┼ ┼ ┼ ┤
│▒▒▒│▒▒▒▒▒▒▒▒▒▒▒ │ │ │
├▒▒▒┼───┼───┼▒▒▒┼ ┼ ┼───┼ ┼ ┼ ┤
│▒▒▒│ ▒▒▒│ │ │ │ │
├───┼ ┼ ┼▒▒▒┼───┼ ┼ ┼ ┼ ┼───┤
│ │▒▒▒ │ │
├ ┼───┼ ┼▒▒▒┼───┼───┼───┼───┼ ┼───┤
│ │▒▒▒│ │
├───┼ ┼───┼▒▒▒┼───┼───┼───┼───┼ ┼───┤
│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ │ │ │
├▒▒▒┼▒▒▒┼───┼▒▒▒┼───┼ ┼───┼ ┼ ┼ ┤
│▒▒▒│▒▒▒▒▒▒▒│▒▒▒▒▒▒▒│ │
├▒▒▒┼───┼───┼───┼───┼───┼ ┼ ┼ ┼ ┤
│▒▒▒▒▒▒▒ │ │ │ │
├▒▒▒┼▒▒▒┼───┼───┼ ┼───┼───┼ ┼ ┼ ┤
│▒▒▒│▒▒▒ │ │ │
├───┴▒▒▒┴ ┴ ┴ ┴───┴ ┴ ┴ ┴───┤
│ ▒▒▒ │
 
Doing 100 trials at each porosity:
p = 0.1: 0.00
p = 0.2: 0.00
p = 0.3: 0.00
p = 0.4: 0.05
p = 0.5: 0.42
p = 0.6: 0.92
p = 0.7: 1.00
p = 0.8: 1.00
p = 0.9: 1.00
p = 1.0: 1.00</pre>
 
=={{header|Swift}}==
 
{{trans|C}}
 
<syntaxhighlight lang="swift">let randMax = 32767.0
let filled = 1
let rightWall = 2
let bottomWall = 4
 
final class Percolate {
let height: Int
let width: Int
 
private var grid: [Int]
private var end: Int
 
init(height: Int, width: Int) {
self.height = height
self.width = width
self.end = width
self.grid = [Int](repeating: 0, count: width * (height + 2))
}
 
private func fill(at p: Int) -> Bool {
guard grid[p] & filled == 0 else { return false }
 
grid[p] |= filled
 
guard p < end else { return true }
 
return (((grid[p + 0] & bottomWall) == 0) && fill(at: p + width)) ||
(((grid[p + 0] & rightWall) == 0) && fill(at: p + 1)) ||
(((grid[p - 1] & rightWall) == 0) && fill(at: p - 1)) ||
(((grid[p - width] & bottomWall) == 0) && fill(at: p - width))
}
 
func makeGrid(porosity p: Double) {
grid = [Int](repeating: 0, count: width * (height + 2))
end = width
 
let thresh = Int(randMax * p)
 
for i in 0..<width {
grid[i] = bottomWall | rightWall
}
 
for _ in 0..<height {
for _ in stride(from: width - 1, through: 1, by: -1) {
let r1 = Int.random(in: 0..<Int(randMax)+1)
let r2 = Int.random(in: 0..<Int(randMax)+1)
 
grid[end] = (r1 < thresh ? bottomWall : 0) | (r2 < thresh ? rightWall : 0)
 
end += 1
}
 
let r3 = Int.random(in: 0..<Int(randMax)+1)
 
grid[end] = rightWall | (r3 < thresh ? bottomWall : 0)
 
end += 1
}
}
 
@discardableResult
func percolate() -> Bool {
var i = 0
 
while i < width && !fill(at: width + i) {
i += 1
}
 
return i < width
}
 
func showGrid() {
for _ in 0..<width {
print("+--", terminator: "")
}
 
print("+")
 
for i in 0..<height {
print(i == height ? " " : "|", terminator: "")
 
for j in 0..<width {
print(grid[i * width + j + width] & filled != 0 ? "[]" : " ", terminator: "")
print(grid[i * width + j + width] & rightWall != 0 ? "|" : " ", terminator: "")
}
 
print()
 
guard i != height else { return }
 
for j in 0..<width {
print(grid[i * width + j + width] & bottomWall != 0 ? "+--" : "+ ", terminator: "")
}
 
print("+")
}
}
}
 
let p = Percolate(height: 10, width: 10)
 
p.makeGrid(porosity: 0.5)
p.percolate()
p.showGrid()
 
print("Running \(p.height) x \(p.width) grid 10,000 times for each porosity")
 
for factor in 1...10 {
var count = 0
let porosity = Double(factor) / 10.0
 
for _ in 0..<10_000 {
p.makeGrid(porosity: porosity)
 
if p.percolate() {
count += 1
}
}
 
print("p = \(porosity): \(Double(count) / 10_000.0)")
}</syntaxhighlight>
 
{{out}}
 
<pre>+--+--+--+--+--+--+--+--+--+--+
|[]| | | | | | |
+ + +--+--+ + +--+ + + +
|[] [] | | | |
+--+ +--+--+ +--+--+ +--+ +
| [] [] []| | | |
+ +--+--+ + +--+--+ + + +
| [] []| | |
+--+--+ +--+ + + + +--+ +
| [] [] | | | |
+ +--+--+ +--+--+--+--+ +--+
| | | |[] | | |
+ + +--+ +--+--+--+--+--+--+
| | |[] [] [] | |
+--+--+--+--+--+ + +--+--+ +
| | | |[]| | | |
+ + + + +--+ +--+ + +--+
| | | | [] []| | | |
+--+--+--+--+ +--+--+--+--+ +
| | | [] | | |
+--+--+ +--+ +--+ +--+--+ +
Running 10 x 10 grid 10,000 times for each porosity
p = 0.1: 1.0
p = 0.2: 1.0
p = 0.3: 0.9968
p = 0.4: 0.9125
p = 0.5: 0.4959
p = 0.6: 0.0858
p = 0.7: 0.004
p = 0.8: 0.0
p = 0.9: 0.0
p = 1.0: 0.0</pre>
 
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
{{trans|Python}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.6
 
# Structure the bond percolation system as a class
Line 1,167 ⟶ 2,401:
puts [format "p=%.2f: %2.1f%%" $p [expr {$tot*100./$tries}]]
}
}}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,206 ⟶ 2,440:
p=0.90: 0.0%
p=1.00: 0.0%
</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "random" for Random
import "./fmt" for Fmt
 
var rand = Random.new()
var RAND_MAX = 32767
 
// cell states
var FILL = 1
var RWALL = 2 // right wall
var BWALL = 4 // bottom wall
 
var x = 10
var y = 10
var grid = List.filled(x * (y + 2), 0)
var cells = 0
var end = 0
var m = 0
var n = 0
 
var makeGrid = Fn.new { |p|
var thresh = (p * RAND_MAX).truncate
m = x
n = y
for (i in 0...grid.count) grid[i] = 0 // clears grid
for (i in 0...m) grid[i] = BWALL | RWALL
cells = m
end = m
for (i in 0...y) {
for (j in x - 1..1) {
var r1 = rand.int(RAND_MAX + 1)
var r2 = rand.int(RAND_MAX + 1)
grid[end] = ((r1 < thresh) ? BWALL : 0) |
((r2 < thresh) ? RWALL : 0)
end = end + 1
}
var r3 = rand.int(RAND_MAX + 1)
grid[end] = RWALL | ((r3 < thresh) ? BWALL : 0)
end = end + 1
}
}
 
var showGrid = Fn.new {
for (j in 0...m) System.write("+--")
System.print("+")
 
for (i in 0..n) {
System.write((i == n) ? " " : "|")
for (j in 0...m) {
System.write(((grid[i * m + j + cells] & FILL) != 0) ? "[]" : " ")
System.write(((grid[i * m + j + cells] & RWALL) != 0) ? "|" : " ")
}
System.print()
if (i == n) return
for (j in 0...m) {
System.write(((grid[i * m + j + cells] & BWALL) != 0) ? "+--" : "+ ")
}
System.print("+")
}
}
 
var fill // recursive
fill = Fn.new { |p|
if ((grid[p] & FILL) != 0) return false
grid[p] = grid[p] | FILL
if (p >= end) return true // success: reached bottom row
return (((grid[p + 0] & BWALL) == 0) && fill.call(p + m)) ||
(((grid[p + 0] & RWALL) == 0) && fill.call(p + 1)) ||
(((grid[p - 1] & RWALL) == 0) && fill.call(p - 1)) ||
(((grid[p - m] & BWALL) == 0) && fill.call(p - m))
}
 
var percolate = Fn.new {
var i = 0
while (i < m && !fill.call(cells + i)) i = i + 1
return i < m
}
 
makeGrid.call(0.5)
percolate.call()
showGrid.call()
 
System.print("\nRunning %(x) x %(y) grids 10,000 times for each p:")
for (p in 1..9) {
var cnt = 0
var pp = p / 10
for (i in 0...10000) {
makeGrid.call(pp)
if (percolate.call()) cnt = cnt + 1
}
Fmt.print("p = $3g: $.4f", pp, cnt / 10000)
}</syntaxhighlight>
 
{{out}}
Sample run:
<pre>
+--+--+--+--+--+--+--+--+--+--+
|[]|[] []|[] [] []|[] []|[] []|
+--+ + +--+ +--+--+ +--+ +
| [] []|[] []|[] [] []|[] []|
+--+--+--+--+--+--+--+--+ + +
| | | | |[] [] [] [] []|
+--+--+ + + +--+--+--+ +--+
| | |[] [] [] []| |
+--+ +--+ + + + +--+ + +
| | |[]|[]|[] []| |
+ +--+--+ + + +--+--+--+--+
| | | |[]| | |
+--+ + + +--+ +--+--+ +--+
| | |[]| | |
+ + + +--+--+ + +--+--+--+
| |[] []| |
+ +--+--+--+ +--+ +--+--+--+
| | [] [] []| | |
+--+--+--+--+--+--+ +--+--+ +
| | |[] []| | | |
+ +--+--+--+ + +--+ + +--+
[]
 
Running 10 x 10 grids 10,000 times for each p:
p = 0.1 : 1.0000
p = 0.2 : 0.9999
p = 0.3 : 0.9970
p = 0.4 : 0.9120
p = 0.5 : 0.5022
p = 0.6 : 0.0829
p = 0.7 : 0.0026
p = 0.8 : 0.0000
p = 0.9 : 0.0000
</pre>
 
=={{header|zkl}}==
{{trans|C}}
<langsyntaxhighlight lang="zkl">// cell states
const FILLED=1; // and odd
const RWALL =2; // right wall
Line 1,255 ⟶ 2,622:
i:=0; while(i<m and not fill(grid,i+m,m)){ i+=1; } // pour juice on top row
return(i<m); // percolated through the grid?
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">grid:=makeGrid(10,10,0.40);
println("Did liquid percolate: ",percolate(grid,10)); show(grid,10,10);
 
Line 1,263 ⟶ 2,630:
cnt:=0.0; do(10000){ cnt+=percolate(makeGrid(10,10,p),10); }
"p=%.1f: %.4f".fmt(p, cnt/10000).println();
}</langsyntaxhighlight>
{{out}}
<pre>
Alextretyak
1,480

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/234142...363368"