How to resolve the algorithm Percolation/Site percolation step by step in the J programming language
How to resolve the algorithm Percolation/Site percolation step by step in the J programming language
Table of Contents
Problem Statement
Given an
M × N
{\displaystyle M\times N}
rectangular array of cells numbered
c e l l
[ 0.. M − 1 , 0.. N − 1 ]
{\displaystyle \mathrm {cell} [0..M-1,0..N-1]}
assume
M
{\displaystyle M}
is horizontal and
N
{\displaystyle N}
is downwards. Assume that the probability of any cell being filled is a constant
p
{\displaystyle p}
where Simulate creating the array of cells with probability
p
{\displaystyle p}
and then testing if there is a route through adjacent filled cells from any on row
0
{\displaystyle 0}
to any on row
N
{\displaystyle N}
, i.e. testing for site percolation. Given
p
{\displaystyle p}
repeat the percolation
t
{\displaystyle t}
times to estimate the proportion of times that the fluid can percolate to the bottom for any given
p
{\displaystyle p}
. Show how the probability of percolating through the random grid changes with
p
{\displaystyle p}
going from
0.0
{\displaystyle 0.0}
to
1.0
{\displaystyle 1.0}
in
0.1
{\displaystyle 0.1}
increments and with the number of repetitions to estimate the fraction at any given
p
{\displaystyle p}
as
t
= 100
{\displaystyle t>=100}
. Use an
M
15 , N
15
{\displaystyle M=15,N=15}
grid of cells for all cases. Optionally depict a percolation through a cell grid graphically. Show all output on this page.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Percolation/Site percolation step by step in the J programming language
Source code in the j programming language
groups=:[: +/\ 2 </\ 0 , *
ooze=: [ >. [ +&* [ * [: ; groups@[ <@(* * 2 < >./)/. +
percolate=: ooze/\.@|.^:2^:_@(* (1 + # {. 1:))
trial=: percolate@([ >: ]?@$0:)
simulate=: %@[ * [: +/ (2 e. {:)@trial&15 15"0@#
,.' P THRU';(, 100&simulate)"0 (i.%<:)11
┌────────┐
│ P THRU│
├────────┤
│ 0 0│
│0.1 0│
│0.2 0│
│0.3 0│
│0.4 0.01│
│0.5 0.09│
│0.6 0.61│
│0.7 0.97│
│0.8 1│
│0.9 1│
│ 1 1│
└────────┘
1j1 #"1 ' .#'{~ percolate 0.6>:?15 15$0
# # # # # # # #
# # # # # # # # # # # #
# # # # # # # #
# # # # # # # # #
# . # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # #
. # #
. . # # # #
. . . . # # # # # # # # #
. . . . # # # # # # #
. . . # . # # #
. . . . . . . # # .
. . . . . . . . # #
any =: +./
all =: *./
quickCheck =: [: all [: (any"1) 2 *./\ ] NB. a complete path requires connections between all row pairs
percolate =: 15 15&$: : (dyad define) NB. returns 0 iff blocked Use: (N, M) percolate P
NB. make a binary grid
GRID =: y (> ?@($&0)) x
NB. compute the return value
if. -. quickCheck GRID do. 0 return. end.
STARTING_SITES =. 0 ,. ({. GRID) # i. {: x NB. indexes of 1 in head row of GRID
any STARTING_SITES check GRID
)
NB. use local copy of GRID. Too slow.
check =: dyad define"1 2 NB. return 1 iff through path found use: START check GRID
GRID =. y
LOCATION =. x
if. 0 (= #) LOCATION do. 0 return. end. NB. no starting point? 0
if. LOCATION any@:((>: , 0 > [) $) GRID do. 0 return. end. NB. off grid? 0
INDEX =. <LOCATION
if. 1 ~: INDEX { GRID do. 0 return. end. NB. fail. either already looked here or non-path
if. (>: {. LOCATION) = (# GRID) do. 1 return. end. NB. Success! (display GRID here)
G =: GRID =. INDEX (>:@:{)`[`]}GRID
any GRID check~ LOCATION +"1 (, -)0 1,:1 0
)
NB. use global GRID.
check =: dyad define"1 2 NB. return 1 iff through path found use: START check GRID
LOCATION =. x
if. 0 (= #) LOCATION do. 0 return. end. NB. no starting point? 0
if. LOCATION any@:((>: , 0 > [) $) GRID do. 0 return. end. NB. off grid? 0
INDEX =. <LOCATION
if. 1 ~: INDEX { GRID do. 0 return. end. NB. fail. either already looked here or non-path
if. (>: {. LOCATION) = (# GRID) do. 1 return. end. NB. Success! (display GRID here)
GRID =: INDEX (>:@:{)`[`]}GRID
any GRID check~ LOCATION +"1 (, -)0 1,:1 0
)
simulate =: 100&$: : ([ %~ [: +/ [: percolate"0 #) NB. return fraction of connected cases. Use: T simulate P
You may also check:How to resolve the algorithm Loops/Wrong ranges step by step in the ALGOL W programming language
You may also check:How to resolve the algorithm Program termination step by step in the QB64 programming language
You may also check:How to resolve the algorithm Palindrome detection step by step in the MiniScript programming language
You may also check:How to resolve the algorithm Amb step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Middle three digits step by step in the Common Lisp programming language