NSI, TP percolation 1

La fonction grille() à compléter :

from random import *
import matplotlib.pyplot as plt
import numpy as np

def grille(largeur,hauteur,densite):
    '''
    génère une grille sous la forme d'un tuple de tuples
    de largeur et hauteur données
    chaque élément de la grille a la probabilité densité
    d'être plein
    largeur : int
    hauteur : int
    densite : float
    return : tuple
    exemple : grille(10,10,0.1) retournera une grille aléatoire
    du type
    ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 1, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 1, 0, 0, 0, 1),
    (0, 0, 0, 0, 0, 0, 0, 0, 1, 0),
    (0, 0, 1, 0, 0, 0, 0, 1, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 1, 0),
    (0, 0, 0, 1, 0, 1, 0, 0, 0, 1),
    (0, 1, 0, 0, 0, 0, 0, 1, 0, 0))
    '''

La fonction afficher()

def afficher(grille):
    '''
    affichage de la grille
    '''
    hauteur=len(grille)
    largeur=len(grille[0])
    grille_a_afficher=np.zeros((largeur,hauteur))
    for i in range(hauteur):
        for j in range(largeur):
            grille_a_afficher[j,i]=grille[j][i]    
    plt.spy(grille_a_afficher)
    plt.show()

La fonction fréquence à compléter :

def frequence(grille):
    '''
    retourne la frequence des 1 présents dans la grille
    grille : tuple de tuples
    return : float
    >>> g=((0, 0, 0, 0, 0, 0, 1, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 1, 0, 1),
    (0, 0, 0, 1, 1, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 1, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0))
    >>>print(frequence(g))
    0.06
    '''

La fonction amas() à compléter :

def amas(grille):
    '''
    détermine les amas de cases vides de la grille
    en partant du haut et de manière ordonnée
    grille : tuple de tuples contenant des 0 et des 1
    return : tuple constitué de tuples contenant les coordonnées
    des cases formant un même amas
    >>>g=(
    (0, 0, 1, 0, 0, 0, 1, 0, 1, 1),
    (1, 1, 0, 1, 0, 0, 1, 0, 0, 1),
    (0, 0, 1, 1, 1, 1, 0, 1, 0, 1),
    (1, 0, 1, 1, 1, 0, 0, 1, 0, 0),
    (0, 1, 1, 1, 0, 1, 0, 1, 1, 0),
    (1, 1, 0, 0, 0, 1, 1, 0, 0, 0),
    (0, 1, 0, 1, 0, 0, 1, 0, 0, 1),
    (1, 0, 1, 0, 0, 1, 0, 1, 0, 0),
    (0, 0, 0, 1, 1, 0, 0, 1, 1, 0),
    (1, 1, 1, 0, 0, 0, 0, 1, 0, 0))
    >>> amas(grille)
    (((0,0),(1,0)),
    ((3,0),(4,0),(5,0),(4,1),(5,1)),
    ((7,0),(7,1),(8,1),(8,2),(8,3),(9,3),
    (9,4),(7,5),(8,5),(9,5),(7,6),(8,6),
    (8,7),(9,7),(9,8),(8,9),(9,9)))
    '''

Proposition de correction

from random import *
import matplotlib.pyplot as plt
import numpy as np

def grille(largeur,hauteur,densite):
    '''
    génère une grille sous la forme d'un tuple de tuples
    de largeur et hauteur données
    chaque élément de la grille a la probabilité densité
    d'être plein
    largeur : int
    hauteur : int
    densite : float
    return : tuple
    exemple : grille(10,10,0.1) retournera une grille aléatoire
    du type
    ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 1, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 1, 0, 0, 0, 1),
    (0, 0, 0, 0, 0, 0, 0, 0, 1, 0),
    (0, 0, 1, 0, 0, 0, 0, 1, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 1, 0),
    (0, 0, 0, 1, 0, 1, 0, 0, 0, 1),
    (0, 1, 0, 0, 0, 0, 0, 1, 0, 0))
    '''
    grille=()
    for j in range(hauteur):
        ligne=()
        for i in range(largeur):
            if random()<densite:
                ligne+=(1,)
            else :
                ligne+=(0,)
        grille+=(ligne,)
    return grille
                
def frequence(grille):
    '''
    retourne la frequence des 1 présents dans la grille
    grille : tuple de tuples
    return : float
    >>> g=((0, 0, 0, 0, 0, 0, 1, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 1, 0, 1),
    (0, 0, 0, 1, 1, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 1, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0))
    >>>print(frequence(g))
    0.06
    '''
    compteur=0
    for j in range(len(grille)):
        for i in range(len(grille)):
            if grille[j][i]==1:
                compteur+=1
    return compteur/((i+1)*(j+1))

def afficher(grille):
    '''
    affichage de la grille
    '''
    hauteur=len(grille)
    largeur=len(grille[0])
    grille_a_afficher=np.zeros((largeur,hauteur))
    for i in range(hauteur):
        for j in range(largeur):
            grille_a_afficher[j,i]=grille[j][i]    
    plt.spy(grille_a_afficher)
    plt.show()

def afficher_amas(grille,mes_amas):
    hauteur=len(grille)
    largeur=len(grille[0])
    grille_a_afficher=np.zeros((largeur,hauteur))
    for i in range(hauteur):
        for j in range(largeur):
            if not(cellule_pas_dans_mes_amas(mes_amas,i,j)):
                grille_a_afficher[j][i]=1
    plt.spy(grille_a_afficher)
    plt.show()
    
    
    
def amas(grille):
    '''
    détermine les amas de cases vides de la grille
    en partant du haut et de manière ordonnée
    grille : tuple de tuples contenant des 0 et des 1
    return : tuple constitué de tuples contenant les coordonnées
    des cases formant un même amas
    >>>g=(
    (0, 0, 1, 0, 0, 0, 1, 0, 1, 1),
    (1, 1, 0, 1, 0, 0, 1, 0, 0, 1),
    (0, 0, 1, 1, 1, 1, 0, 1, 0, 1),
    (1, 0, 1, 1, 1, 0, 0, 1, 0, 0),
    (0, 1, 1, 1, 0, 1, 0, 1, 1, 0),
    (1, 1, 0, 0, 0, 1, 1, 0, 0, 0),
    (0, 1, 0, 1, 0, 0, 1, 0, 0, 1),
    (1, 0, 1, 0, 0, 1, 0, 1, 0, 0),
    (0, 0, 0, 1, 1, 0, 0, 1, 1, 0),
    (1, 1, 1, 0, 0, 0, 0, 1, 0, 0))
    >>> amas(grille)
    (((0,0),(1,0)),
    ((3,0),(4,0),(5,0),(4,1),(5,1)),
    ((7,0),(7,1),(8,1),(8,2),(8,3),(9,3),
    (9,4),(7,5),(8,5),(9,5),(7,6),(8,6),
    (8,7),(9,7),(9,8),(8,9),(9,9)))
    '''
    mes_amas=()
    for i in range(len(grille[0])):
        if grille[0][i]==0 and cellule_pas_dans_mes_amas(mes_amas,i,0):
            amas=((i,0),)
            frontiere=bord_cellules_amas(amas,grille,mes_amas)
            while len(frontiere)!=0:
                amas+=frontiere
                frontiere=bord_cellules_amas(frontiere,grille,amas)
            mes_amas+=(amas,)
    
    
    return mes_amas

def cellule_pas_dans_amas(mon_amas,x,y):
    '''
    détermine si une case appartient à un amas
    : mes_amas : tuple de tuples contenant nos amas
    : x,y : int coordonnées de la case
    : return : bolléen
    >>> amas=(
    ((0,0)),
    ((3,0),(4,0),(4,1))
    )
    >>> cellule_pas_dans_amas_finaux(amas,4,0)
    False
    >>> cellule_pas_dans_amas_finaux(amas_finaux,3,1)
    True
    '''
    if (x,y) in mon_amas :
            return False
    return True

def cellule_pas_dans_mes_amas(mes_amas,x,y):
    '''
    détermine si une case appartient à un ensemble d'amas
    : mes_amas : tuple de tuples contenant nos amas
    : x,y : int coordonnées de la case
    : return : bolléen
    >>> amas=(
    ((0,0)),
    ((3,0),(4,0),(4,1))
    )
    >>> cellule_pas_dans_amas_finaux(amas,4,0)
    False
    >>> cellule_pas_dans_amas_finaux(amas_finaux,3,1)
    True
    '''
    for amas in mes_amas:
        if (x,y) in amas :
            return False
    return True
               
            
def bord_cellules_amas(amas,grille,mes_amas):
    '''
    détermine les cellules adjacentes l'amas
    et n'appartenant pas à cet amas en construction et aux
    amas déjà déterminés
    : amas : tuple
    : grille : tuple
    : amas : tuple
    : return : tuple contenant les coordonnées des cellules voisines d'un amas
    >>>g=(
    (0, 0, 1, 0, 0, 0, 1, 0, 1, 1),
    (1, 1, 0, 1, 0, 0, 1, 0, 0, 1),
    (0, 0, 1, 1, 1, 1, 0, 1, 0, 1),
    (1, 0, 1, 1, 1, 0, 0, 1, 0, 0),
    (0, 1, 1, 1, 0, 1, 0, 1, 1, 0),
    (1, 1, 0, 0, 0, 1, 1, 0, 0, 0),
    (0, 1, 0, 1, 0, 0, 1, 0, 0, 1),
    (1, 0, 1, 0, 0, 1, 0, 1, 0, 0),
    (0, 0, 0, 1, 1, 0, 0, 1, 1, 0),
    (1, 1, 1, 0, 0, 0, 0, 1, 0, 0))
    >>> mes_amas=(
    ((0,0),(1,0)),
    ((3,0),(4,0)),
    )
    >>> cases=(
    (5,0),(4,1)
    )
    >>> print(bord_cellules_amas(cases,g,mes_amas))
    ((5,1),)
    >>>>>> cases=(
    (7,0),(1,0)
    )
    >>> print(bord_cellules_amas(cases,g,mes_amas))
    ((7,1),)
    '''
    retour=()
    for case in amas :
        x=case[0]
        y=case[1]
        if x<len(grille[0])-1:
            if grille[y][x+1]==0 and cellule_pas_dans_amas(mes_amas,x+1,y) and cellule_pas_dans_mes_amas(mes_amas,x+1,y):
                retour+=((x+1,y),)
        if x>0 :
            if grille[y][x-1]==0 and cellule_pas_dans_amas(mes_amas,x-1,y) and cellule_pas_dans_mes_amas(mes_amas,x-1,y):
                retour+=((x-1,y),)
        if y>0 :
            if grille[y-1][x]==0 and cellule_pas_dans_amas(mes_amas,x,y-1) and cellule_pas_dans_mes_amas(mes_amas,y-1,y):
                retour+=((x,y-1),)
        if y<len(grille)-1:
            if grille[y+1][x]==0 and cellule_pas_dans_amas(mes_amas,x,y+1) and cellule_pas_dans_mes_amas(mes_amas,x,y+1):
                retour+=((x,y+1),)
    return on_enleve_les_doublons(retour)

def on_enleve_les_doublons(mon_tuple):
    '''
    retourne un tuple sans éléments en plusieurs exemplaires
    : mon_tuple : tuple
    : retour : tuple
    >>> mon_tuple=((1,1),(0,1),(1,1),(2,1))
    >>> print(on_enleve_les_doublons(mon_tuple))
    ((1,1),(0,1),(2,1))
    '''
    retour =()
    for elt in mon_tuple :
        if not(elt in retour):
            retour+=(elt,)
    return retour

def percolation(grille,mes_amas):
    '''
    détermine si un mas présent dans les amas réalise
    la percolation
    : grille : tuple de tuples
    : mes_amas : tuple de tuples
    : return : True si il y a percolation, False sinon
    >>> g=((1, 0, 1, 1, 0, 1, 0, 1, 0, 1),
    (0, 1, 1, 0, 1, 0, 1, 1, 1, 0),
    (0, 0, 0, 0, 0, 1, 0, 0, 1, 0),
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
    (0, 1, 0, 0, 0, 0, 1, 0, 1, 0),
    (1, 1, 0, 0, 0, 1, 1, 0, 0, 0), 
    0, 0, 1, 0, 0, 0, 1, 1, 0, 0),
    (1, 0, 1, 0, 0, 1, 0, 1, 1, 0),
    (0, 1, 0, 0, 1, 1, 1, 1, 0, 1))
    >>> amas=(((1, 0),), ((4, 0),), ((6, 0),), ((8, 0),))
    >>> print(percolation(grille,mes_amas))
    True
    >>>g=((0, 0, 0, 0, 0, 0, 0, 0, 0, 0), 
    (0, 1, 0, 0, 1, 0, 1, 0, 0, 0), 
    (0, 0, 1, 1, 0, 0, 0, 1, 0, 0), 
    (0, 0, 1, 1, 1, 1, 1, 0, 1, 0), 
    (1, 0, 0, 1, 0, 0, 1, 0, 1, 1), 
    (1, 0, 0, 1, 0, 0, 1, 1, 0, 1), 
    (1, 1, 1, 0, 1, 0, 0, 0, 0, 0), 
    (0, 1, 0, 1, 0, 0, 0, 1, 1, 0), 
    (1, 0, 0, 0, 0, 0, 1, 1, 0, 0), 
    (0, 0, 1, 1, 1, 0, 0, 0, 0, 0))
    >>> amas=(((0, 0), (1, 0), (0, 1), (2, 0), (0, 2), (3, 0), (2, 1), (1, 2), (0, 3), (4, 0), (3, 1), (1, 3), (5, 0), (1, 4), (6, 0), (5, 1), (2, 4), (1, 5), (7, 0), (5, 2), (2, 5), (8, 0), (7, 1), (6, 2), (4, 2), (9, 0), (8, 1), (9, 1), (8, 2), (9, 2), (9, 3)),)
    >>> print(percolation(grille,mes_amas))
    False
    '''