Une « partie » se déroule sur une grille, théoriquement infinie, divisée en cellules carrées. Chaque cellule est soit « vivante », soit « morte ».
On appelle voisin d'une cellule, une cellule qui partage au moins un « coin » avec celle-ci. On a représenté ci-dessous une cellule (coloriée) et ses huit voisins (pointés).
L'état actuel d'une grille représente une « génération ». Afin de calculer la génération suivante, on parcourt toutes les cellules de la grille actuelle et, pour chacune, on applique l'une des règles suivantes :
si elle est morte et possède exactement trois voisines vivantes alors elle sera vivante à la prochaine génération. Si elle ne possède pas trois voisines vivantes, elle reste morte ;
si elle est vivante et possède deux ou trois voisines vivantes alors elle restera vivante à la prochaine génération. Dans le cas contraire, elle meurt.
Malgré leur simplicité, ces règles permettent d'engendrer des comportements complexes1.
On se propose dans cet exercice de mettre en œuvre le jeu de la vie avec Python. Pour cela, plusieurs questions sont proposées. Ces questions sont indépendantes et peuvent être traitées dans l'ordre souhaité. La dernière question regroupe l'ensemble du code et permet de visualiser l'évolution d'une grille.
La grille de jeu sera représentée par une liste de listes contenant les valeurs 0 (cellule morte) ou 1 (cellule vivante). On garantit que les grilles sont toutes des carrés de largeur et hauteur égales à un entier \(n\) strictement positif.
Dans toute la suite, les variables i désigneront des indices de lignes et j des indices de colonnes.
On fournit une fonction grille_aleatoire qui prend pour paramètres la dimension taille d'une grille (taille est un entier strictement positif indiquant le nombre de lignes et de colonnes de la grille) et un nombre flottant proba_vie (compris entre 0.0 et 1.0). Cette fonction renvoie une grille de la dimension souhaitée dans laquelle chaque cellule à une probabilité proba_vie d'être vivante.
Ainsi :
grille_aleatoire(7,0.3) renvoie une grille de \(7\times 7\) dans laquelle chaque cellule a une probabilité de \(p=0,3\) d'être vivante ;
grille_aleatoire(10,0.0) renvoie une grille de \(10\times 10\) entièrement remplie de cellules mortes.
Cette fonction est d'ores et déjà accessible dans tous les éditeurs. Il est inutile de l'importer.
Code de grille_aleatoire
On fournit le code de la fonction grille_aleatoire pour information.
On propose dans un premier temps de visualiser le fonctionnement du jeu de la vie en observant l'évolution d'une grille lors de plusieurs générations.
On fournit donc une fonction visualisation qui prend en paramètres une liste de listes grille représentant l'état initial de la grille et un entier nb_generations qui indique le nombre de générations à simuler.
Cette fonction calcule l'état de la grille au fil du nombre de générations indiquées et dessine la grille correspondante sous l'éditeur. À ce titre certains réglages sont modifiables par le biais des variables TAILLE_CELLULE (taille d'une cellule en pixels), DELAI_SECONDES (délai entre les affichages de deux grilles) et COULEUR_VIVANTE (couleur d'une cellule vivante).
Cette section ne comporte pas de tests mais seulement une représentation visuelle. Vous pouvez l'utiliser afin de tester des grilles aléatoires ou des motifs particuliers.
Restons raisonnables
Ne perdez pas de vue que nous travaillons dans le navigateur et que l'exécution de code Python n'est pas immédiate.
Dessiner des grilles de grande taille ou demander un grand nombre de générations risque dans certains cas de ralentir le fonctionnement du navigateur.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
La grille sera dessinée ici
Voisins valides
Une grille étant donnée, on souhaite calculer la grille de la génération suivante. Pour cela, il faut, pour chaque cellule, compter son nombre de voisins vivants.
Les cellules du centre de la grille ont bien huit voisins. Celles des « bords » n'en possèdent toutefois pas huit. Une cellule située dans un « coin » de la grille ne possède par exemple que trois voisins.
On demande dans un premier temps d'écrire une fonction voisins qui prend en paramètres une liste de listes grille représentant une grille ainsi que deux coordonnées valides i et j et renvoie la liste des coordonnées des voisins de la cellule de coordonnées (i,j).
Égalité de listes
Les tests de cet exercice utilisent une fonction egales qui renvoie True si les deux listes passées en paramètres contiennent exactement les mêmes éléments sans tenir compte de leur ordre d'apparition dans chacune.
Une version fonctionnelle de la fonction voisins de la question précédente est disponible dans cette question. Il est inutile de l'importer.
Cette fonction étant connue, il faut désormais parcourir l'ensemble des voisins valides d'une cellule afin de connaître le nombre de voisins vivants parmi ceux-ci.
On demande d'écrire une fonction voisins_vivants qui prend en paramètres une liste de listes grille représentant une grille ainsi que deux coordonnées valides i et j et renvoie le nombre de voisins vivants de la cellule de coordonnées (i,j).
Des versions fonctionnelles des fonctions voisins et voisins_vivants des questions précédentes sont disponibles dans cette question. Il est inutile de les importer.
Ces fonctions étant connues, on peut désormais, connaissant une grille, calculer la grille à la génération suivante. Pour ce faire :
on crée une nouvelle grille ne contenant que des cellules mortes,
on parcourt toutes les cellules de la grille actuelle et, pour chacune, on met à jour l'état de la cellule correspondante de la génération suivante en appliquant les règles du jeu de la vie.
On rappelle les règles du jeu :
si la cellule actuelle est morte et possède exactement trois voisines vivantes alors elle sera vivante à la prochaine génération. Si elle ne possède pas trois voisines vivantes, elle reste morte ;
si la cellule actuelle est vivante et possède deux ou trois voisines vivantes alors elle restera vivante à la prochaine génération. Dans le cas contraire, elle meurt.
On demande d'écrire une fonction generation qui prend en paramètres une liste de listes grille représentant une grille et renvoie une nouvelle grille représentant la génération suivante.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)