Correction de Puzzle

Quelques propositions d’élèves, et à la fin un corrigé du professeur.

Propositions d’élèves
Corrigé du professeur

Propositions d’élèves

À la suite de chaque proposition de code, un commentaire de correction du professeur. Le cartouche demandé en introduction a été supprimé ici.

Proposition 1

def insertion_puzzle(petit_puzzle: list, grand_puzzle : list):
    """ Regarde si l'on peut insérer le petit puzzle 4*4 dans les emplacements vides du grand puzzle
    >>> insertion_puzzle([[0, 1, 1, 0], [0, 1, 1, 0], [1, 1, 1, 1], [0, 0, 1, 1]],[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 1, 1, 1, 0, 0, 1], [1, 1, 0, 0, 1, 1, 1, 0, 0, 1], [1, 0, 0, 0, 0, 1, 1, 1, 0, 1], [1, 1, 0, 0, 0, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 1, 1, 1, 1, 1], [1, 1, 0, 0, 1, 0, 0, 1, 1, 1], [1, 1, 1, 0, 1, 1, 0, 0, 1, 1], [1, 1, 1, 0, 1, 1, 1, 1, 1, 1]])
    1
    """
    def début_petit_puzzle(petit_puzzle:list) -> tuple:
        """Renvoie les coordonnées de la première pièce du petit puzzle
        >>> début_petit_puzzle([[0, 1, 1, 0], [0, 1, 1, 0], [1, 1, 1, 1], [0, 0, 1, 1]])
        (0,1)
        """
        for y in range(4):
            for x in range(4):
                if petit_puzzle[y][x] != 0:
                    return (y,x)

    début = début_petit_puzzle(petit_puzzle)
                    

    déplacements = []
    def recherche_déplacement(petit_puzzle: list,déplacements:list,début:tuple):
        """ Prend le positionnement de chaque piéce du puzzle par rapport à la première pièce et le met dans déplacements
        >>> recherche_déplacement([[0, 1, 1, 0], [0, 1, 1, 0], [1, 1, 1, 1], [0, 0, 1, 1]],[],(0,1))
        """
        y,x = début
        for y_1 in range(4):
            for x_1 in range(4):
                if petit_puzzle[y_1][x_1] != 0:
                    déplacements.append((y_1-y,x_1-x))


            
    # On affecte chaque déplacement du petit puzzle dans déplacement
    recherche_déplacement(petit_puzzle,déplacements,début)
    
    def est_possible(y : int, x:int) -> bool:
        """ Regarde si le déplacement est possible
        >>> est_possible(8,9)
        True
        >>> est_possible(10,2)
        False
        """
        return (0 <= x < 10) and (0 <= y < 10)

    def recherche_emplacement(x:int, y:int, déplacements:list,grand_puzzle:list) -> int:
        """ Recherche si il est possible d'insérer le petit puzzle dans le grand puzzle et renvoie 1 sinon 0
        >>> recherche_emplacement(2,2,[(0, 1), (1, 0), (1, 1), (2, -1), (2, 0), (2, 1), (2, 2), (3, 1), (3, 2)],[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 1, 1, 1, 0, 0, 1], [1, 1, 0, 0, 1, 1, 1, 0, 0, 1], [1, 0, 0, 0, 0, 1, 1, 1, 0, 1], [1, 1, 0, 0, 0, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 1, 1, 1, 1, 1], [1, 1, 0, 0, 1, 0, 0, 1, 1, 1], [1, 1, 1, 0, 1, 1, 0, 0, 1, 1], [1, 1, 1, 0, 1, 1, 1, 1, 1, 1]])
        1
        """
        for déplacement_y,déplacement_x in déplacements:
            if not(est_possible(y + déplacement_y, x+  déplacement_x)) or (grand_puzzle[y+déplacement_y][x+ déplacement_x] != 0):
                return 0
        return 1

    for y in range(10):
        for x in range(10):
            if grand_puzzle[y][x] != 1:
                insertion_possible = recherche_emplacement(x, y,déplacements,grand_puzzle)
                if insertion_possible == 1:
                    return insertion_possible
    return 0

# tests
import doctest
doctest.testmod()

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

grand_puzzle = []
for x in range(10):
    grand_puzzle.append(list(map(int,input())))

# Sortie
print(insertion_puzzle(petit_puzzle,grand_puzzle))

De bonnes choses, mais code trop long.
Revoir le PEP-8.
x et y sont de mauvais choix ici.

Proposition 2

nb_lignes_pièce = nb_colonnes_pièce = 4
nb_lignes_puzzle = nb_colonnes_puzzle = 10

pièce = []
puzzle = []

for ligne in range(nb_lignes_pièce):
    entrée = list(map(int, list(input())))
    pièce.append(entrée)

for ligne in range(nb_lignes_puzzle):
    entrée = list(map(int, list(input())))
    puzzle.append(entrée)

def est_dans_le_puzzle(x, y):
    """
    Renvoie si les coordonnées `x` et `y` sont dans les limites de la puzlle
    """
    return (0 <= x < nb_lignes_puzzle )and (0 <= y < nb_colonnes_puzzle)

def recherche_puzzle_correct(x_départ, y_départ):
    """
    Retourne un booléen si la pièce est compatible avec le puzzle à partir du coordonnées `x_départ` `y_départ`
    """
    for delta_x in range(4):
        for delta_y in range(4):
            if not est_dans_le_puzzle(x_départ+delta_x, y_départ+delta_y):
                return False
            if puzzle[x_départ+delta_x][y_départ+delta_y] == 1 and 1 == pièce[delta_x][delta_y]:
                return False
    return True

puzzle_correct = False

for ligne in range(nb_lignes_puzzle):
    for colonne in range(nb_lignes_puzzle):
        if puzzle_correct:
            break
        if puzzle[ligne][colonne] != puzzle[0][0]:
            if recherche_puzzle_correct(ligne, colonne):
                puzzle_correct = True
print(1 if puzzle_correct else 0)

Erreur

            if not est_dans_le_puzzle(x_départ+delta_x, y_départ+delta_y):
                return False

Il vaut mieux

            if (1 == pièce[delta_x][delta_y]) and (not est_dans_le_puzzle(x_départ+delta_x, y_départ+delta_y)):
                return False

En effet, si un zéro est en dehors du cadre, c’est autorisé…

Pas terrible

        if puzzle_correct:
            break

Il vaut mieux mettre cette section dans une fonction, et au lieu de puzzle_correct = True, faire un return True

Bonne pratique ; tu as défini des constantes au début, mais il faut les utiliser alors partout, il reste au moins deux 4 à remplacer !!!

Proposition 3

def trouve_enplacement_piece(piece_puzzle,  puzzle_entier,x: int, x2: int):
    """ cherche un endroit où la piece de puzzle peut entrer si elle entre affiche 1 sinon 0
    """
    piece_rentre = 0
    conteur_piece_vide = 0
    conte_nb_rentre = 0
    def cherche_peut_rentrer(piece_puzzle, puzzle_entier, x: int, x2:int, ligne: int, piece_rentre: int, conte_nb_rentre: int):
        "analise si la piece pourait rentrer dans le puzzle "
        sauvegarde_ligne = ligne 
        if ligne == 0:
            ligne -= 1
            for y in range(0, len(piece_puzzle)):
                ligne += 1
                if piece_puzzle[x2][y] != puzzle_entier[x][ligne] or piece_puzzle[x2][y] == '0':
                    conte_nb_rentre +=1
            ligne = sauvegarde_ligne
            if x2 < 3 :
                cherche_peut_rentrer(piece_puzzle, puzzle_entier, x + 1, x2 + 1, ligne, piece_rentre, conte_nb_rentre)
                
            if conte_nb_rentre == 12:
                piece_rentre = 1
                   
        else:
            if piece_puzzle[x2][0] == '0' or piece_puzzle[x2][0] != puzzle_entier[x][ligne - 1]:
                ligne -= 1
                for y in range(0, 4):
                    if piece_puzzle[x2][y] != puzzle_entier[x][ligne] or piece_puzzle[x2][y] == '0':
                        conte_nb_rentre +=1
                    ligne += 1
                ligne = sauvegarde_ligne
                if x2 < 3 :
                    cherche_peut_rentrer(piece_puzzle, puzzle_entier, x + 1, x2 + 1, ligne, piece_rentre, conte_nb_rentre)
                if conte_nb_rentre == 12:
                    piece_rentre = 1
                   
            else:
                for y in range(0, 4):
                    if piece_puzzle[x2][y] != puzzle_entier[x][ligne] or piece_puzzle[x2][y] == '0':
                        conte_nb_rentre +=1
                    ligne += 1
                ligne = sauvegarde_ligne
                if x2 < 3 :
                    cherche_peut_rentrer(piece_puzzle, puzzle_entier, x + 1, x2 + 1, ligne, piece_rentre, conte_nb_rentre)
                if conte_nb_rentre == 12:
                    piece_rentre = 1      

              
            

    for vérif in piece_puzzle:
        if vérif == '0000':
            conteur_piece_vide += 1
    if conteur_piece_vide == 4:
        return '1'
    else:
        sauvegarde_x = x
        for ligne in range(0, len(puzzle_entier)):
            if puzzle_entier[x][ligne] != '1':
                cherche_peut_rentrer(piece_puzzle, puzzle_entier, x, x2, ligne, piece_rentre, conte_nb_rentre)
            x2 = 0
            x = sauvegarde_x
            conte_nb_rentre = 0
        if x < 9 and piece_rentre == 0:
            return trouve_enplacement_piece(piece_puzzle, puzzle_entier, x + 1, x2)
        else:
            return piece_rentre
            
         

piece_puzzle = [input() for _ in range(4)]
puzzle_entier = [input() for _ in range(10)]
x = 0
x2 = 0
print(trouve_enplacement_piece(piece_puzzle, puzzle_entier, x, x2))
""" problème out of range ligne 34, 45 alors qu'il ne drvrait pas 
et aussi il y a un problème si la primière ligne de la piece de puzzle ressemble à ça 0001 alors j'ai pas de code pour savoir ça"""

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.
Il y a beaucoup plus simple comme façon de faire !!!

Proposition 4

# 0- Coeur du programme

def emplacement_compatible(puzzle: list, pièce: list, i: int, j: int) -> bool:
    """ Détermine s'il est possible de placer la pièce dans la zone sélectionée du puzzle de (i,j) à (i+3,j+3).
    Renvoie True si oui, sinon False.
    >>> puzzle = ["0000000000", "0000000000", "0000000000", "0000000000", "0000000000", "0000000000", "0000000000", "0000000000", "0000000000", "0000000000"]
    >>> pièce = ["1111", "1111", "1111", "1111"]
    >>> emplacement_compatible(puzzle, pièce, 0, 0)
    True
    """

    for x in range(4):
        for y in range(4):
            if pièce[x][y] == "1" and puzzle[i+x][j+y] == "1":
                return False
    return True

def pièce_compatible_puzzle(puzzle: list, pièce: list) -> int:
    """ Pour chaque cases du puzzle entre 0 <= i,j < 7 (car sinon, on sort du puzzle), appel la fonction emplacemnt_compatible.
    Si elle renvoie True, alors la fonction renvoie 1, 
    mais si toutes les cases ont été parcourue sans trouver d'emplacement compatible, la fonction renvoie 0.
    >>> puzzle = ["1111111111", "1110111111", "1100111001", "1100111001", "1000011101", "1100011111", "1111011111", "1100100111", "1110110011", "1110111111"]
    >>> pièce = ["0110", "0110", "1111", "0011"]
    >>> pièce_compatible_puzzle(puzzle, pièce)
    1
    """

    for i in range(7):
        for j in range(7):
            if emplacement_compatible(puzzle, pièce, i, j):
                return 1
    return 0

# 1- Tests

import doctest
doctest.testmod()

# 2- Lecture des entrées

pièce = [input() for _ in range(4)]
puzzle = [input() for _ in range(10)]

# 3- Appel de la fonction / Sortie

print(pièce_compatible_puzzle(puzzle, pièce))

Il faut faire un meilleur test pour faire déborder la pièce. S’il n’y a que des zéros à l’extérieur, la pièce peut être placée.
En Python, on préfère que la fonction pièce_compatible_puzzle renvoie un booléen, au lieu de 0 ou 1 qui est une tradition du langage C qui n’a pas de booléen. Pour finir, l’affichage de 0 ou 1 peut se faire avec print("1" if pièce_compatible_puzzle(puzzle, pièce) else "0").

Corrigé du professeur

"""
auteur : Franck CHAMBON
https://prologin.org/train/2003/semifinal/puzzle
"""

# Constantes
L_Pièce = 4
L_Puzzle = 10


# Lecture de l'entrée
pièce = [input() for _ in range(L_Pièce)]
puzzle = [input() for _ in range(L_Puzzle)]


# Cœur du problème
def est_valide(i: int, j: int) -> bool:
    "Renvoie : peut-on mettre la pièce en partant de (i, j) ?"
    for di in range(L_Pièce):
        idi = i + di
        for dj in range(L_Pièce):
            jdj = j + dj
            if pièce[di][dj] == "1":
                if (idi >= L_Puzzle) or (jdj >= L_Puzzle):
                    return False
                if puzzle[idi][jdj] == "1":
                    return False
    return True

def est_possible() -> bool:
    "Renvoie : peut-on placer la pièce quelque part ?"
    for i in range(L_Puzzle):
        for j in range(L_Puzzle):
            if est_valide(i, j):
                return True
    return False


# Sortie
print("1" if est_possible() else "0")

Je débute mes constantes en majuscule, ou je les préfixe comme CONST_ma_constante.
On teste tous les décalages possibles, une pièce pouvant déborder s’il n’y a que des zéros à l’extérieur. L’énoncé n’était pas très clair à ce propos.
Pas de doctest ici ; autre méthode.
Dans mon répertoire prologin_2003/E9, j’ai créé un fichier in.txt contenant :

J’ai lancé ensuite dans un terminal bash :

prologin_2003/E9$ python puzzle.py < in.txt
1

Cette commande lance l’interpréteur Python avec mon script puzzle.py, et en redirigeant l’entrée standard sur le fichier in.txt.
Je vérifie que la sortie est bien 1.
On peut construire d’autres fichiers tests…
Cela évite de polluer le code avec de trop gros tests.
Les doctest, c’est très bien pour les petites fonctions ; pour les grosses fonctions on utilise d’autres méthodes, dont la génération de fichiers tests (entrées et sorties), comme ici.
Nous l’avons déjà vu en première, et nous reverrons comment rediriger l’entrée et la sortie et automatiser les tests.