## Question 5

def etat_possible(t) -> bool :
    for i in range (len(t)-1) :

        if t[i] < t[i+1] :
            return False



    if t[len(t) - 1] < 0 :
        return False

    return True




































## Question 6

def coup_jouer(lj,coup) :
    i,j = coup
    for n in range(i,len(lj)) :
        lj[n] = min(j,lj[n])

    while lj[-1] == 0 :
        lj.pop()






















## Question 7

def coup_possible(t) :
    rep = []
    for k in range (len(t)) :
        for l in range (t[k]) :
            if k != 0 or l != 0 :
                rep.append((k,l))
    return rep

## Question 9
def est_fini1(t) :
    return t == [1]

def est_fini2(t) :
    return len(coup_possible) == 0


## Question 10








def construire_graphe(h,l) :
    pos_depart = [l for _ in range (h)] # A compléter
    pile = [(pos_depart,1)]
    dico_g = {}

    while pile != [] :
        plateau_explorer, joueur = pile.pop()
        joueur_suiv = joueur%2 + 1

        liste_voisin = []
        if (tuple(plateau_explorer), joueur) not in dico_g :
            for c in coup_possible(plateau_explorer) :
                plateau_suiv = plateau_explorer.copy()
                coup_jouer(plateau_suiv,c)
                liste_voisin.append((plateau_suiv,joueur_suiv))


                if not (tuple(plateau_suiv),joueur_suiv) in dico_g :
                    pile.append((plateau_suiv,joueur_suiv))

            # A compléter
            dico_g[(tuple(plateau_explorer), joueur)] = liste_voisin
    return dico_g






## Question 11
def est_gagnant(s0,g) :
    plateau, joueur = s0
    # Cas de base
    if len(g[s0]) == 0 :
        return joueur == 2

    else :
        if joueur == 1 :
            for pos,j in g[s0] :
                if est_gagnant((tuple(pos),j),g) :
                    return True
            return False

        else :
            for pos,j in g[s0] :
                if not  est_gagnant((tuple(pos),j),g) :
                    return False
            return True



## Question 12



d_mem = {}
def est_gagnant_mem(s0,g) :
    if s0 in d_mem :
        return d_mem[s0]
    plateau, joueur = s0
    # Cas de base
    if len(g[s0]) == 0 :
        d_mem[s0] = joueur == 2
        return joueur == 2


    else :
        if joueur == 1 :
            for pos,j in g[s0] :
                if est_gagnant_mem((tuple(pos),j),g) :
                    d_mem[s0] = True
                    return True
            d_mem[s0] = False
            return False

        else :
            for pos,j in g[s0] :
                if not est_gagnant_mem((tuple(pos),j),g) :
                    d_mem[s0] = False
                    return False
            d_mem[s0] = True
            return True