import matplotlib.pyplot as plt
import matplotlib as mpl
import numpy as np
from random import random
## Fonctions pour les piles
def estvide(p):
    return(p==[])

def newpile():
    return([])

def depile(p):
    return(p.pop())

def empile(x,p):
    p.append(x)

def sommet(p):
    return(p[-1])
    
##

def probapond(a,b,p):
    """retourne a avec un proba de p et b avec une proba de 1-p, p dans [0,1]"""
    k = random()
    return(a*(k<p) + b*(k>p))


def cree_grille(n,p):
    M = np.zeros((n,n))
    for i in range(n):
        for j in range(n):
            M[(i,j)] = probapond(2,0,p)
    return M

def remplit(M):
    p = newpile()
    for i in range(0,len(M)):
        if M[0,i] ==  2:
            empile([0,i],p)
            M[0,i] = 1
    while not estvide(p):
        a,b = depile(p)
        d = (a,b+1)
        g = (a,b-1)
        h = (a-1,b)
        b = (a+1,b)
        if d[1] < len(M) and M[d]== 2:
            empile(d,p)
            M[d] =  1
        if g[1] >=0 and M[g]== 2:
            empile(g,p)
            M[g] =  1
        if b[0] < len(M) and M[b]== 2:
            empile(b,p)
            M[b] =  1
        if h[0] >= 0 and M[h]==2:
            empile(h,p)
            M[h] =  1
    return M
    
M = cree_grille(400,0.8)

M2 = remplit(M)
plt.imshow(M,interpolation='none', cmap='gist_stern', norm = mpl.colors.Normalize(vmin=0.,vmax=2.))
plt.show()

def percolation(p,n):
    M = cree_grille(n,p)
    remplit(M)
    i = 0
    while i < n and M[n-1][i] != 1: 
        i = i + 1
    return(i<n)