E09 - Puzzle⚓︎
Le problème
Proposition 1⚓︎
🐍 Script Python
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 debut_petit_puzzle(petit_puzzle:list) -> tuple:
"""Renvoie les coordonnées de la première pièce du petit puzzle
>>> debut_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 = debut_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.
Proposition 2⚓︎
🐍 Script Python
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)
1) Erreur
🐍 Script Python
if not est_dans_le_puzzle(x_départ+delta_x, y_départ+delta_y):
return False
Il vaut mieux
🐍 Script Python
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é...
2) Pas terrible
🐍 Script Python
if puzzle_correct:
break
Il vaut mieux mettre cette section dans une fonction, et au lieu de puzzle_correct = True, faire un return True
Proposition 3⚓︎
🐍 Script Python
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⚓︎
🐍 Script Python
# 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_puzzlerenvoie un booléen, au lieu de0ou1qui est une tradition du langage C qui n'a pas de booléen. Pour finir, l'affichage de0ou1peut se faire avecprint("1" if pièce_compatible_puzzle(puzzle, pièce) else "0").
Corrigé du professeur⚓︎
🐍 Script Python
"""
author : Franck CHAMBON
problem: https://prologin.org/train/2003/semifinal/puzzle
"""
# Constantes
L_Piece = 4
L_Puzzle = 10
# Lecture de l'entrée
piece = [input() for _ in range(L_Piece)]
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_Piece):
idi = i + di
for dj in range(L_Piece):
jdj = j + dj
if piece[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.
Méthode de test⚓︎
Dans mon répertoire prologin_2003/E9, j'ai créé un fichier in.txt contenant :
📋 Texte
0110
0110
1111
0011
1111111111
1110111111
1100111001
1100111001
1000011101
1100011111
1111011111
1100100111
1110110011
1110111111
J'ai lancé ensuite dans un terminal bash :
Bash Session
$ 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 fichierin.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.