We consider here the probability to percolate (i.e. find a path) in a triangular shape made of hexagons as given in Fig. 1.
Fig. 1 : Departure line in red (hexagons $1, 2, 4, 7, 11, 16, 22$). Arrival line in blue. The "YES" verdict means that one can "percolate" from the red line to the blue line by finding a path between them made of blue hexagons, turning around yellow hexagons (walls), here by taking for example the path $22,30,39,40, \cdots 72,84,97$.
where the blue hexagons are for empty spaces and the yellow hexagons for "walls" ; the starting points are any of the hexagons above red line (here hexagon numbers $1,2, 4,7,11,16,22$) and arrival point any of the hexagons ($92, 93, \cdots 105$) along the dark blue line. The colors blue/yellow of each hexagon is randomly chosen with equal probability for each one.
Rather recent Cardy's formula (Bibliography at the bottom) says the probability to percolate through the triangle from the red line to the blue line is equal to the ratio of their lengths.
In the case at hand, the probability to percolate is $7/14 = 1/2$.
I have written a Matlab program providing, for a given coloring of the "triangle's floor", and for a certain length of the red (departure) line (always beginning at the left hand vertex), the verdict "YES/NO" about the possibility to percolate.
This program builds and uses for this purpose the adjacency matrix $V$ of the different hexagons (here a $105 \times 105$ matrix with $V_{i,j}=1 $ if and only hexagon $H_i$ is contiguous to hexagon $H_j$, with $V_{i,j}=0$ otherwise).
Let us denote by $W$ the $k$th power of $V$. It is well known that
$$W_{i,j}=1 \ \text{indicates the existence of a k steps path between } \ H_i \ \text{and} \ H_j.$$
Using powers of a large dimensional matrix is known to be computational-heavy, therefore unefficient for large sizes. Some improvements can be made but it will not speed up the process in an important way.
My question: Are some of the readers of this question able to propose a more efficient computational approach (cellular automata, complex transformations ...), in the spirit of being understandable at graduate level (my purpose is to give this issue as a project for students at this level) ?
Matlab program :
clear all; close all; hold on; axis equal off;
X=7; % width of the horizontal "departure" line
n=14; % triangle sidelengths
nh=n*(n+1)/2; % total number of hexagons
E=1:X;E=E.*(E-1)/2+1; % list of numbers of departure hexagons (here 1,2,4, ... 22)
pro=0.5; % proportion of yellow hexagons
ex=round(nh/2); % max power for adjacency matrix
% construction of adjacency matrix V
for x=1:n;
p=x*(x-1)/2+1; % index of the k-th bottom hex (ex. x=5 -> p=11)
d=p+x;
for y=0:x-1
V(p+y,d+y)=1;V(p+y,d+y+1)=1; % EAST and NORTH-EAST neighbours
end;
for y=0:x-2;V(p+y,p+y+1)=1;end;% NORTH-WEST neighbours
end;
V=V(:,1:nh); % matrix "chopping" in order to get a square matrix
V=V+V'+eye(nh); % transposition used to create reciprocal links
% WEST neighbours, etc... (a cell has at most 6 neighbours)
% Adding identity matrix means that any hex. is its own neighbour
% 1) Graphical pa)art :
H=exp(i*pi/6)*exp(1i*(0:6)*pi/3); % model hexagon
t=['y','c']; % colors array
k=1;
plot(sqrt(3)/2+sqrt(3)*[0,X],[-1.5,-1.5],'r')
plot(sqrt(3)*[n+1,n+1+n*exp(2*i*pi/3)],'b');
for x=1:n
for y=0:x-1
C=sqrt(3)*(x+y*exp(2*i*pi/3)); % center
c=(rand>pro); % numbers 0 or 1 according to color BLUE/YELLOW
D=C+H;
fill(real(D),imag(D),t(c+1));
text(real(C),imag(C),num2str(k),'horizontalalignment','center');
dt(k)=c;
k=k+1;
end;
end;
D=diag(dt);
W=D*V*D; % lines and columns of yellow hexagons are set to 0
W=W^ex;
Q=sum(sum(W(E,(nh-n+1):nh)));
Rep='NO YES';z=(Q>0);text(3*n/2,n,Rep(1+3*z:3+3*z));
% 2) statistical part
ne=1000;% number of attempts
c=0;% number of successes (= number of cases where percolation takes place)
for k=1:ne
D=diag(rand(1,nh)>pro);
W=D*V*D; % see supra
W=W^ex; % big power
if sum(sum(W(E,(nh-n+1):nh)))>0;c=c+1;end
end;
pro=c/ne, % proportion of successes (should be closed to X/14)
% according to Cardy's formula
Bibliography :
https://www.ihes.fr/~duminil/publi/2013lecture_notes_percolation.pdf
https://www.ihes.fr/~duminil/teaching.html
http://hongler.org/lattice-models/triangular-lattice.pdf
https://www.researchgate.net/publication/225743589_Cardy's_Formula_for_some_Dependent_Percolation_Models
This is more extended comment than answer, but it may be sufficient. The pseudo code here suggests an application of a flood fill algorithm.
for each hexagon above the red line: if the hexagon is blue: color it green add it to a list of green hexagons for each hexagon in the list: for each adjacent hexagon: if it is blue: color it green add it to the list of green hexagons if any hexagon along the blue line is green, the goal has been reachedNotes: You do not need an $n\times n$ matrix. An $n\times 6$ matrix will do. Each entry $(i,j)$ gives the index of a hexagon adjacent to hexagon $i$. For hexagons with fewer than six neighbours, a value of $0$ will indicate no further neighbours.