from pylab import *

### Question 1)
### randint(p,q) pioche un entier au hasard dans [p,q[

def Proc1() :
    LX=[k for k in range(1,15)]
    LY=[]
    for k in LX :
        A_alea=[randint(0,2) for i in range(2**(k+2))]
        LY.append(len([x for x in A_alea if x==0])/2**(k+2))
    figure()
    grid()
    plot(LX,LY)
    show()
        
# Proc1()

def Proc2() :
    LX=[k for k in range(1,15)]
    LZ=[]
    for k in LX :
        A_alea=[binomial(1,1/3) for i in range(2**(k+2))]
        LZ.append(len([x for x in A_alea if x==1])/2**(k+2))
    figure()
    grid()
    plot(LX,LZ)
    show()

# Proc2()

# M=ones((5,5,3))
# N=M.copy()
# ion() # mode interactif
# figure(1) # nouvelle figure
# axis('off')
# image=imshow(M,cmap="jet",interpolation="nearest") #trace de l'image
# show() # affichage
# pause(0.05) # pause en seconde
# L_Cases=[]
# while len(L_Cases)<25  : 
#     i=randint(0,5)
#     j=randint(0,5)
#     if not([i,j] in L_Cases) :
#         L_Cases.append([i,j])
#     M[i,j]=(uniform(0,1),uniform(0,1),uniform(0,1)) # couleur aléatoire
#     image.set_data(M) # on met a jour les donnees de la figure
#      
#     title("Nombre de cases remplies : "+str(len(L_Cases)))
#     image.changed() # on indique que l'image a changé, il faudra la redessiner
#     draw() # on redessine
#     pause(0.05) # on attend un peu   
#     show()  
# ioff() # fin du mode interactif

### IMPLEMENTATION DE L'ANIMATION

def Pioche(L) :
    return L[randint(0,len(L))]
    
# L=[0,1]
# print([Pioche(L) for k in range(10)])


def Visualisation(M) :
    figure()
    axis('off')
    imshow(M,interpolation='nearest')
    show()
    

def Initialise(p,q,dep,arr,proba) :
    """ renvoie une matrice de taille p*q avec des obstacles (0) pris au hasard, un point de départ et un point d'arrivée avec une proba proba d'avoir un obstacle"""
    M=ones((p,q,3))
    i,j=dep
    k,l=arr
    for x in range(p) :
        for y in range(q) :
            if binomial(1,proba) :
                M[x,y]=(0,0,0) # obstacle noir
    M[i,j]=(0,1,0) # point de départ vert
    M[k,l]=(1,0,0) # point d'arrivée rouge
    return M
    
# TESTS

# p=10
# q=30
# proba=0.99
# dep=[3,9]
# arr=[20,20]

# Visualisation(Initialise(p,q,dep,arr,proba))
    

def Voisins(M,case) :
    """ M est une matrice dont les obstacles sont noirs ; case voisine = case blanche ou case d'arrivée rouge """
    dx,dy=M.shape[:2]
    Res=[]
    i,j=case
    if i>0 and (all(M[i-1,j]==(1,1,1)) or all(M[i-1,j]==(1,0,0))) :
        Res.append([i-1,j])
    if i<dx-1 and (all(M[i+1,j]==(1,1,1)) or all(M[i+1,j]==(1,0,0))) :
        Res.append([i+1,j])
    if j>0 and (all(M[i,j-1]==(1,1,1)) or all(M[i,j-1]==(1,0,0))) :
        Res.append([i,j-1])
    if j<dy-1 and (all(M[i,j+1]==(1,1,1)) or all(M[i,j+1]==(1,0,0))) :
        Res.append([i,j+1])
    return Res
    
    

def Algo(M,dep,arr) :
    """ implémente une pile de recherche pour naviguer dans la matrice """
    Pile=[dep]
    c=0
    ion() # mode interactif
    figure(1) # nouvelle figure
    axis('off')
    image=imshow(M,cmap="jet",interpolation="nearest") #trace de l'image
    show() # affichage
    pause(0.05) # necessaire (bug matplotlib)
    
    while Pile!=[] and Pile[-1]!=arr and fignum_exists(1) :
        pos=Pile[-1]
        V=Voisins(M,pos)
        if V!=[] :
            i,j=Pioche(V)
            if [i,j]!=arr and [i,j]!=dep :
                M[i,j]=(0,1,1)
            Pile.append([i,j])
        else :
            k,l=pos
            M[k,l]=(1,0,1)
            Pile.pop()
        image.set_data(M) # on met a jour les donnees de la figure
        title("Longueur de la pile: "+str(len(Pile)))
        image.changed() # on indique que l'image a change, il faudra la redessiner
        draw() # on redessine
        pause(0.05) # on attend un peu   
        
        show() # necessaire (bug matplotlib) 
    ioff() # fin du mode interactif
    if Pile==[] :
        print('Pas de chemin possible !!')
    else :
        print('Il y a un chemin possible !!')

p=20
q=20
proba=0.3
dep=[3,19]
arr=[17,13] 
M=Initialise(p,q,dep,arr,proba)
Algo(M,dep,arr)