#------------------fonctions d'exploration de l'arbre------------
    
def parcoursSigne(arbre,noeud,signe):
    pass
    
    
def minMax(arbre,noeud,signe):
    pass

def affichePoids(arbre):
    for clef in arbre:
        print(clef,arbre[clef][0])
        
#-------------------puissance 4 : fonctions de base----------

HAUTEUR=6
LARGEUR=7

def grilleP4():
    return[[0 for i in range(LARGEUR)] for i in range(HAUTEUR)]
        
def symbole(s):
    if s==0:
        return " "
    else: 
        return str(s)
        
def afficheLigne(l,separateur,debut,fin):
    str=debut+separateur.join(l)+fin
    print(str)
    
def afficheGrille(g):
    ligneH=u"\u2500"*LARGEUR
    for i in range(len(g)-1,-1,-1):
        ligne=[symbole(x) for x in g[i]]
        afficheLigne(ligne,u"\u2502",u"\u2502",u"\u2502")
        if i>0:
            afficheLigne(ligneH,u"\u253C",u"\u251C",u"\u2524")
    afficheLigne(ligneH,u"\u2534",u"\u2514",u"\u2518")
    
def estPleine(grille,col):
    return grille[HAUTEUR-1][col]!=0
        
def dansLaGrille(l,c):
    return (l>=0 and c>=0 and l<HAUTEUR and c<LARGEUR)
    
def premierLibre(grille,col):
    """renvoie l'indice de la première case libre dans la colonne
    en partant de la ligne du bas (indice 0)
    Ne sera utilisé que pour une colonne non pleine : 
    pas besoin de le tester ici"""
    pass
    
def ajouterPion(grille,joueur,col):
    """ajoute un pion portant le numéro du joueur=1 ou 2
    dans la colonne col.
    Si la colonne est pleine,déclenche un erreur"""
    pass   
    
def debutJeu(listeCoups):
    """en entrée : uneliste de numéros de colonnes.
    La fonction crée une grille, la remplit et la renvoie
    Le remplissage se fait enconsidérant que les joueurs 1 et 2
    jouent alternativement dans les colonnes indiquées (1 commence)"""
    pass

#------------------estimation de la valeur --------
    
def nbAlignes(grille,l,c,dl,dc,joueur):
    """compte combien de pions successifs portent la couleur du joueur
    dans une direction donnée"""
    cpt=1
    l1=l+dl
    c1=c+dc
    while dansLaGrille(l1,c1) and grille[l1][c1]==joueur:
        l1=l1+dl
        c1=c1+dc
        cpt+=1
    return cpt
    
def coupFatal(grille,l,c,joueur):
    """renvoie True si placer un jeton en position (l,c) termine
    un alignement de 4, False sinon"""
    if nbAlignes(grille,l,c,-1,0,joueur)>3:
        return True
    if nbAlignes(grille,l,c,0,1,joueur)+nbAlignes(grille,l,c,0,-1,joueur)>4:
        return True
    if nbAlignes(grille,l,c,1,1,joueur)+nbAlignes(grille,l,c,-1,-1,joueur)>4:
        return True
    if nbAlignes(grille,l,c,-1,1,joueur)+nbAlignes(grille,l,c,1,-1,joueur)>4:
        return True
    return False

def nbLibresParmi3(grille,l,c,dl,dc,adversaire):
    """renvoie un score de 1,2,3 selon le nombre de cases utilisables 
    pour un futur alignement dans une direction donnée"""
    cpt=0
    l1=l+dl
    c1=c+dc
    while cpt<3 and dansLaGrille(l1,c1) and grille[l1][c1]!=adversaire:
        l1=l1+dl
        c1=c1+dc
        cpt+=1
    return cpt
    
def positionsLibresDirection(grille,l,c,dl,dc,adversaire):
    """utilise le précédent, pour donner un score en regardant des deux côtés"""
    val=nbLibresParmi3(grille,l,c,dl,dc,adversaire)
    val+=nbLibresParmi3(grille,l,c,-dl,-dc,adversaire)
    if val<2:
        return 0
    return val-2

        
def valeurCoup(grille,col,joueur):
    """c'est l'heuristique"""
    ligne=premierLibre(grille,col)
    adversaire=3-joueur
    if coupFatal(grille,ligne,col,joueur):
        return float("inf")
    val=positionsLibresDirection(grille,ligne,col,0,1,adversaire)
    val+=positionsLibresDirection(grille,ligne,col,1,1,adversaire)
    val+=positionsLibresDirection(grille,ligne,col,1,-1,adversaire)
    val+=positionsLibresDirection(grille,ligne,col,1,0,adversaire)
    return val


#------------------Détermination du coup à jouer --------

def coupsPossibles(grille):
    """renvoie la liste des coups possibles,
    c'est-à-dire des colonnes pas encore pleines"""
    pass  

def enleverPion(grille,col):
    assert grille[0][col]!=0
    if estPleine(grille,col):
        lg=HAUTEUR-1
    else:
        lg=premierLibre(grille,col)-1
    grille[lg][col]=0
        
def analyse(grille,profondeur,signe,joueur):
    pass
    
def partieAuto(profondeur,nbCoups,listeCoups=[]):
    pass
        

#------------------fonctions de création de l'arbre------------
    
def creerArbre(hauteur,nbFils,valeurs):
    arbre=dict()
    lettre=65
    nombreCases=1
    for h in range(hauteur-1):
        for n in range(nombreCases):
            code=chr(lettre+h)+str(n)
            lesFils=[]
            for i in range(nbFils):
                codeFils=chr(lettre+h+1)+str(nbFils*n+i)
                lesFils.append(codeFils)
            arbre[code]=[None,lesFils]
        nombreCases*=nbFils
    for n in range(nombreCases):
        code=chr(lettre+hauteur-1)+str(n)
        arbre[code]=[valeurs[n],[]]
    return arbre

listeVal=[-5,2,-3,4,8,9,-1,2,3,7,2,6,4,1,0,-2,0,-2,3,1,-2,4,2,1,5,3,3]
arbre=creerArbre(4,3,listeVal)
       

#--------exemples de commandes----------------

#parcoursSigne(arbre,"A0",1)
#minMax(arbre,"A0",1)
#affichePoids(arbre)