import matplotlib.pyplot as plt
import matplotlib as mpl
import numpy as np
from turtle import *
from random import random
import sys

def trace(n):
    for i in range(n):
        forward(100/n**0.5)
        left(360/n)

##trace(40)
##plt.show()
##speed(0)
##left(90)
def arbre(n,l,th):
    if n == 0 :
        forward(l)
        backward(l)
    else :
        forward(l/3)
        right(th)
        arbre(n-1,2*l/3,th)
        left(2*th)
        arbre(n-1,2*l/3,th)
        right(th)
        backward(l/3)

def arbrec(n,l,th,c):
    if n == 0 :
        forward(l)
        backward(l)
    else :
        tr = random() - .5
        tr1 = random() -0.5
        lr = random() 
        lr1 = random()
        pensize(5*n/c)
        tup = (0.5,0.3+0.7*(c-n)/c,0)
        pencolor(tup)
        forward(l/3)
        right(th)
        arbrec(n-1,2*l*(1+lr/3)/3,th*(1+tr/5),c)
        left(2*th)
        arbrec(n-1,2*l*(1+lr1/3)/3,th*(1+tr1/5),c)
        right(th)
        penup()
        backward(l/3)
        pendown()

def Fc(a,b,L):
    bn = a/b - int(a/b) 
    if abs(bn) < 10**(-10):
        if int(a/b) == 1:
            return(L[:-1] + [L[-1] + 1])
        else : 
            return(L + [int(a/b)])
    else :
        return(Fc(1,bn,L + [int(a/b)]))
        
def evalueFC(L):
    if len(L) ==1 :
        return(L[0])
    else :
        return(L[0]+1/evalueFC(L[1:]))


def FcR(x,L,n):
    xn = x - int(x) 
    if len(L) == n or abs(xn) < 10**(-10):
        if int(x) == 1:
            return(L[:-1] + [L[-1] + 1])
        else : 
            return(L + [int(x)])
    else :
        return(FcR(1/xn,L + [int(x)],n))



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):
    sys.setrecursionlimit(n**3)
    M = np.zeros((n,n))
    for i in range(n):
        for j in range(n):
            M[i][j] = probapond(0,2,p)
##    plt.imshow(M,interpolation='none', cmap='gist_stern_r', norm = mpl.colors.Normalize(vmin=0.,vmax=2.))
##    plt.show()
    return(M)

##M = cree_grille(80,0.8)
def etat_case(M,i,j):
    n = len(M)
    if i >= 0 and j >= 0 and i < n and j < n:
        return M[i][j]
    else :
        return 2


def diffuse(M,a,b):
    n = len(M)
    L = [[-1,0],[0,-1],[1,0],[0,1]]
    if etat_case(M,a,b) == 0 :
        M[a][b] = 1
        for i in L:
            if etat_case(M,a+i[0],b + i[1]) ==0:
                diffuse(M,a+i[0],b + i[1])
        return M
    else :
        return M


def remplit(M):
    n = len(M)
    for i in range(n):
        diffuse(M,0,i)
        
##M2 = remplit(M)
##
##plt.imshow(M,interpolation='none', cmap='gist_stern_r', 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)


def Proba(p):
    P = 0
    for i in range(20):
        P = P + percolation(p,30)/20
    return P



##Lp = np.linspace(0,1,40)
##Y = [Proba(p) for p in Lp]
##plt.plot(Lp,Y)
##plt.show()
##