from random import randint,random
from math import sqrt,cos,sin,pi
import matplotlib.pyplot as plt

# Question 1

def conducteur(p):
    return random() < p

# Question 2

def config(n,p):
    """
    Construit une liste de n^2 listes [i,x,y,c]
    i : numero de la boule
    x,y : coordonnées
    cond : conducteur ou non
    """
    L = []
    for lig in range(n):
        for col in range(n):
            i = col+n*lig
            if lig % 2 == 0:
                x = 1+2*col
            else:
                x = 2+2*col
            y = 1+sqrt(3)*lig
            cond = conducteur(p)
            L.append([i,x,y,cond])
    return L

# Tracé des billes

def trace(L):
    for bille in L:
        i,x,y,c = bille
        abs = [x+cos(k*2*pi/100) for k in range(101)]
        ord = [y+sin(k*2*pi/100) for k in range(101)]
        if c:
            plt.plot(abs,ord,"r")
        else:
            plt.plot(abs,ord,"b")
        plt.text(x-0.2,y-0.2,str(i))
        plt.show()

# L = config(10,0.5)
# trace(L)

# Question 3

def distance(P,Q):
    x1,y1 = P
    x2,y2 = Q
    return sqrt((x1-x2)**2+(y1-y2)**2)

# Question 4

def voisins(L,k):
    """
    k est un elt, L est une liste config
    renvoie les voisins de k
    """
    vois = []
    P = [L[k][1],L[k][2]]
    for l in L:
        i,x,y,c = l
        Q = [x,y]
        if distance(P,Q)<2.5 and c:
            vois.append(i)
    return vois

# Question 5

def sommets(L):
    c = []
    for i in range(len(L)):
        if L[i][3]:
            c.append(i)
    return c

# Question 6

def graphe(L):
    som = sommets(L)
    dico = {}
    for i in som:
        dico[i] = voisins(L,i)
    return dico

# Question 7

def ajoute_sommet(dico,chemin):
    sommet = chemin[-1]
    L = []
    for i in dico[sommet]:
        if not i in chemin:
            L.append(chemin+[i])
    return L

def percolation(L,n):
    som = sommets(L)
    dico = graphe(L)
    i = 0
    while len(som) > i and som[i] < n:
        chemins_temp = [[som[i]]]
        chemins = []
        while len(chemins_temp) != 0:
            c = chemins_temp.pop()
            if c[-1] >= n**2-n:
                return True
            else:
                L = ajoute_sommet(dico,c)
                if L == []:
                    chemins.append(c)
                else:
                    for l in L:
                        chemins_temp.append(l)
        i += 1
    return False

def chemin_perco(L,n):
    som = sommets(L)
    dico = graphe(L)
    i = 0
    while len(som) > i and som[i] < n:
        chemins_temp = [[som[i]]]
        chemins = []
        while len(chemins_temp) != 0:
            c = chemins_temp.pop()
            if c[-1] >= n**2-n:
                return c
            else:
                L = ajoute_sommet(dico,c)
                if L == []:
                    chemins.append(c)
                else:
                    for l in L:
                        chemins_temp.append(l)
        i += 1
    return False

def dessin_chemin(c):
    abs = [L[i][1] for i in c]
    ord = [L[i][2] for i in c]
    plt.plot(abs,ord,"k")
    plt.show()

L = config(10,0.5)
trace(L)
if percolation(L,10):
    c = chemin_perco(L,10)
    dessin_chemin(c)

def percolation_moyenne(n,p):
    S = 0
    for i in range(20):
        L = config(n,p)
        if percolation(L,n):
            S += 1
    return S/20
#
# Prob = [i/20 for i in range(1,20)]
# moy = [percolation_moyenne(10,p) for p in Prob]
# plt.plot(Prob,moy)
# plt.show()