Aller au contenu

E12 - Plages du Pacifique⚓︎

Le problème

Plages du Pacifique

Proposition 1⚓︎

🐍 Script Python
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))
  • On ne peut pas résoudre ce problème par balayage ligne après ligne, un tel balayage évite les méandres...
    • Il faut le voir comme un graphe.

Proposition 2⚓︎

🐍 Script Python
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))
  • Même remarque que supra.

Proposition 3⚓︎

🐍 Script Python
# 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)) 
  • Même avec les commentaires, le code est peu clair... Ça reste un très beau travail d'initiation, on devine un bel avenir de codeur. Avec l'expérience on arrive à écrire un code clair et efficace. Il y a plusieurs phases à découvrir : s'essayer à résoudre, s'essayer à être efficace, s'essayer à être clair, enfin maîtriser. Tout un programme de plusieurs années.

Corrigé du professeur⚓︎

🐍 Script Python
"""
author: Franck CHAMBON
problem: 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()
  • main (principale, en anglais) est la première fonction lancée dans un programme écrit en langage C, et par extension une tradition avec d'autres langages.
  • 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.
  • Pour les plages, on exclut les cases en diagonale d'une case de l'océan, d'où le test (di == 0) or (dj == 0).
  • Plusieurs fichiers de test 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, comme dans l'exemple :

Bash Session
$ 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 \(572\) plages avec l'entrée suivante, et que le temps utilisateur (user) est de 0,062 s sur ma machine. De quoi être confiant pour réussir avec le juge.

Création de fichiers de tests

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 à maitriser, 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 travaillent 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 :

📋 Texte
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