# -*- coding: utf-8 -*-
"""
Created on Sat Dec 10 11:56:16 2016

@author: alain
"""

from pylab import *
import sys
sys.setrecursionlimit(100000) 

#                       EXERCICE 1

# Question a

def occurence(L,a):  # Itératif : première version
    S=0
    for i in range(len(L)):
        if L[i]==a:
            S=S+1
    return S
    
def Occurence(L,a):  #  Itératif : deuxième version
    S=0
    for i in L:
        if i==a:
            S=S+1
    return S    

    
L=[1,2,3,4,5,6,7,6,5,4,3,2,1,5]  
n=Occurence(L,2) 
print(n)

def occurencebis(L,a):  #  Algorithme récursif
    if len(L)==0:
        return 0
    else:
        n=len(L)
        M=L[0:n-1]
        if L[n-1]==a:
            return occurencebis(M,a)+1
        else:
            return occurencebis(M,a)
        
L=[1,2,3,4,5,6,7,6,5,4,3,2,1,5]  
n=occurencebis(L,7) 
print(n)        

#                       EXERCICE 2
        
def suite(n):    #  Algorithme récursif avec une mauvaise complexité
    if n==0:
        return 2
    if n==1:
        return 1
    else:
        return 6*suite(n-1)+suite(n-2)  
        
def suitebis(n):   # Etude mathématiques : pour tout n, on a u_n = 3**n+(-2)**n
    return 3**n+(-2)**n
    
L=[suite(i) for i in range(8)]    
M=[suitebis(i) for i in range(8)] 
print(L)
print(M) 

def suite_bis(n):  #  Algorithme récursif avec une meilleure complexité
    if n==0:
        return [2,1]
    else:
        L=suite_bis(n-1)
        return [L[1],L[0]+6*L[1]]
        
print(suite(10))
print(suite_bis(10))      
 
#                       EXERCICE 3
        
# Question 2
        
def f(x):
    return x**3+x-5
    
x=linspace(1,2,100)
y=f(x)
plot(x,y)
show()

def dicho(epsilon):  #  Alagorithme itératif pour la dichotomie
    a=1
    b=2
    while b-a>epsilon:
        m=(a+b)/2
        if f(m)>=0:
            b=m
        else:
            a=m
    return (a+b)/2

c1=dicho(1.e-10) 
print(c1) 

def dichorec(a,b,epsilon): #  Alagorithme récursif pour la dichotomie
    if abs(a-b)<=epsilon:
        return (a+b)/2
    else:
        m=(a+b)/2
        if f(m)*f(a)>=0:
            return dichorec(m,b,epsilon)
        else:
            return dichorec(a,m,epsilon)
            
c2=dichorec(1,2,1.e-11) 
print(c2)

def fprime(x):
    return 3*x**2+1
    
def Newton(epsilon): # Algorithme de Newton, première version
    a=1
    while abs(f(a))>epsilon:
        a=a-f(a)/fprime(a)
    return a
    
def Newtonbis(epsilon): # Algorithme de Newton, seconde version
    a=1
    b=a-f(a)/fprime(a)
    while abs(b-a)>epsilon:
        a=b
        b=b-f(b)/fprime(b)
    return a    
    
c3=Newton(1.e-10) 
print(c3)   

c4=Newtonbis(1.e-10) 
print(c4)    
 
#                       EXERCICE 4
 
def f(t):
    return  1+exp(-t)*cos(8*t)
    
x1=linspace(0,7,1000)
y1=f(x1)
plot(x1,y1,color='red')
show()

close() 

def Euler(a,b,c,d,alpha,beta,h):  #  Méthode d'Euler
    T=[0,h]
    Y=[alpha,alpha+beta*h]
    n=2
    while n*h<=7:
        u=(2-b*h/a)*Y[n-1]+(-1+b*h/a-c*h**2/a)*Y[n-2]-d*h**2/a
        Y.append(u)
        v=T[n-1]+h
        T.append(v)
        n=n+1
    return T,Y
    


    
resultat=Euler(1,2,65,-65,2,-1,0.001)
x2=resultat[0]
y2=resultat[1]
plot(x2,y2,color='blue')
plot(x1,y1,color='red')
show()


    

#                       EXERCICE 5

#                       Question 1

def Indice(L):
    return 8*L[0]+L[1]

print(Indice([2,1]))
print('')

#                       Question 2

def Coord(n):
    i=n//8
    j=n%8
    return [i,j]
    
print(Coord(17))
print('')

#                       Question 3

def CasA(n):
    Deplacements=[[1,-2],[2,-1],[2,1],[1,2],[-1,2],[-2,1],[-2,-1],[-1,-2]]
    L=[]
    i,j=Coord(n)
    for d in Deplacements:
        u=i+d[0]
        v=j+d[1]
        if u>=0 and u<8 and v>=0 and v<8:
            L.append(Indice([u,v]))
    return L
    
print(CasA(0))
print(CasA(39))
print('')



#                       Question 4


def Init():
    global ListeCoups,ListeCA
    ListeCoups=[]
    ListeCA=[CasA(n) for n in range(64)]
        

 #                       Question 5
        
ListeCA=[[] for i in range(64)]
Init()
print(ListeCA[16])

#                       Question 6.1  



def OccupePosition(n):
    global ListeCoups,ListeCA
    ListeCoups.append(n)
    Res=False
    for k in ListeCA[n]:
        ListeCA[k].remove(n)
        if ListeCA[k]==[]:
            Res=True
    return Res
    
ListeCoups=[]
ListeCA=[[] for i in range(64)]
Init()
print(ListeCA[1])
OccupePosition(18)
print(ListeCA[1])




 #                       Question 6.2

def LiberePosition():
    global ListeCoups,ListeCA
    n=ListeCoups.pop()
    for k in ListeCA[n]:
        ListeCA[k].append(n)
            

ListeCA=[[] for i in range(64)]
Init()
print(ListeCA) 
print('')
OccupePosition(8)
print(ListeCA)    
print('')
LiberePosition()
print(ListeCA)        
    
  #                       Question 6.3
    
def TestePosition(n):
    global ListeCoups,ListeCA
    Test=OccupePosition(n)
    if Test:
        if len(ListeCoups)==64:
            return True
        else:
            LiberePosition()
            return False
    else:
        Local=[]
        for k in ListeCA[n]:
            Local.append(k)
        for k in Local:
            if TestePosition(k):
                return True
        LiberePosition()
        return False


ListeCoups=[]            
ListeCA=[[] for i in range(64)]
Init() 
print(TestePosition(0)) 
print(ListeCoups)