Quelques propositions d'élèves, et à la fin un corrigé du professeur.
À la suite de chaque proposition de code, un commentaire de correction du professeur. Le cartouche demandé en introduction a été supprimé ici.
def Plages_Pacifique(nb_ligne:int,nb_colonne:int,grille:list): """ Renvoie le nombre de plage sur une île représentée par des 1, 0 représente la mer""" directions = [(1, 0), (0, 1),(-1,0),(0,-1)] def est_possible(i, j): """Regarde si le déplacement est possible""" return (0 <= i < nb_ligne) and (0 <= j < nb_colonne) def vérifie(i, j, direction_y, direction_x): """ vérifie si il y a une case océan à proximité d'une case terre """ i += direction_y j += direction_x if est_possible(i, j) and (grille[i][j] == 0): return 1 return 0 def plage(i:int,j:int,directions:list) -> int: """ Renvoie le nombre de plage disponible""" for direction_y, direction_x in directions: if vérifie(i, j, direction_y, direction_x) != 0: return 1 return 0 nb_plages = 0 sortie = 0 for i in range(nb_ligne): for j in range(nb_colonne): if grille[i][j] == 1: nb_plages += plage(i,j,directions) return nb_plages # tests import doctest doctest.testmod() # Entrée nb_colonne,nb_ligne= map(int,input().split()) grille = [] for x in range(nb_ligne): grille.append(list(map(int,input()))) # Sortie print(Plages_Pacifique(nb_ligne,nb_colonne,grille))
nb_colonnes, nb_lignes = map(int, input().split(" ")) carte = [] vecteurs = [(-1, 0), (1, 0), (0, 1), (0, -1)] for _ in range(nb_lignes): entrée = list(map(int, list(input()))) carte.append(entrée) def est_dans_la_carte(x,y): """ """ return (0<=x<nb_lignes) and (0<= y < nb_colonnes) def liste_les_océans(): """ Renvoie un ensemble avec toutes les cases qui sont un océan >>> liste_les_océans() {(0,0),(0,1)(0,2),(0,3),(0,4),(0,5),(0,6),(0,7)} """ ensemble_océans = {(0, 0)} for x in range(nb_lignes): for y in range(nb_colonnes): for delta_x in [-1, 0 , 1]: for delta_y in [-1, 0, 1]: if delta_x == 0 and delta_y == 0: continue else: if not est_dans_la_carte(x+delta_x, y+delta_y): continue else: if carte[delta_x+x][delta_y+y] == 0: if (x+delta_x, y+delta_y) in ensemble_océans: if carte[x][y] == 0: ensemble_océans.add((x, y)) return ensemble_océans ensemble_océans = liste_les_océans() ensemble_océans = sorted(ensemble_océans) def liste_les_plages(): """ Renvoie un ensemble avec toutes les cases étant des plages >>> liste_les_plages() {(1,1),(1, 2), (1, 3), (1, 4), (1, 5), (1, 6)} """ ensemble_plages = set() for x in range(nb_lignes): for y in range(nb_colonnes): if carte[x][y] == 0: continue for delta_x, delta_y in vecteurs: if (x+delta_x, y+delta_y) in ensemble_océans: ensemble_plages.add((x, y)) continue return sorted(ensemble_plages) ensemble_plages = liste_les_plages() print(len(ensemble_plages))
# 0- Coeur du programme def est_dans_le_tableau(largeur: int, hauteur: int, coord_x: int, coord_y:int, x: int, y: int) -> bool: """ Renvoie True si le curseur i+x,j+y est dans le tableau >>> est_dans_le_tableau(4, 3, 1, 1, 1, 1) True >>> est_dans_le_tableau(5, 5, 4, 4, 1, 0) False """ if 0 <= coord_x+x <= hauteur-1 and 0 <= coord_y+y <= largeur-1: return True else: return False def déterminer_départ(largeur: int, hauteur: int, tableau: list) -> tuple: """ Détermine les coordonnées de la première case d'eau(0) à gauche d'une case de Terre(1). >>> déterminer_départ(5, 5, ["00000", "01110", "01110", "01110", "00000"]) (1, 0) """ for x in range(0,hauteur-1): for y in range(0,largeur-1): if tableau[x][y+1] == "1": return (x,y) def déterminer_direction(largeur: int, hauteur: int, tableau: list, coord_x: int, coord_y: int, dernière_direction: int) -> tuple: """ Détermine la direction à prendre pour le prochain déplacement et renvoie x,y et le numéro de la direction(entre 1 et 8) >>> déterminer_direction(5, 5, ["00000", "01110", "01110", "01110", "00000"], 0, 1, 3) (0, 1, 2) """ combinaisons = [(1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (1,0)] # Chaque combinaison correspond à une direction à tester, il faut les faire dans un ordre précis! # Il s'agit d'un cercle qui doit toujours commencer par la case derière à droite du dernier déplacement, numéroté de 1 à 8 dernière_direction = dernière_direction-4 if dernière_direction-4 >= 0 else dernière_direction+4 # On inverse alors le dernier déplacement pour que ce soit la case derière nous qu'il vise for id_combinaisons in range(-7+dernière_direction, dernière_direction): # On commence ainsi par le déplacement derrière à droite x, y = combinaisons[id_combinaisons] if est_dans_le_tableau(largeur, hauteur, coord_x, coord_y, x, y): # On vérifie si le déplacement est dans le tableau if tableau[coord_x+x][coord_y+y] == "0": # On vérifie que l'on aille bien sur une case de mer(qui sera donc juste à côté d'une case de Terre) dernière_direction = id_combinaisons+1 if id_combinaisons+1 >= 0 else id_combinaisons+9 # On met dans dernière_direction , le numéro de la direction que l'on vient de prendre return (x,y, dernière_direction) # (c'est à dire, l'identifiant de id_combinaison +1 ou +9 ) def nombre_de_plages(largeur: int, hauteur: int, tableau: list) -> int: """ Calcule le nombre de plage de l'ile, le nombre de case de terre (1) qui touche une case océan (0). >>> nombre_de_plages(5, 5, ["00000", "01110", "01110", "01110", "00000"]) 8 """ # Mise en place des variables emplacements_plages = list() # On crée une liste des plages afin de les recenser et de ne pas en compter une 2 fois emplacement_de_départ = déterminer_départ(largeur, hauteur, tableau) # Recherche de la première zone d'eau(0) à côté de Terre (1) coord_x, coord_y = emplacement_de_départ coord_x_départ, coord_y_départ = emplacement_de_départ emplacements_plages.append((coord_x, coord_y+1)) coord_x -= 1 # Le premier déplacement est toujours en diagonale(Haut/Droite) coord_y += 1 dernière_direction = 3 # D'après les combinaisons dans la fonction déterminer_direction, # il s'agit de la 3ème direction (on commence à 1) # Début des déplacemennt while coord_x != coord_x_départ or coord_y != coord_y_départ: # La fonction s'arrêtera lorsque nous seront revenu à notre point de départ # On souhaite déterminer la bonne combinaison pour continuer à avancer au bord de la plage x, y, dernière_direction = déterminer_direction(largeur, hauteur, tableau, coord_x, coord_y, dernière_direction) coord_x += x coord_y += y combinaisons = [(1,0), (0,1), (-1,0), (0,-1)] # Chaque combinaison correspond à une direction à tester pour les zones de Terre(1), dans l'ordre on a : # Bas, Droite, Haut, Gauche for x, y in combinaisons: if est_dans_le_tableau(largeur, hauteur, coord_x, coord_y, x, y): # On vérifie si le déplacement est dans le tableau if tableau[coord_x+x][coord_y+y] == "1" and (coord_x+x, coord_y+y) not in emplacements_plages: # On vérifie s'il s'agit d'un plage et si elle n'est pas déjà répertoriée dans emplacements_plages emplacements_plages.append((coord_x+x, coord_y+y)) # S'il s'agit d'une plage non répertoriée, alor son l'ajoute à la liste return len(emplacements_plages) # Pour finir, on renvoie le nombre de plages dans emplacements_plages # 1- Tests import doctest doctest.testmod() # 2- Lecture des entrées largeur, hauteur = map(int,input().split()) tableau = [input() for _ in range(hauteur)] # 3- Appel de la fonction / Sortie print(nombre_de_plages(largeur, hauteur, tableau))
""" auteur : Franck CHAMBON https://prologin.org/train/2003/semifinal/plages_du_pacifique """ def main(): def est_valide(i: int, j: int) -> bool: return (0 <= i < nb_lignes) and (0 <= j < nb_colonnes) nb_colonnes, nb_lignes = map(int, input().split()) grille = [list(input()) for _ in range(nb_lignes)] courant = set() # On place tout le tour de la grille dans l'océan. for i in range(nb_lignes): courant.add((i, 0)) courant.add((i, nb_colonnes - 1)) for j in range(nb_colonnes): courant.add((0, j)) courant.add((nb_lignes - 1, j)) plages = set() while courant != set(): suivant = set() for (i, j) in courant: grille[i][j] = "3" # marquage pour vu for di in (-1, 0, +1): idi = i + di for dj in (-1, 0, +1): jdj = j + dj if est_valide(idi, jdj): if (grille[idi][jdj] == "0"): # on prépare les cases voisines, tout autour ! suivant.add((idi, jdj)) if (grille[idi][jdj] == "1"): if (di == 0) or (dj == 0): # pas en diagonale plages.add((idi, jdj)) courant = suivant print(len(plages)) main()
courant désigne les cases d'océan qui vont être étudiées bientôt. suivant désigne les prochaines. On fait un parcours de graphe en largeur.(di == 0) or (dj == 0).in.txt sont utilisés, dont certains grands fabriqués aléatoirement pour tester la rapidité du script.Exercice 1 : réécrire ce code avec un style POO.
Exercice 2 : Réécrire ce code, sans jamais utiliser les set. On pourra utiliser d'autres caractères pour marquer les cases.
Exercice 3 : Écrire un script Python qui produit une grande entrée aléatoire convenable pour ce problème. On pourra dessiner des disques alternativement à 0 et 1, avec des rayons et centres aléatoires. L'aléatoire uniforme n'est pas le meilleur choix... Ensuite, une méthode pour vérifier le temps d'un programme quelque soit son langage est :
prologin_2003/E12$ time votre_programme < in.txt
Ici:
prologin_2003/E12$ time python plages.py < in.txt 572 real 0m0,070s user 0m0,062s sys 0m0,008s
On découvre qu'il y a plages avec l'entrée suivante, et que le temps utilisateur (user) est de s sur ma machine. De quoi être confiant pour passer le juge.
Savoir créer de bons fichiers de tests est une compétence très recherchée. Il n'y a pas que le côté aléatoire à maîtriser, mais aussi les cas délicats (corner cases). Pour résoudre un problème difficile, on commence souvent avec une version force brute, qui est utile ensuite pour fabriquer des fichiers de tests pour la version efficace. Cette méthode permet aussi de travailler avec d'autres langages, et les mêmes fichiers de tests. C'est la raison principale pour laquelle les juges en ligne travaille avec des fichiers d'entrée et de sortie à comparer. L'autre raison étant que de nombreux programmes communiquent entre eux via des fichiers textes.
Voici un exemple de grande entrée aléatoire :
100 100
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0011111111111111111111000000011111100000000000000000000111110101000000000000000010000000000000000000
0111111111111111111110000000111111100000000000000000001111111111100000000000000000000010100000000000
0111111111111111111100000000011111100000000000000000000111111101000000000000000000111111111000000000
0111111111101111111000000000001111100000000000000000000111111100000000000000001011111111111110000000
0111111111111111111000000000001111100000000000000000000011111000000001000000000111111111111111000000
0110111111111111111000000000001111100000000000000000000000100000000000000000001111111111111111011000
0111111111111111110000000000000111100000000000000000000000000000000000000000011111111111111111111100
0111111111111111111000000000001111110000000000000000000000000000000000000000011111111111111111111000
0111111111111111111000000000001111111000000000000000100000000000000000000000111111111111111111111000
0111111111111111111000000000001111111100000000000000000001000000000100000000111111111111111111111000
0111111101111111111100000000011011110110000000000000000011100000000000000000111011111111111111111000
0111111111111111111110000000111111100011000000000000010001000000000000000000110001111111111111111000
0111111111111111011111110111111111100111000000000000111000000000000000000001111011110111111101111100
0111111111111100000111111101111111111111100000000000010000000000000000000000111111111111111111111000
0111111111111100010111111111111111111111110000000000000000000000000000000000111111111111111111111000
0111011111111000000011111111111111111111110000000000000000000000000000000000111111111111111111111000
0111111111111100000110111111111111111111101000000000000000000000000000000000111111111111111111111010
0101111111111100000111111101111111111111111000000000000000000000000000000000011111111111111111110000
0111110111111111011111111000111111111111111100000000000000000000000000000000011111111111111111110000
0111100011111011111111111100111111101011111100000000000000000000000000000000001011111111111111100000
0111110111111111111111111000001111110001111110000000000000000000000000000000000111111111111111000000
0111111111111111111111111000001111111011111110000000000000000001000000000000000011111110111110000000
0111011111111111110111111000000111011111111110000000000000000000000000010000000000111111111000000000
0111111111111111111011111000011111111101111111000000000000000000000000000100000000000010000000000000
0111111111111111111111111000001111110000011111000000000000000000000000100000000010000000000000100000
0111111111111111110110111110111111110000011111000000000000000000000000000010001111100000000000000000
0111111111111111111111111111111111100000001111000000000000000000000000001000011111110000000000000000
0111111111111111111111111111111111110000011111000000000000000001000000000000011111110000000000000000
0111111111111111111111111111111111110000011111000000000000000000000000000000111111111000000000000000
0111111111111111111111111111111111111101111111000000000000000000000000000000011111110000000000000000
0111111111011111111101111111111111111111111111000000000000010000000000000000011111110000000000000000
0111111111111111111000111111101111111111111111100000000000000000000000000000001111100000000000000010
0111111111111111111101111111111111111111111011000000000000100001000000000000110010000000000000000110
0111111111111111111111111111111111111111111111000000000000000000000000000001111100000000000000000010
0111111111111000111101111111111111111111111111000000000000000000000000000001111110000000000000000000
0111111111100000011000111111111111111111111111000000000000000000000000000011111110000000000000000000
0111111111001000000101111111000111111111111111000000000000000000000000001101111111000000000000000000
0111111110000000000000010000000011111111111111000000000000000000000000000011111110000000000000000000
0111111100000000000000000000000001111111111111000000000000000000000000000011111110000000000000000000
0111111000000000000000000000000000111111111111000000000000000000000000100001111100000000000000000000
0111111000000000000000000000000000111111111110000000000000000000000000000000010000000000000000000000
0111110000000000000000000000000000011111111110000000000000000000000000000000000000000000000000000000
0111110000000000000000000000000000011111010110000000000000000000000000000000000000000000000000000000
0111100000010000000000000000000000001110110100100000000000000000000000000000000000000000000000000000
0111100000111000000000000000000000001111111100000000000110000000000000000000000000000000000000000000
0111100000010000000000000000000000001111111000000000001111000000000000000000000000000000000000000000
0111100000000000000000000000000000001111111000000000000100000000000000001000000000000000000000000000
0111100000000000000000000000000100001111110000000000000000000000000000000000000000000000000000000000
0111000000000000000000000000000000000111110000000000000000000000000000000000000000000000000000000000
0111100000000000000000000000000000001111100000000000000000000000000000000000000000000000100100000100
0111100000000000000000000000000000001111000000000000000000000000000000000100000000000000000000000000
0111100000000000000000000000000000001111000000000000000000000000000000000000000000000000000000000000
0111100100000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000
0111110000000000000000000010000000001100000000000000000000000000000000000000000000000000000001000000
0111111000000000000000000000000000011000000000000000000000000000000000000000000000000000000000100000
0111101000000000000000000000000000010000000000000000010000000000000000000000000000000000000000000000
0101111100000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000
0111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0101111110000100000000000000100000000000000000000000000000000000000000000000000000000000000000000000
0111111111000000000000000000000000000100000000000000000100000000000000000000000000000000000000000000
0111101011100000000000000000000000000000000000000000001110000000000000000000000000000000000000000000
0011000111011000000000000000000000000000000000010000000100000000000000000000000000000000000000000000
0000001111111110000000000000000000010000000000000000000000000000000000000000000000000000000000000000
0000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000
0000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000
0000000100000010000000000000000000000000000000000001110000000000000000000000000000000000000001010000
0000100000000000000000000000000000000000000000001000100000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000
0001000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000
0000000010000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000
0000000000010001000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000001000000000000000000000000000000000000000000001000000000100000000000000000100000000010
0000000000000000000100000000000000000000000000000000000000011100000001110000000000000000000000000000
0000000000000000001110000000000000000000000000010000000000001000000000100000000000000000000000000000
0010000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000001000000000000000000000000000100000000000000000000
0000000000000000000000000000000000000000000000000000001000000000000000000000011111000000000000000000
0000110000000000000000000000000000000000000000000000111010000000000000000000111111000000000000000000
0000010000000000000000000000000000000000000000000001111111000000000000000000111111100000000000000000
0000000000000000000000000000000000000010000000000001111101000001000000000001111111110000000000000000
0000000000100000000000000000000000000111000000000011111111100000000000000000111111100000000000000000
0000000000000000000000000000000000001010000000000001111111000000000000000000111111100000000000000000
0000000000000000000000000000000000000000000000000001111111000000000000000000011111000000000000000000
0000100000000000000000000000000000001000000000000000111110010000100000000000000100000000000000000000
0000000000000000000000010000000000000000000000000000001000000000000000000000000000000000000110000000
0000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000100000000
0000000000000000100000000000000000000000000000000000000000000000000000000000000000000000011110000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111110000000
0000000000000000000000000000010000000000000000000000000000000000000000000000000000000000111110000000
0000000000000000000000000000000000000000000000000000000000000000000001000000000001000001111100000000
0010000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000
0000000000000000000000000000000000000000000000000000000000000000000000100000100000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000