E08 - Puissance 4

Le problème

Puissance 4

Proposition 1

🐍 Script Python

def puissance4(table_puissance4: list) -> int:
    """Cette fonction prend en paramètre un tableau d'entiers à deux dimensions contenant 42 cases
    (6 lignes, 7 colonnes). Une case de ce tableau contient soit 0 (case vide) soit 1 (pion jaune), soit 2 (pion rouge). 
    Et doit renvoyer 1 ou 2 s'il y a un alignement de 4 pions et 0 si personne n'a gagné.
    >>> 0010000
        0022000
        0121000
        0221000
        2212100
        1211210
    2
    """
    for x in range(6):
        for n in range(4):
            ## Vérif horizontale ##
            if table_puissance4[x][n] == table_puissance4[x][n+1] == table_puissance4[x][n+2] == table_puissance4[x][n+3]:
                if table_puissance4[x][n] == 0:
                    pass
                else:
                    return table_puissance4[x][n]
            ## Vérif verticale ##
            elif table_puissance4[n][x] == table_puissance4[n+1][x] == table_puissance4[n+2][x] == table_puissance4[n+3][x]:
                if table_puissance4[x][n] == 0:
                    pass
                else:
                    return table_puissance4[x][n]
                ## Vérif diagonale droite gauche ##
                elif table_puissance4[x][n] == table_puissance4[x+1][n+1] == table_puissance4[x+2][n+2] == table_puissance4[x+3][n+3]:
                    if table_puissance4[x][n] == 0:
                        pass
                    else:
                        return table_puissance4[x][n]
                ## Vérif diagonale gauche droite ##
                elif table_puissance4[x][6-n] == table_puissance4[x+1][5-n] == table_puissance4[x+2][4-n] == table_puissance4[x+3][3-n]:
                    if table_puissance4[x][n] == 0:
                        pass
                    else:
                        return table_puissance4[x][n]
                else:
                return 0
# tests 
import doctest
doctest.testmod()

# Entrée
table_puissance4 = [input() for _ in range(6)]

# Sortie
print(puissance4(table_puissance4))

• Erreur d'indentation et dans le doctest, entre autres.
• else pass à éviter.
• Toutes les cases ne sont pas testées en vertical.
• Mauvaise idée d'utiliser n et x et de les intervertir.
• On pouvait travailler avec des str plutôt que des int dans ce problème.

Proposition 2

🐍 Script Python

def Puissance_4(grille:list) -> int:
    """ Renvoie le gagnant 1 pour le joueur 1 ou 2 pour le joueur 2 si il arrive à aligné 4 pions identitique,sinon 0 en cas d'égalité
    >>> Puissance_4([[0, 0, 1, 0, 0, 0, 0], [0, 0, 2, 2, 0, 0, 0], [0, 1, 2, 1, 0, 0, 0], [0, 2, 2, 1, 0, 0, 0], [2, 2, 1, 2, 1, 0, 0], [1, 2, 1, 1, 2, 1, 0]])
    2
    """
    # Toutes les directions possibles 
    directions = [(1, 0), (0, 1), (1, 1), (1, -1),(-1,-1),(-1,1),(-1,0),(0,-1)]

    def est_possible(x:int, y:int) -> bool:
        """ Regarde si le déplacement est possible sur une grille 6*7
        >>> est_possible(3, 7)
        False
        >>> est_possible(2, 4)
        True
        """
        return (0 <= y < 6) and (0 <= x < 7)

    def recherche_gagnant(x:int, y:int, direction_y:int, direction_x:int) -> int:
        """ Recherche et affiche un joueur si il a réussi à aligné ses pions sur 4 cases à la suite dans chaque direction sinon il affiche 0
        >>> recherche_gagnant(5, 3, 1, 0)
        0
        """
        joueur = grille[y][x]
        for _ in range(1, 4):
            y += direction_y
            x += direction_x
            if not(est_possible(x, y)) or (grille[y][x] != joueur):
                    return 0
        return joueur

    for y in range(6):
        for x in range(7):
            if grille[y][x] != 0:
                for direction_y, direction_x in directions:
                    joueur = recherche_gagnant(x, y, direction_y, direction_x)
                    if joueur != 0:
                        return joueur
    return 0

# tests
import doctest
doctest.testmod()

# Entrée
grille = []
for x in range(6):
    grille.append(list(map(int,input())))

# Sortie
print(Puissance_4(grille))

• Beaucoup de bonnes choses. Bien.
• 4 directions suffisaient à être testées, au lieu de 8.
• La ligne if not(est_possible(x, y)) or (grille[y][x] != joueur): utilise de l'évaluation paresseuse ! C'est bien. Si le premier test est_possible(x, y) est False, alors sa négation est True, dans ce cas True or ... n'évalue pas le second opérande. Ainsi grille[y][x] ne provoque pas d'erreur. C'est bien !
• On pouvait simplifier le code, en ne testant que le plus éloigné des 4 pions, au lieu des trois suivants.

Proposition 3

🐍 Script Python

nb_lignes = 6
nb_colonnes = 7

plateau = [[0 for _ in range(nb_colonnes)] for _ in range(nb_lignes)]

for ligne in range(nb_lignes):
    entrée_str = list(input())
    entrée = list(map(int, entrée_str))
    for colonne in range(nb_colonnes):
        plateau[ligne][colonne] = entrée[colonne]

directions = [(-1,1),(0,1),(1,1),(1,0)]

def est_dans_le_plateau(ligne, colonne):
    """
    Retourne un booléen si les coordonnées (`ligne`,`colonne`) est
    dans le plateau
    """
    if (ligne < 0) or (ligne >= nb_lignes) or (colonne < 0) or (colonne >= nb_colonnes):
        return False
    return True

gagnant = 0

for ligne in range(nb_lignes):
    for colonne in range(nb_colonnes):
        if gagnant != 0:
            break
        joueur = plateau[ligne][colonne]
        if joueur != 0:
            for direction in directions:
                ligne_temporaire = ligne
                colonne_temporaire = colonne
                alignés = 1
                for _ in range(3):
                    ligne_temporaire += direction[0]
                    colonne_temporaire += direction[1]
                    if est_dans_le_plateau(ligne_temporaire, colonne_temporaire):
                        if(plateau[ligne_temporaire][colonne_temporaire] == joueur):
                            alignés += 1
                if alignés == 4:
                    gagnant = joueur
print(gagnant)

• « Retourne un booléen si (...) », mieux : « Retourne le booléen True si (...) »
• Le break peut presque toujours être évité en créant... une fonction.
• En créant plusieurs fonctions, on peut faire de nombreux renvois prématurés. Au lieu de vérifier si on a 4 alignés à la fin, on peut, en cours de vérification, renvoyer « pas de gagnant ici pour l'instant » ; c'est une bonne pratique. On doit morceler son code en fonction élémentaire.

Proposition 4

🐍 Script Python

def puissance_4(nb_lignes: int, nb_colonnes: int , grille: list) -> int:
    """Renvoie le vainqueur ou non du puissance 4.
    >>> puissance_4(6, 7, [[0, 0, 1, 0, 0, 0, 0], [0, 0, 2, 2, 0, 0, 0], [0, 1, 2, 1, 0, 0, 0], [0, 2, 2, 1, 0, 0, 0], [2, 2, 1, 2, 1, 0, 0], [1, 2, 1, 1, 2, 1, 0]])
    2
    """
    sens = [(1, 0), (0, 1), (1, 1), (1, -1)]

    def dans_grille(lig, col):
        return (0 <= lig < nb_lignes) and (0 <= col < nb_colonnes)

    def vérifie(lig, col, diff_lig, diff_col):
        pions = grille[lig][col]
        for _ in range(1, 4):
            lig += diff_lig
            col += diff_col
            if not(dans_grille(lig, col)) or (grille[lig][col] != pions):
                    return 0
        return pions

    for lig in range(nb_lignes):
        for col in range(nb_colonnes):
            if grille[lig][col] != 0:
                for diff_lig, diff_col in sens:
                    pions = vérifie(lig, col, diff_lig, diff_col)
                    if pions != 0:
                        return pions
    return ""

# Test
import doctest
doctest.testmod()

# Entrée
nb_colonnes = 7
nb_lignes = 6
grille = [list(map(int, input())) for _ in range(6)]

# Sortie 
print(puissance_4(nb_lignes, nb_colonnes, grille))

• Beaucoup de bonnes choses.
• Utiliser de meilleurs identifiants. lig et col, c'est un mauvais style.
• Le return "" devrait être un return 0, en cas de match nul.

Proposition 5

🐍 Script Python

def puissance_4(matrice_jeu):
    """ trouve le gagnon 1 ou 2 si égaliter affiche 0"""
    cologne = 0
    gagnent_est = 0
    ligne = 0


    def lit_horizontalement(cologne: int, gagnent_est: int):
        """ sa lit horizantalement le jeu"""
        vérifie_gagnent = 0 # si vérifie_gagnant est égale a 3, on a un gagnent
        for z in range (5): #car il y a 6 cologne mais on va prendre un facteur +1 sur la matrice 
            if matrice_jeu[z][cologne] != 0 and matrice_jeu[z][cologne] == matrice_jeu[z + 1][cologne] :
                vérifie_gagnent += 1 
            else:
                vérifie_gagnent = 0
            if vérifie_gagnent == 3:
                gagnent_est = matrice_jeu[z][cologne]
        if gagnent_est == 1 or gagnent_est == 2:
            return gagnent_est
        else:
            if cologne < 5:
                return lit_horizontalement(cologne + 1 , gagnent_est)
            else :
                None


    def lit_verticalement(cologne: int, gagnent_est: int):
        vérifie_gagnent = 0 # si vérifie_gagnant est égale a 3, on a un gagnent
        for y in range(6)  : #car il y a 7 ligne mais on va prendre un facteur +1 sur la matrice 
            if matrice_jeu[cologne][y] != 0 and matrice_jeu[cologne][y] == matrice_jeu[cologne][y + 1]: # erreur out of range mais je comprend pas où car si la bouvle fait 4 tour il est quand meme out 
                vérifie_gagnent += 1
            else:
                vérifie_gagnent = 0
            if vérifie_gagnent == 3: 
                gagnent_est = matrice_jeu[cologne][y]
        if gagnent_est == 1 or gagnent_est == 2:
            return gagnent_est
        else:
            if cologne < 5 :
                return lit_verticalement(cologne + 1, gagnent_est)
            else:
                None

    """
    def lit_diagonalement(cologne: int, ligne: int, gagnent_est: int):
        est la je suis bloquer
    """
    lit_horizontalement(cologne, gagnent_est)
    if gagnent_est == 1 or gagnent_est == 2:
        return gagnent_est
    else:
        cologne = 0
        lit_verticalement(cologne, gagnent_est)
        if gagnent_est == 1 or gagnent_est == 2:
            return gagnent_est
        else:
            """
            cologne = 0
            lit_diagonalement(cologne, ligne)
            if gagnent_est == 1 or gagnent_est == 2:
                return gagnent_est
            else :
            """   
            return "0" 


matrice_jeu = [] 
for x in range(6):
    matrice_jeu.append(input())
print(puissance_4(matrice_jeu))
""" il se peut qu'il aurai un probleme de rapiditer et on plus je vois pas commen lire ma diagonal"""

• Il vaut mieux mettre des parenthèses aux tests composés comme (...) and (...) and (...), pour confirmer les priorités opératoires, et faciliter la lecture pour un tiers.
• Le code est très peu clair, on ne comprend pas pourquoi il y a des appels récursifs (en particulier)...
• Mais il a le mérite d'être découpé en fonctions ; c'est bien.

Proposition 6

🐍 Script Python

# 0- Coeur du programme

def est_dans_la_grille(i: int, j: int) -> bool:
    """ Renvoie True si le curseur i,j est dans la grille
    >>> est_dans_la_grille(0, 0)
    True
    >>> est_dans_la_grille(-1, 7)
    False
    """

    #La grille à une taille de 6*7 
    if 0 <= i <= 5 and 0 <= j <= 6: 
        return True
    else:
        return False

def déterminer_gagnant(tableau: list) -> int:
    """ détermine si l'un des joueur a gagné la partie. Renvoie 1 ou 2 selon les pions gagnant et 0 si personne n'a gagné
    >>> déterminer_gagnant(["0000000", "0000000", "0000000", "0000000", "0000000", "0000000"])
    '0'
    >>> déterminer_gagnant(["0010000", "0022000", "0121000", "0221000", "2212100", "1211210"])
    '2'
    """

    # Chaque combinaison correspond à une direction à tester, dans l'ordre on a : 
    # Bas, Droite, Gauche, Haut, Diagonale(Bas/Droite), Diagonale(Haut/Gauche), Diagonale(Bas/Gauche), Diagonale(Haut/Droite)
    combinaison = [(0,1),(1,0),(0,-1),(-1,0),(1,1),(-1,-1),(1,-1),(-1,1)]
    for i in range(6):                                  # Ensuite, pour chaque case de la grille
        for j in range(7):
            if tableau[i][j] != "0":                    # ayant un pion (!= 0)
                for x,y in combinaison:                 # on test pour chaque direction
                    if est_dans_la_grille(i+x*3,j+y*3): # s'il existe une case à 3 pîons de i,j , c'est à dire qui se trouve dans la grille
                                                        # et si cette ligne est constituée uniquement du même pion (1 ou 2)
                        if tableau[i][j] == tableau[i+x][j+y] == tableau[i+x*2][j+y*2] == tableau[i+x*3][j+y*3]:
                            return tableau[i][j]        # Si oui, on renvoie le numéro du gagnant
    return "0"                                          # Si, à la fin, on a trouvé aucunes combinaisons créant une ligne de 4 pions identiques, on renvoie 0

# 1- Tests

import doctest
doctest.testmod()

# 2- Lecture de l'entrée

grille = [input() for _ in range(6)]

# 3- Appel de la fonction / Sortie

print(déterminer_gagnant(grille))

• return (0 <= i <= 5) and (0 <= j <= 6) est mieux pour est_dans_grille.
• Attention aux lignes trop longues.
  • On peut mettre les commentaires sur la ligne précédente.
  • On peut partager une ligne qui a une parenthèse ouverte (ou bien un crochet, ou une accolade), ou alors, en dernier recours, utiliser la contre-oblique. Revoir le cours à ce sujet.

Corrigé du professeur

🐍 Script Python

"""
author : Franck CHAMBON
problem: https://prologin.org/train/2003/semifinal/puissance_4
"""

def gagnant_puissance_4(grille: list[str]) -> str:
    """Renvoie le gagnant au jeu de Puissance 4.
    '0' désigne une case vide, et aussi un match nul.

    >>> l_1 = "0010000"
    >>> l_2 = "0022000"
    >>> l_3 = "0121000"
    >>> l_4 = "0221000"
    >>> l_5 = "2212100"
    >>> l_6 = "1211210"
    >>> grille = [l_1, l_2, l_3, l_4, l_5, l_6]
    >>> gagnant_puissance_4(grille)
    '2'

    """
    def est_dans_grille(i: int, j: int) -> bool:
        return (0 <= i < 6) and (0 <= j < 7)

    def teste_en(i: int, j: int) -> str:
        """Renvoie "1" ou "2" si un gagnant est trouvé en partant de (i, j),
        sinon renvoie "0".
        """
        candidat = grille[i][j]
        if candidat == "0":
            return "0"
        vecteurs = [
                    (0, 1), # horizontal
                    (1, 0), # vertical
                    (1, 1), # diagonal 1
                    (1, -1) # diagonal 2
                ]
        for di, dj in vecteurs:
            if est_dans_grille(i + 3*di, j + 3*dj):
                if grille[i + di][j + dj] == candidat:
                    if grille[i + 2*di][j + 2*dj] == candidat:
                        if grille[i + 3*di][j + 3*dj] == candidat:
                            return candidat
        return "0"

    for i in range(6):
        for j in range(7):
            candidat = teste_en(i, j)
            if candidat != "0":
                return candidat
    return "0"


import doctest
doctest.testmod()

grille = [input() for _ in range(6)]

print(gagnant_puissance_4(grille))

• Le code a déjà été factorisé pour chacune des 4 façons de gagner : horizontale, verticale et deux diagonales.

• Pour factoriser encore les trois lignes qui se ressemblent, on peut utiliser la fonction all de Python qui renvoie True si tous ses éléments sont vrais, sinon un False prématuré est renvoyé.

Une version raccourcie de la fonction teste_en est alors :

🐍 Script Python

    def teste_en(i: int, j: int) -> str:
        candidat = grille[i][j]
        if candidat == "0":
            return "0"
        if not est_dans_grille(i + 3*di, j + 3*dj):
            return "0"
        for di, dj in [(0, 1), (1, 0), (1, 1), (1, -1)]:
            if all(grille[i + k*di][j + k*dj] == candidat for k in range(1, 4)):
                return candidat
        return "0"