class Grille:
    
    global niveau_max
    niveau_max = 5
    
    def __init__(self):
        self.grille = [[0 for _ in range(7)] for _ in range(6)]
        
    def __str__(self):
        res = ""
        for ligne in self.grille:
            res += " ".join(str(x) for x in ligne) + "\n"
        return res
    
    def joue(self, colonne, joueur):
        ligne = 5 # on part de la rangée la plus basse
        while ligne!=-1 and self.grille[ligne][colonne]!=0:
            ligne -= 1
        if ligne != -1:
            self.grille[ligne][colonne] = joueur
            return True
        else:
            return False
        
    def score(self):
        score = 0
        for ligne in range(6):
            for colonne in range(7):
                joueur = self.grille[ligne][colonne]
                if joueur != 0:
                    alignements = valeur_case(ligne, colonne)
                    if joueur == 1:
                        score -= alignements
                    else:
                        score += alignements
        return score
    
    def gagnant(self):
        """Renvoie le numéro du joueur gagnant (1 ou 2) ou 0 s'il n'y a pas de gagnant."""
        directions = [
            (0, 1),   # horizontal
            (1, 0),   # vertical
            (1, 1),   # diagonal /
            (1, -1)   # diagonal \
        ]
        
        for dr, dc in directions:
            # Pour chaque direction, on vérifie s'il y a un alignement de 4 cases du même joueur
            for ligne in range(6):
                for colonne in range(7):
                    joueur = self.grille[ligne][colonne]
                    if joueur != 0:
                        count = 1
                        for k in range(1, 4):
                            r = ligne + k * dr
                            c = colonne + k * dc
                            if 0 <= r < 6 and 0 <= c < 7 and self.grille[r][c] == joueur:
                                count += 1
                            else:
                                break
                        if count >= 4:
                            return joueur
        return 0
    
    def copie_grille(self):
        nouvelle_grille = Grille()
        for ligne in range(6):
            for colonne in range(7):
                nouvelle_grille.grille[ligne][colonne] = self.grille[ligne][colonne]
        return nouvelle_grille

def valeur_case(ligne, colonne):
    """Renvoie le nombre d'alignements de 4 cases contenant la case (ligne, colonne) dans une grille de puissance 4 (6 lignes, 7 colonnes).

    Args:
        ligne (int): Numéro de la ligne de la case
        colonne (int): Numéro de la colonne de la case

    Returns:
        int: Nombre d'alignements de 4 cases contenant la case (ligne, colonne)
    """
    assert not(ligne < 0 or ligne > 5 or colonne < 0 or colonne > 6)
    
    count = 0
    directions = [
        (0, 1),   # horizontal
        (1, 0),   # vertical
        (1, 1),   # diagonal /
        (1, -1)   # diagonal \
    ]
    
    for dr, dc in directions:
        # Pour chaque direction, on compte les alignements possibles
        # On cherche toutes les positions où une ligne de 4 contient (ligne, colonne)
        
        for start in range(-3, 1):  # start peut être -3, -2, -1 ou 0
            ligne_start = ligne + start * dr
            colonne_start = colonne + start * dc
            
            # Vérifier que les 4 cases sont dans la grille
            if 0 <= ligne_start <= 5 and 0 <= colonne_start <= 6:
                ligne_end = ligne_start + 3 * dr
                colonne_end = colonne_start + 3 * dc
                
                if 0 <= ligne_end <= 5 and 0 <= colonne_end <= 6:
                    count += 1
    
    return count

class Noeud:
    def __init__(self, colonne):
        self.colonne = colonne
        self.score = 0
        self.suivants = []
    
    def colonne_score_min(self):
        colonne = self.suivants[0].colonne
        score = self.suivants[0].score
        for fils in self.suivants:
            if fils.score < score:
                score = fils.score
                colonne = fils.colonne
        return colonne, score
    
    def colonne_score_max(self):
        colonne = self.suivants[0].colonne
        score = self.suivants[0].score
        for fils in self.suivants:
            if fils.score > score:
                score = fils.score
                colonne = fils.colonne
        return colonne, score
    
    def calcule_score(self, niveau, joueur, grille):
        g = grille.gagnant()
        if g == 1:
            self.score = -(100 + 10 * (niveau_max - niveau)) 
        elif g == 2:
            self.score = 100 + 10 * (niveau_max - niveau)
        elif niveau == niveau_max:
            self.score = grille.score()
        else:
            for colonne in range(7):
                grille2 = grille.copie_grille()
                if grille2.joue(colonne, joueur):
                    nouveau_noeud = Noeud(colonne)
                    self.suivants.append(nouveau_noeud)
                    nouveau_noeud.calcule_score(niveau + 1, 3 - joueur, grille2)
            if joueur == 1:
                self.score = self.colonne_score_min()[1]
            else:
                self.score = self.colonne_score_max()[1]

def choisir_coup(grille, joueur):
    racine = Noeud(-1)  # la colonne n'est pas utilisée pour la racine
    racine.calcule_score(0, joueur, grille)
    if joueur == 1:
        return racine.colonne_score_min()[0]
    else:
        return racine.colonne_score_max()[0]

jeu1 = Grille()
jeu1.joue(2,1)
jeu1.joue(3,2)
jeu1.joue(3,1)
joueur = 2
for _ in range(35):
    print(jeu1)
    meilleur_coup = choisir_coup(jeu1, joueur)
    print("meilleur_coup =", meilleur_coup)
    jeu1.joue(meilleur_coup, joueur)
    joueur = 3 - joueur
    print("\n\n")