"""
--------------------------------------------------
-----------X2022 - grotte inondée-----------------
--------------------------------------------------
"""

#Vous pouvez utiliser les constantes D,B,G,H et la fonction
#liste_des_points comme indiqué dans le sujet (cf dessous)

#en bas de ce listing vous avez des fonctions de création 
#aléatoire, de représentation et de test visuel

#Voici également pour vos tests les deux exemples du sujet
D,B,G,H="D","B","G","H"
exVallee=[B,B,B,D,D,B,D,B,B,B,D,D,B,D,D,D,H,D,H,D,H,H,H,D,H,D,D,H]
exGrotte=[B,D,B,B,D,H,H,D,B,B,D,H,D,B,D,H,H,D,B,D,D,H,D,H]

     
"""----------version TP - résolution------------"""

#Q2
def est_une_vallee(g):
    if g[0]==H or g[len(g)-1]==B:
        return False
    phase_remontee=False
    for d in g:
        if d==G:
            return False
        elif d==H:
            phase_remontee=True
        elif d==B and phase_remontee:
            return False
    return True

#Q5, deux versions
def est_simple_v1(g):
    L=liste_des_points(g)
    n=len(L)
    for i in range(n):
        for j in range(i):
            if L[i]==L[j]:
                return False
    return True
            
def est_simple_v2(g):
    L=liste_des_points(g)
    dicoPts=dict()
    for p in L:
        if p in dicoPts:
            return False
        else:
            dicoPts[p]=True
    return True

#Q6
def fond(v):
    L=liste_des_points(v) 
    posMin=0
    i=0
    while i<len(v) and v[i]!=H:
        if v[i]==B:
            posMin=i+1
        i+=1
    return L[posMin]
    
#Q7
def plateaux(v): 
    liste_plateaux=[]
    L=liste_des_points(v)
    i=0
    while i<len(v):
        if v[i]==D:
            j=1
            while i+j<len(v) and v[i+j]==D:
                j+=1
            liste_plateaux.append((L[i][0],L[i+j][0],L[i][1]))
            i+=j
        else:
            i+=1
    return liste_plateaux

#Q8
def decomposition_en_rectangles(v):
    (x,y)=fond(v)
    LP=plateaux(v)
    rect=[]
    i1=0
    while LP[i1][0]!=x:
        i1+=1
    i2=i1
    while i1>0 or i2<len(LP)-1:
        largeur=LP[i2][1]-LP[i1][0]
        if i1==0:
            newy=LP[i2+1][2]
            i2+=1
        elif i2==len(LP)-1:
            newy=LP[i1-1][2]
            i1-=1
        else:
            if LP[i1-1][2]>LP[i2+1][2]:
                newy=LP[i1-1][2]
                i1-=1            
            elif LP[i1-1][2]<LP[i2+1][2]: 
                newy=LP[i2+1][2]
                i2+=1
            else:
                newy=LP[i2+1][2]
                i2+=1
                i1-=1
        rect.append((largeur,y-newy))
        y=newy
    rect.append((LP[i2][1]-LP[i1][0],-1))
    return rect

#Q9
def hauteur_de_l_eau(t,v):
    R=decomposition_en_rectangles(v)
    vol=t
    h=0
    i=0
    while i<len(R)-1 and vol>R[i][0]*R[i][1]:
        vol-=R[i][0]*R[i][1]
        h+=R[i][1]
        i+=1
    return h+vol/R[i][0]

#Q10
def hierarchie_rectangles(g):
    pile=[]
    origine=[]
    largeur=[]
    parent=[]
    enfants=[]
    x,y=0,0
    numero=-1
    for d in g:
        if d==D:
            x+=1
        elif d==B:
            y+=1
            numero+=1
            origine.append((x,y))
            largeur.append(-1)
            enfants.append([])
            if len(pile)>0:
                pere=pile[len(pile)-1]
                enfants[pere].append(numero)
            else:
                pere=-1
            parent.append(pere)
            pile.append(numero)
        else: #forcément d==H
            y-=1
            numeroFermant=pile.pop()
            x0=origine[numeroFermant][0]
            largeur[numeroFermant]=x-x0
    return origine,largeur,parent,enfants
           
#'jai considéré parent inutile car le seuls intérêt est de trouver le sans parent qui est numéro 0
            
def complete_listeR(listeR,actuel,enfants):
    for i in enfants[actuel]: #appelle fils d'abord
        complete_listeR(listeR,i,enfants)
    listeR.append(actuel)

def ordre_remplissage_depuis_origine(parent,enfants):
    listeR=[] #parent inutile
    complete_listeR(listeR,0,enfants)
    return listeR

def hauteurs_eau_depuis_origine(t,largeur,parent,enfants):
    nbR=len(largeur)
    listeR=ordre_remplissage_depuis_origine(parent,enfants)
    print(listeR)
    hauteur=[0.0 for i in range(nbR)]
    vol=t
    i=0
    while i<len(listeR)-1 and vol>largeur[listeR[i]]:
        vol-=largeur[listeR[i]]
        hauteur[listeR[i]]=1.0
        i+=1
    if vol>0:
        hauteur[listeR[i]]=vol/largeur[listeR[i]]        
    return hauteur

def volume_sous(i,enfants,vol,largeur):
    V=largeur[i]
    for j in enfants[i]:
        V+=volume_sous(j,enfants,vol,largeur)
    vol[i]=V
    return V

def volumes_totaux(largeur,parent,enfants):
    nbR=len(largeur)
    vol=[0.0 for i in range(nbR)]
    volume_sous(0,enfants,vol,largeur)
    return vol



"""
------- objets prédéfinis dans le sujet--------
"""

def voisin(x,y,d):
    if d==D:
        return (x+1,y)
    elif d==G:
        return (x-1,y)
    elif d==H:
        return (x,y-1)
    return (x,y+1)
    
def liste_des_points(g):
    x,y=(0,0)
    pos=[(x,y)]
    for d in g:
        (x,y)=voisin(x,y,d)
        pos.append((x,y))
    return pos


"""
------- fonctions utilitaires pour les tests--------
"""

import numpy.random as rd
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle

def vallee_hasard(taille):
    """crée une vallée au hasard. Choix effectués : 
    - une transition aléatoire entre descente et montée
    entre le 1/3 et le 2/3 de la largeur
    - dans chaque phase 50% horizontal vs vertical"""
    v=[D for i in range(taille)]
    choixFond=taille//3+int(rd.random()*taille/3)
    for i in range(taille):
        if rd.random()<0.5:
            if i>choixFond:
                v[i]=H
            elif i<choixFond: # si ==choixFond laisse D
                v[i]=B
    return v

def grotte_hasard(taille):
    """crée une grotte à ciel ouvert au hasard
    puis la normalise (elle dépasse donc taille)"""
    g=[D for i in range(taille)]
    for i in range(1,taille-1):
        p=rd.random()
        if i==0 or g[i-1]==D:
            if p<1/3:
                g[i]=H
            elif p<2/3:
                g[i]=B
        else:
            if p<1/2:
                g[i]=g[i-1]
    #normalisation
    L=liste_des_points(g)
    yM=min([L[i][1] for i in range(1,len(L)-1)])
    yf=L[len(L)-1][1]
    if yf>0:
        g=g+[H for i in range(yf)]
    if yf<0:
        g=[B for i in range(-yf)]+g
        yM=yM-yf
    if yM<=0:
        g=[B for i in range(-yM+1)]+g+[H for i in range(-yM+1)]
    return g


def trace_profil(g):
    L=liste_des_points(g)
    X=[p[0] for p in L]
    Y=[-p[1] for p in L]
    plt.plot(X,Y,'--')

def teste_vallee(v):
    """test visuel représente le fond et les plateaux."""
    trace_profil(v)
    pos_fond=fond(v)
    plt.plot([pos_fond[0]],[-pos_fond[1]],"o")
    LP=plateaux(v)
    for p in LP:
        plt.plot([p[0],p[1]],[-p[2],-p[2]],'r')
    plt.show()

def teste_grotte_source_origine(t,g):
    """Test visuel :
    représente le résultat de l'algorithme de remplissage"""
    origine,largeur,parent,enfants=hierarchie_rectangles(g)
    haut=hauteurs_eau_depuis_origine(t,largeur,parent,enfants)
    listeR=ordre_remplissage_depuis_origine(parent,enfants)
    nbR=len(haut)    
    trace_profil(g)
    plt.plot([0],[0],'ro')
    currentAxis = plt.gca()
    for i in range(nbR):
        r=listeR[i]
        h=haut[r]
        if h>0:
            x,y=origine[r]
            l=largeur[r]
            currentAxis.add_patch(Rectangle((x,-y), l,h))
    plt.show()