Percolation

En géologie, la percolation est un écoulement d'eau à travers un sol sous l'effet de la gravité. Le sol n'étant pas compact, l'eau s'infiltre dans les "vides" et pénètre en profondeur.

Précisons tout de suite que l'on appelle sol, l'ensemble du milieu : la surface sur laquelle nous marchons et l'épaisseur de terre et de roche sous nos pieds !

On se propose ici de simuler grossièrement ce mécanisme en se demandant si un écoulement d'eau peut atteindre une certaine profondeur dans un sol.

Le sol

Le sol sera représenté en Python par une liste de listes contenant des entiers. Dans cette liste :

• 0 représente une cellule vide ; l'eau peut la traverser.
• 1 représente de la terre ; l'eau ne peut pas la traverser.
• 2 représente de l'eau.

On garantit que, mis à part une cellule vide sur la première ligne, tous les bords de la grille sont en "terre".

On donne ci-dessous un exemple de sol "sec" (aucune cellule ne contient la valeur 2) :

🐍 Console Python

>>> sol = [
...     [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
...     [1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
...     [1, 1, 0, 1, 0, 1, 1, 1, 0, 1],
...     [1, 1, 1, 1, 1, 1, 1, 0, 0, 1],
...     [1, 0, 1, 0, 1, 0, 0, 0, 1, 1],
...     [1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
...     [1, 1, 1, 0, 0, 1, 1, 1, 0, 1],
...     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
... ]

Comme on peut le voir, une cellule de la première ligne est "vide" (sol[0][5] vaut 0). L'eau peut donc pénétrer par cet endroit.

Comme on le verra dans la suite, l'eau va s'écouler dans ce sol. On peut récupérer un "sol sec" (sans aucun 2 dans la grille) en faisant sol = nouveau_sol().

Génération d'un nouveau sol

La fonction ci-dessous est accessible dans la zone de saisie, inutile de la recopier !

🐍 Script Python

def nouveau_sol(nom='base'):
    """
    Renvoie un sol sec
    Trois sols sont proposés
    Par défaut on récupère le sol 'base'
    """
    sols = {'base': [
        [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
        [1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
        [1, 1, 0, 1, 0, 1, 1, 1, 0, 1],
        [1, 1, 1, 1, 0, 1, 1, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
        [1, 1, 1, 0, 0, 1, 1, 1, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    ],
        'puits': [
        [1, 0, 1],
        [1, 0, 1],
        [1, 0, 1],
        [1, 0, 1],
        [1, 1, 1],
    ],
        'diagonale': [
        [1, 0, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 1, 1, 1, 1, 1, 1, 1],
        [1, 1, 0, 0, 1, 1, 1, 1, 1, 1],
        [1, 1, 1, 0, 0, 1, 1, 1, 1, 1],
        [1, 1, 1, 1, 0, 0, 1, 1, 1, 1],
        [1, 1, 1, 1, 1, 0, 0, 1, 1, 1],
        [1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    ]

    }
    return [ligne.copy() for ligne in sols[nom]]

L'écoulement

Lors de l'écoulement, l'eau peut se déplacer dans trois directions :

• vers le bas
• vers la gauche
• vers la droite

L'animation ci-dessous présente l'écoulement dans le sol précédent.

Dans ce cas, l'eau peut atteindre les profondeurs 0 à 5, mais pas la 6 ni la 7.

La fonction à écrire

On écrira une fonction percolation prenant en argument les coordonnées de la cellule de départ (ligne i et colonne j) ainsi qu'une profondeur maximale à atteindre. La liste décrivant le sol sera déclarée dans le corps du programme et modifiée directement.

La fonction renverra True si l'eau atteint cette profondeur, False dans le cas contraire.

On utilisera une fonction récursive procédant ainsi :

• à chaque appel, on indique dans le sol que l'eau s'est écoulée jusqu'à cette cellule (on place un 2 dans la cellule correspondante)
• on vérifie ensuite que la profondeur de la cellule passée en argument est égale à la profondeur cherchée. Si c'est le cas, on renvoie True
• dans le cas contraire :
  • on vérifie que la cellule de dessous est vide. Si oui, on explore cette cellule en appelant à nouveau la fonction. Si cette exploration renvoie True, la fonction renvoie True
  • on procède de la même façon avec les cellules de gauche et de droite
  • une fois ces trois cas étudiés, si la fonction ne s'est pas encore terminée (aucune des explorations n'a renvoyé True) on renvoie False

Attention

Dans la mesure où la fonction modifie la liste Python représentant le sol (en l'inondant avec des valeurs 2), il est nécessaire de générer un nouveau sol avant chaque test

Exemples

On génère un sol sec grâce à la fonction nouveau_sol définie plus haut. Le point de départ est en i=0 et j=5.

🐍 Console Python

>>> sol = nouveau_sol()
>>> # L'eau atteint-elle la profondeur 4 ?
>>> percolation(sol, 0, 5, 4)
True

On n'oublie pas d'assécher le sol avant de faire un nouveau test :

🐍 Console Python

>>> sol = nouveau_sol()
>>> # L'eau atteint-elle la profondeur 6 ?
>>> percolation(sol, 0, 5, 6)
False

Au travail

Compléter ci-dessous la fonction percolation :

###

Lancer # Testsbksl-nlfrom copy import deepcopybksl-nlbksl-nlbasepy-undsol = [bksl-nl [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],bksl-nl [1, 1, 0, 1, 0, 0, 0, 0, 0, 1],bksl-nl [1, 1, 0, 1, 0, 1, 1, 1, 0, 1],bksl-nl [1, 1, 1, 1, 0, 1, 1, 0, 0, 1],bksl-nl [1, 0, 1, 0, 1, 0, 0, 0, 1, 1],bksl-nl [1, 0, 1, 1, 1, 1, 0, 1, 1, 1],bksl-nl [1, 1, 1, 0, 0, 1, 1, 1, 0, 1],bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl]bksl-nlbksl-nl# Test profondeur 0 (déjà atteinte)bksl-nlsol = deepcopy(basepy-undsol)bksl-nlassert percolation(sol, 0, 5, 0)bksl-nl# Test profondeur 1 (atteignable)bksl-nlsol = deepcopy(basepy-undsol)bksl-nlassert percolation(sol, 0, 5, 1)bksl-nl# Test profondeur 5 (atteignable)bksl-nlsol = deepcopy(basepy-undsol)bksl-nlassert percolation(sol, 0, 5, 5)bksl-nl# Test profondeur 6 (non atteignable)bksl-nlsol = deepcopy(basepy-undsol)bksl-nlassert not percolation(sol, 0, 5, 6)bksl-nlbksl-nl# Tests supplémentairesbksl-nlbasepy-undsol = [bksl-nl [1, 0, 1],bksl-nl [1, 0, 1],bksl-nl [1, 0, 1],bksl-nl [1, 0, 1],bksl-nl [1, 1, 1],bksl-nl]bksl-nlbksl-nl# Test profondeur 0 (déjà atteinte)bksl-nlsol = deepcopy(basepy-undsol)bksl-nlassert percolation(sol, 0, 1, 0)bksl-nl# Test profondeur 3 (atteignable)bksl-nlsol = deepcopy(basepy-undsol)bksl-nlassert percolation(sol, 0, 1, 1)bksl-nl# Test profondeur 4 (non atteignable)bksl-nlsol = deepcopy(basepy-undsol)bksl-nlassert not percolation(sol, 0, 1, 4)bksl-nlbksl-nlbasepy-undsol = [bksl-nl [1, 0, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl [1, 0, 0, 1, 1, 1, 1, 1, 1, 1],bksl-nl [1, 1, 0, 0, 1, 1, 1, 1, 1, 1],bksl-nl [1, 1, 1, 0, 0, 1, 1, 1, 1, 1],bksl-nl [1, 1, 1, 1, 0, 0, 1, 1, 1, 1],bksl-nl [1, 1, 1, 1, 1, 0, 0, 1, 1, 1],bksl-nl [1, 1, 1, 1, 1, 1, 0, 1, 1, 1],bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl]bksl-nlbksl-nl# Test profondeur 0 (déjà atteinte)bksl-nlsol = deepcopy(basepy-undsol)bksl-nlassert percolation(sol, 0, 1, 0)bksl-nl# Test profondeur 3 (atteignable)bksl-nlsol = deepcopy(basepy-undsol)bksl-nlassert percolation(sol, 0, 1, 1)bksl-nl# Test profondeur 6 (atteignable)bksl-nlsol = deepcopy(basepy-undsol)bksl-nlassert percolation(sol, 0, 1, 1)bksl-nl# Test profondeur 7 (non atteignable)bksl-nlsol = deepcopy(basepy-undsol)bksl-nlassert not percolation(sol, 0, 1, 7)bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

# --- HDR ---#bksl-nldef nouveaupy-undsol(nom="base"):bksl-nl """bksl-nl Renvoie un sol secbksl-nl Trois sols sont proposésbksl-nl Par défaut on récupère le sol 'base'bksl-nl """bksl-nl sols = {bksl-nl "base": [bksl-nl [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],bksl-nl [1, 1, 0, 1, 0, 0, 0, 0, 0, 1],bksl-nl [1, 1, 0, 1, 0, 1, 1, 1, 0, 1],bksl-nl [1, 1, 1, 1, 0, 1, 1, 0, 0, 1],bksl-nl [1, 0, 1, 0, 1, 0, 0, 0, 1, 1],bksl-nl [1, 0, 1, 1, 1, 1, 0, 1, 1, 1],bksl-nl [1, 1, 1, 0, 0, 1, 1, 1, 0, 1],bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl ],bksl-nl "puits": [bksl-nl [1, 0, 1],bksl-nl [1, 0, 1],bksl-nl [1, 0, 1],bksl-nl [1, 0, 1],bksl-nl [1, 1, 1],bksl-nl ],bksl-nl "diagonale": [bksl-nl [1, 0, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl [1, 0, 0, 1, 1, 1, 1, 1, 1, 1],bksl-nl [1, 1, 0, 0, 1, 1, 1, 1, 1, 1],bksl-nl [1, 1, 1, 0, 0, 1, 1, 1, 1, 1],bksl-nl [1, 1, 1, 1, 0, 0, 1, 1, 1, 1],bksl-nl [1, 1, 1, 1, 1, 0, 0, 1, 1, 1],bksl-nl [1, 1, 1, 1, 1, 1, 0, 1, 1, 1],bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl ],bksl-nl }bksl-nl return [ligne.copy() for ligne in sols[nom]]bksl-nlbksl-nlbksl-nl# --- HDR ---#bksl-nlTERRE = 1bksl-nlVIDE = 0bksl-nlEAU = 2bksl-nlbksl-nlbksl-nldef percolation(sol, i, j, profpy-undmax):bksl-nl sol[i][j] = ...bksl-nlbksl-nl if ... == ...:bksl-nl return Truebksl-nl else:bksl-nl if ... == VIDE:bksl-nl if percolation(sol, ..., ..., profpy-undmax):bksl-nl return Truebksl-nlbksl-nl ...bksl-nlbksl-nl ...bksl-nlbksl-nl return Falsebksl-nlbksl-nlbksl-nl# Testsbksl-nl# Test profondeur 0 (déjà atteinte)bksl-nlsol = nouveaupy-undsol()bksl-nlassert percolation(sol, 0, 5, 0)bksl-nl# Test profondeur 1 (atteignable)bksl-nlsol = nouveaupy-undsol()bksl-nlassert percolation(sol, 0, 5, 1)bksl-nl# Test profondeur 5 (atteignable)bksl-nlsol = nouveaupy-undsol()bksl-nlassert percolation(sol, 0, 5, 5)bksl-nl# Test profondeur 6 (non atteignable)bksl-nlsol = nouveaupy-undsol()bksl-nlassert not percolation(sol, 0, 5, 6)bksl-nlbksl-nlTERRE = 1bksl-nlVIDE = 0bksl-nlEAU = 2bksl-nlbksl-nlbksl-nldef percolation(sol, i, j, profpy-undmax):bksl-nl sol[i][j] = EAUbksl-nlbksl-nl if i == profpy-undmax:bksl-nl return Truebksl-nl else:bksl-nl if sol[i + 1][j] == VIDE:bksl-nl if percolation(sol, i + 1, j, profpy-undmax):bksl-nl return Truebksl-nlbksl-nl if sol[i][j - 1] == VIDE:bksl-nl if percolation(sol, i, j - 1, profpy-undmax):bksl-nl return Truebksl-nlbksl-nl if sol[i][j + 1] == VIDE:bksl-nl if percolation(sol, i, j + 1, profpy-undmax):bksl-nl return Truebksl-nlbksl-nl return Falsebksl-nlbksl-nlbksl-nldef nouveaupy-undsol(nom="base"):bksl-nl """bksl-nl Renvoie un sol secbksl-nl Trois sols sont proposésbksl-nl Par défaut on récupère le sol 'base'bksl-nl """bksl-nl sols = {bksl-nl "base": [bksl-nl [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],bksl-nl [1, 1, 0, 1, 0, 0, 0, 0, 0, 1],bksl-nl [1, 1, 0, 1, 0, 1, 1, 1, 0, 1],bksl-nl [1, 1, 1, 1, 0, 1, 1, 0, 0, 1],bksl-nl [1, 0, 1, 0, 1, 0, 0, 0, 1, 1],bksl-nl [1, 0, 1, 1, 1, 1, 0, 1, 1, 1],bksl-nl [1, 1, 1, 0, 0, 1, 1, 1, 0, 1],bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl ],bksl-nl "puits": [bksl-nl [1, 0, 1],bksl-nl [1, 0, 1],bksl-nl [1, 0, 1],bksl-nl [1, 0, 1],bksl-nl [1, 1, 1],bksl-nl ],bksl-nl "diagonale": [bksl-nl [1, 0, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl [1, 0, 0, 1, 1, 1, 1, 1, 1, 1],bksl-nl [1, 1, 0, 0, 1, 1, 1, 1, 1, 1],bksl-nl [1, 1, 1, 0, 0, 1, 1, 1, 1, 1],bksl-nl [1, 1, 1, 1, 0, 0, 1, 1, 1, 1],bksl-nl [1, 1, 1, 1, 1, 0, 0, 1, 1, 1],bksl-nl [1, 1, 1, 1, 1, 1, 0, 1, 1, 1],bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl ],bksl-nl }bksl-nl return [ligne.copy() for ligne in sols[nom]]bksl-nlbksl-nl

A

On utilise par commodité les variables VIDE et EAU définies.

Dès la première ligne, on indique dans le sol que l'eau s'est écoulée jusqu'à cette cellule. Cette action empêchera de reconsidérer des cellules déjà visitées.

On teste ensuite le cas de base de la récursivité : la profondeur de la cellule actuelle est-elle égale à la profondeur visée ? Si oui, on renvoie True.

Dans le cas contraire, on explore successivement les trois directions (bas, gauche, droite) :

• Pour chacune, on vérifie tout d'abord que la cellule est vide

• Si c'est le cas, on teste alors le retour de l'appel percolation(sol, nouveau_i, nouveau_j, prof_max). S'il vaut True, on renvoie directement True

• Si aucune des explorations n'a renvoyé True, on ne peut pas atteindre la profondeur souhaitée : on renvoie False

Z