E10 - Solitaire⚓︎
Le problème
Proposition 1⚓︎
🐍 Script Python
def solitaire(grille:list) -> int:
""" Prend une grille qui décrit des positions d'un jeu de solitaire puis recherche et renvoie le nombre de coup possible
>>> solitaire([[2, 2, 0, 1, 1, 2, 2], [2, 2, 0, 0, 1, 2, 2], [0, 0, 1, 1, 0, 1, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 1, 0], [2, 2, 0, 0, 0, 2, 2], [2, 2, 0, 1, 1, 2, 2]])
7
"""
# Toutes les placements possibles d'une bille autour d'une autre
directions = [(1, 0),(0,1),(-1,0),(0,-1)]
def est_possible(x:int, y:int) -> bool:
""" Regarde si le déplacement est possible sur une grille 7*7
>>> est_possible(3, 7)
False
>>> est_possible(2, 4)
True
"""
return (0 <= y < 7) and (0 <= x < 7)
def recherche_coup(x:int, y:int, direction_coup_y:int, direction_coup_x:int) -> int:
""" Recherche et renvoie 1 si il est possible de faire un coup sachant qu'il y a une bille à cotè sinon 0
"""
y += direction_coup_y
x += direction_coup_x
if not(est_possible(x, y)) or (grille[y][x] !=0):
return 0
return 1
nb_coups = 0
for y in range(7):
for x in range(7):
# Si on a une bille
if grille[y][x] == 1:
for direction_y, direction_x in directions:
# On regarde dans les 4 directions si il est possible de se déplacer et si il y a une bille
déplacement_x = x+direction_x
déplacement_y = y+direction_y
if est_possible(déplacement_y,déplacement_x) and grille[déplacement_y][déplacement_x] == 1:
# On regarde si le placement est possible après la bille qu'on saute
direction_x *= 2
direction_y *= 2
nb_coups += recherche_coup(x, y, direction_y, direction_x)
return nb_coups
# tests
import doctest
doctest.testmod()
# Entrée
grille = []
for x in range(7):
grille.append(list(map(int,input())))
# Sortie
print(solitaire(grille))
- C'est très bien dans l'ensemble.
Proposition 2⚓︎
🐍 Script Python
plateau = []
liste_billes = []
for ligne in range(7):
entrée = list(input())
plateau.append(entrée)
for colonne in range(7):
if entrée[colonne] == "1":
liste_billes.append((ligne, colonne))
def est_déplaçable(x, y):
"""
Retourne le nombre de déplacements possibles à partir de (`x`,`y`)
"""
nombre_déplacements = 0
if 0 <= x+2 < 7 and 0 <= y < 7:
if plateau[x+1][y] == "1":
if plateau[x+2][y] == "0":
nombre_déplacements += 1
if 0 <= x < 7 and 0 <= y+2 < 7:
if plateau[x][y+1] == "1":
if plateau[x][y+2] == "0":
nombre_déplacements += 1
if 0 <= x-2 < 7 and 0 <= y < 7:
if plateau[x-1][y] == "1":
if plateau[x-2][y] == "0":
nombre_déplacements += 1
if 0 <= x < 7 and 0 <= y-2 < 7:
if plateau[x][y-1] == "1":
if plateau[x][y-2] == "0":
nombre_déplacements += 1
return nombre_déplacements
somme_déplacements = sum(est_déplaçable(x_bille, y_bille) for x_bille, y_bille in liste_billes)
print(somme_déplacements)
est_déplaçabledevrait être renommée.- Une fonction pour savoir si on est dans le plateau de jeu serait bienvenue.
- On peut factoriser le code avec 4 vecteurs ; c'est un bon exercice, et une bonne pratique.
Proposition 3⚓︎
🐍 Script Python
def coup_posible(plateau, y: int, nb_coup: int):
""" trouve le nombre de bille qui peuvent etre jouer
"""
for ligne in range(7):
if plateau[y][ligne] == '1':
if ligne < 5 :
if plateau[y][ligne + 1] == '1':
if plateau[y][ligne + 2] == '0':
nb_coup += 1
if plateau[y][ligne - 1] == '0':
nb_coup +=1
if ligne == 5 :
if plateau[y][ligne + 1] == '1' and plateau[y][ligne - 1] == '0':
nb_coup += 1
if y <= 4:
if plateau[y + 1][ligne] == '1' and plateau[y + 2][ligne] == '0':
nb_coup += 1
if y >= 2:
if plateau[y - 1][ligne] == '1' and plateau[y - 2][ligne] == '0':
nb_coup += 1
if y < 6:
return coup_posible(plateau, y + 1, nb_coup)
else :
return nb_coup
plateau = [input() for _ in range(7)]
nb_coup = 0
y = 0
print(coup_posible(plateau, y, nb_coup))
- 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.
y: nom de variable à changer.
Proposition 4⚓︎
🐍 Script Python
# 0- Coeur du programme
def est_dans_le_plateau(i: int, j:int, plateau: list) -> bool:
""" Renvoie True si le curseur i,j est dans le plateau (dans le bon intervalle 0 <= i,j < 7 et que le curseur ne cible pas un 2)
>>> plateau = ["2201122", "2200122", "0011010", "0100000", "0010110", "2200022", "2201122"]
>>> est_dans_le_plateau(0, 0, plateau)
False
>>> est_dans_le_plateau(4, 3, plateau)
True
"""
if 0 <= i <= 6 and 0 <= j <= 6:
if plateau[i][j] != "2":
return True
return False
def nombre_de_coups(plateau: list) -> int:
""" Détermine combien il existe de coups différents possibles, pour le prochain coup et renvoie le nombre.
>>> plateau = ["2201122", "2200122", "0011010", "0100000", "0010110", "2200022", "2201122"]
>>> nombre_de_coups(plateau)
7
"""
# Chaque combinaison correspond à une direction à tester, dans l'ordre on a :
# Droite, Bas, Gauche, Haut
combinaison = [(0,1),(1,0),(0,-1),(-1,0)]
compteur = 0 # On initialise le compteur à 0
for i in range(7): # Ensuite, pour chaque case du plateau
for j in range(7):
if plateau[i][j] == "1": # ayant un pion (= 1)
for x, y in combinaison: # on test pour chaque direction
if est_dans_le_plateau(i+x*2, j+y*2, plateau): # s'il existe une case à 2 pîons de i,j , c'est à dire qui se trouve dans la grille
# et si le premier pion dans la direction est un 1 et le second est un 0
if plateau[i+x][j+y] == "1" and plateau[i+x*2][j+y*2] == "0":
compteur += 1 # Si oui, on ajoute 1 au compteur
return compteur # Quand on a vérifié toutes les cases, on renvoie compteur
# 1- Tests
import doctest
doctest.testmod()
# 2- Lecture de l'entrée
plateau = [input() for _ in range(7)]
# 3- Appel de la fonction / Sortie
print(nombre_de_coups(plateau))
- Lignes trop longues ; on ne met de commentaires que si le code n'est pas explicite.
- Rendre le code plus explicite si nécessaire, et limiter les commentaires.
- Placer les commentaires nécessaires juste avant ; comme une justification en mathématiques : avant. Ou alors un très court sur la même ligne.
vecteursest mieux quecombinaisonici.compteurdevrait être renommé pour être plus explicite.
Corrigé du professeur⚓︎
🐍 Script Python
"""
author : Franck CHAMBON
problem: https://prologin.org/train/2003/semifinal/solitaire
"""
grille = [input() for _ in range(7)]
def est_valide(i: int, j: int) -> bool:
if not((0 <= i < 7) and (0 <= j < 7)):
# en dehors du grand rectangle
return False
# Est-on sur une des deux bandes ?
return (2 <= i < 5) or (2 <= j < 5)
def est_occupee(i: int, j: int) -> bool:
return est_valide(i, j) and (grille[i][j] == "1")
def est_libre(i: int, j: int) -> bool:
return est_valide(i, j) and (grille[i][j] == "0")
nb_coups_possibles = 0
for i in range(7):
for j in range(7):
if est_occupée(i, j):
for di, dj in [(0, +1), (0, -1), (+1, 0), (-1, 0)]:
if est_occupee(i + di, j + dj):
if est_libre(i + 2*di, j + 2*dj):
nb_coups_possibles += 1
print(nb_coups_possibles)
- Un découpage en fonctions élémentaires rend le problème plus simple.
- Pas de doctest ici, mais utilisation d'un fichier
in.txt
title
2201122
2200122
0011010
0100000
0010110
2200022
2201122
et la sortie attendue avec :
Bash Session
$ prologin_2003/E10$ python solitaire.py < in.txt
7