from random import *
import math,statistics


###########
###########   Fonctions utilisées pour le premier algo (on met la plus grande crêpe au sommet)
###########
def deplacement1():
    """cette fonction renverse tout le paquet de crêpes car la crêpe située au-dessus est la plus grande"""
    global nbrenv,longEnHaut
    nbrenv=nbrenv+1
    lcp.reverse()
    lcpep.append(lcp[0])
    del lcp[0]
    longEnHaut = False
    deplacement()

def deplacement():
    """cette fonction identifie la crêpe la plus grande parmi celles qui restent et la renverse avec celles qui sont au-dessus
    de sorte que la plus grande se retrouve au sommet de la pile"""
    global nbrenv,longEnHaut,listeRetournementCas1 ##longEnHaut sert à savoir si la plus grande crêpes (parmi celles qui restent à trier) est en haut
    if len(lcp)!=0:
        pmax=lcp.index(max(lcp))
        if pmax!=0:
            nbrenv=nbrenv+1
            a=lcp[pmax:]
            a.reverse()
            for i in range(pmax,len(lcp)):
                lcp[i]=a[i-pmax]
            longEnHaut = True
            deplacement1()
        else:
            lcpep.append(lcp[0])
            del lcp[0]
            deplacement()
            longEnHaut = False
    else:
        #textper="nombre de renversement "+str(nbrenv)+" pour "+str(nbcrp)+" crêpes."
        #print(textper)
        listeRetournementCas1.append(nbrenv)
        




###########
###########   Cette autre partie est pour la deuxième méthode de retournement des crêpes
###########
def indiceSupInf(l,nb):
    """l est une liste de nombres
    nb est un nombre
    cette fonction renvoie l'indice du plus petit nombre strictement supérieur ou inférieur à nb
    si nb est le max, alors elle renvoie inf pour val max et si nb est la valeur min, elle renvoie -1 pour min"""
    indMin,indMax=-1,-1
    nbMax,nbMin = float('inf'),-1
    #print("l:",l)
    for i in range(len(l)):
        if(nb<l[i]<nbMax):
            nbMax,indMax=l[i],i
        elif(nbMin<l[i]<nb):
            nbMin,indMin=l[i],i
    return indMax,indMin


def deplacementBis():
    """cette fonction identifie la crêpe à retourner suivant 3 critères consécutifs (corrigés pour perdre l'avantage de ce qui aurait été fait)"""
    global nbrenv,longEnHaut,pas,jeuLance,listeRetournementCas1 ##longEnHaut sert à savoir si la plus grande crêpes (parmi celles qui restent à trier) est en haut
    if jeuLance:
        if len(lcp)!=0:
            #On cherche l'indice à partir duquel on va renverser la pile
            pmax,pmin = indiceSupInf(lcp,lcp[-1])
            indiceRetournement = -1
            if pmax==-1:
                #C'est que la plus grande des crêpes à replacer est en haut (donc on retrounera la pile)
                indiceRetournement = len(lcp)
            elif pmax!=len(lcp)-2:
                #la crêpe juste plus grande que celle du sommet n'est pas en position 2, alors on se place juste au-dessus de cette plus grande crêpe
                #On évite tout de même de faire ceci si cela sépare deux crêpes qui doivent être l'une sur l'autre à la fin
                if(abs(lcp[pmax+1]-lcp[pmax]-pas)<math.pow(10,-7)):
                    #On choisit autre chose dans ce cas là
                    #On regarde alors du côté du min avec la même mise en garde
                    if((abs(lcp[pmin]-lcp[pmin+1]-pas)<math.pow(10,-7)) or (pmin==len(lcp)-2)):
                        #je choisis donc de prendre la plus grande crêpe
                        indiceRetournement = lcp.index(max(lcp))
                    else :
                        indiceRetournement = pmin+1
                else :
                    indiceRetournement = pmax+1
            else :
                #la crêpe située en position 2 sur la pile est dans ce cas juste celle qui est plus grande que celle du sommet,
                #donc on cherche la position de la crêpe juste plus petite que celle du sommet et on effectue le retournement au-dessus de cette dernière
                #Je prends les même dispositions que pour le pmax
                if(abs(lcp[pmin]-lcp[pmin+1]-pas)<math.pow(10,-7)):
                    #je choisis donc de prendre la plus grande crêpe
                    indiceRetournement = lcp.index(max(lcp))
                elif pmin==-1:
                    #dans ce cas aussi je prends la plus grande crêpe que je mets dessus
                    indiceRetournement = lcp.index(max(lcp))
                else :
                    indiceRetournement = pmin+1
            if indiceRetournement!=len(lcp):#c'est que celle du dessus n'est pas la plus grande des crêpes restantes
                nbrenv=nbrenv+1
                a=lcp[indiceRetournement:]
                a.reverse()
                for i in range(indiceRetournement,len(lcp)):
                    lcp[i]=a[i-indiceRetournement]
                longEnHaut = False
                deplacementBis()
            else:
                lcp.reverse()
                while (len(lcp)>1 and abs(lcp[0]-lcp[1]-pas)<math.pow(10,-8)):
                    lcpep.append(lcp[0])
                    del lcp[0]
                lcpep.append(lcp[0])
                del lcp[0]
                nbrenv=nbrenv+1
                deplacementBis()
        else:
            #textper="nombre de renversement "+str(nbrenv)+" pour "+str(nbcrp)+" crêpes."
            #print (textper)
            listeRetournementCas2.append(nbrenv)
    else :
        jeuLance = True
        #Si des crêpes sont bien placées, alors on les décompte
        if(lcp[0]==max(lcp)):
            while (len(lcp)>1 and abs(lcp[0]-lcp[1]-pas)<math.pow(10,-8)):
                lcpep.append(lcp[0])
                del lcp[0]
            lcpep.append(lcp[0])
            del lcp[0]
        deplacementBis()



###################################Variables pour le lancement et la construction de la zone
nbrenv=0 #nombre de renversement de la pile de crêpes
nbcrp=10 # nombre de crêpes
pmax=nbcrp #position de la crêpe de taille max (utilisée dans la fonction déplacement)

nbTest = 1000


jeuLance = False
longEnHaut = False

    


##########################
########################## lancement des différents tests pour les 2 cas de figure
##########################

listeRetournementCas1 = []
listeRetournementCas2 = []

lcpInit = []
lcpMelange = []
pas =1
for i in range(nbcrp):
    lcpInit.append(50+pas*i)
#lcpInit = range(1,nbcrp+1)   
for k in range(nbTest):
    nbrenv=0
    lcpMelange=lcpInit.copy() #liste des crêpes non correctement placée (en rouge dansla version graphique)
    shuffle(lcpMelange)
    
    lcp = lcpMelange.copy()
    lcpep=[] #liste des crêpes bien placées (en vert dans la version graphique)
    deplacement()
    nbrenv=0
    lcp=lcpMelange.copy() 
    lcpep=[] #liste des crêpes bien placées (en vert dans la version graphique)
    deplacementBis()


#print("Dans le cas 1:",listeRetournementCas1," et en moyenne:",statistics.mean(listeRetournementCas1)/nbcrp)
#print("Dans le cas 2:",listeRetournementCas2," et en moyenne:",statistics.mean(listeRetournementCas2)/nbcrp)

print("Dans le cas 1 en moyenne:",statistics.mean(listeRetournementCas1))
print("Dans le cas 2 en moyenne:",statistics.mean(listeRetournementCas2))
