~~DISCUSSION~~
Le “jeu de la vie” est un automate cellulaire simple imaginé par John Conwell en 1970.
Il est composé d'une grille dont chaque cellule peut être dans deux états : vivante ou morte, modifié au cours du temps selon les trois règles suivantes :
Les voisines d'une cellule sont les huit cellules l'entourant : N, S, E, O, NE, NO, SE, SO.
La programmation de cet automate est assez simple, il s'agit généralement de créer et manipuler un tableau de deux dimensions.
Ce travail - en python - vise à créer le moteur fonctionnel de l'automate (et son affichage en console) le plus optimisé possible… en moins de lignes possible.
Ce programme utilise au maximum générateurs, listes et diverses syntaxes courtes, et un tableau d'une seule dimension parcouru par une seule boucle associé à une technique d'index relatifs permettant de l'analyser comme une grille en deux dimensions.
Le programme crée une grille de taille donnée, la remplit aléatoirement selon un taux de remplissage, la calcule et met à jour selon les règles de l'automate cellulaire puis l'affiche en console (en indiquant chaque cellule vivante par son nombre de voisins) quand l'utilisateur le demande, et permet de quitter le programme simplement.
Le code fait 13 lignes et 334 caractères.
from random import random l=10 r=range(l*l) n=(1,-1,l,-l,l+1,l-1,-l+1,-l-1) g=list(int(random()*1.8) for i in r) while not raw_input(): p = list(g) for i in r: s = sum(p[i+x] for x in n if 0<i+x<l*l) if not p[i] and s==3 : g[i]=1 if p[i] and (s<2 or s>3): g[i]=0 print chr(32+p[i]*(16+s)), if i+1 and not (i+1)%l: print
Appuyer sur ↵ Enter pour calculer un cycle, rester appuyé pour calculer en boucle.
Appuyer sur n'importe quelle touche et appuyer sur ↵ Enter pour quitter.
Je décrit ci-dessous le fonctionnement du programme, ligne par ligne.
from random import random
Importation du module d'aléatoire utilisé pour remplir initialement la grille.
l=10
l comme length : définit la largeur (et longueur) de la grille en nombre de cases. Pour être visible sans problème en console, préférer un tableau inférieur à 50×50 cases. Le programme peut toutefois calculer sans problème un tableau de 600×600 cases par exemple (hors affichage).
r=range(l*l)
r comme range : liste des index des cases de la grille utilisée pour la créer et la parcourir. La grille est de taille l*l afin de correspondre à une grille de deux-dimensions de côté l.
Cette liste est pré-calculée pour une question de performance, cf. python benchmark.
n=(1,-1,l,-l,l+1,l-1,-l+1,-l-1)
n comme neighbours : Cette liste décrit les index relatifs des huit voisins dans le tableau d'une seule dimension. Le processus est détaillé plus bas.
g=list(int(random()*1.8) for i in r)
g comme grid.
Il s'agit d'un générateur de liste utilisant la syntaxe :
list(value for i in range)
C'est proche de la syntaxe courte de boucle :
[value for i in range]
Mais préférable pour des questions de performance. Cf. Generator Expressions.
La valeur ajoutée à la liste est une manière d'obtenir aléatoirement soit 0 soit 1 : convertir en entier la valeur à virgule flottante aléatoire comprise entre 0 et 1 renvoyée par random().
int(random()*1.8)
1.8 est donc un “taux de remplissage” de la grille pouvant être manipulé entre 0 (0*0 < résultat < 0*1, donc grille toujours vide) et 1.99 (1.99*0 < résultat < 1.99*1, donc grille aléatoirement remplie).
while not raw_input(): p=list(g)
Cette boucle permet de mettre à jour la grille en appuyant sur ↵ Enter (la condition d'exécution est vraie puisque raw_input() n'a rien renvoyé).
Pour stopper le programme, entrer n'importe quelle valeur puis appuyer sur ↵ Enter (la condition d'exécution est fausse puisque raw_input() a renvoyé une valeur).
p comme previous est une copie de la grille permettant par la suite l'analyse de la grille dans son état précédent, non modifié, tout en modifiant l'état actuel.
for i in r:
On répète l'opération suivante pour chaque élément de r, i correspondant donc tour à tour à l'index de chaque cellule de la grille.
Pour savoir le nombre de voisins vivants, il faut faire la somme de l'état des huit voisins.
s=sum(p[i+x] for x in n if 0<i+x<l*l)
Il s'agit encore d'un générateur de liste créant la liste des états des huit voisins, intégré à la fonction sum() retournant directement la somme chacun des éléments de la liste.
Cette ligne est similaire à :
nbrsList = [] for x in n: if 0 < i+x < l*l: nbrsList.append(last[i+x]) s = sum(nbrsList)
On ajoute les index relatifs stockés dans n à l'index courant i pour déterminer l'index des voisins i+x. L'état des voisin lors du cycle précédent est alors déterminé par last[i+x].
Par exemple n[0] est 1, l'index de ce voisin est i+1 et son état p[i+1], ce qui correspond à la case suivante du tableau, donc au voisin de droite.
Description des index relatifs :
1 : case suivante du tableau, EST.-1 : case précédente du tableau, OUEST.l : case située une longueur de ligne après, SUD.-l : case située une longueur de ligne avant, NORD.l+1 : case située une longueur de ligne plus une case après, SUD-EST.l-1 : case située une longueur de ligne moins une case après, SUD-OUEST.-l+1 : case située une longueur de ligne plus une case avant, NORD-EST.-l-1 : case située une longueur de ligne moins une case avant, NORD-OUEST.
La condition impose que l'index du voisin soit bien dans le tableau (une cellule au bord de la grille va observer des cases qui n'existent pas), c'est à dire que son index soit supérieur à 0 et inférieur à la taille du tableau :
if 0<i+x<l*l
La syntaxe x < y < z, peu courante dans d'autres langages, correspond à x < y and y < z.
La technique de la première version de “bordure morte” n'a pas été réutilisée car elle s'avère peu utile dans un tableau uni-dimensionnel n'ayant que deux bords à vérifier. Mais du coup les bords droite/gauche de la grille sont infinis (un objet sortant à droite réapparaît à gauche).
Les règles énoncées plus haut peuvent être décrites en deux règles générales de changement.
if not p[i] and s==3:g[i]=1
Si l'état de la cellule courante est 0 (morte), mais que la somme des voisins vivants est égal à 3, on change son état à 1 (vivante).
if p[i] and(s<2 or s>3):g[i]=0
Si l'état de la cellule courante est 1 (vivante), mais que la somme des voisins vivants n'est pas comprise entre 2 et 3, on change son état à 0 (morte).
Si la cellule ne correspond pas à ces règles, on ne change pas son état.
print chr(32+p[i]*(16+s)),
Cette ligne affiche un espace pour les cellules mortes et le nombre de voisins pour les cellules vivantes, en générant le code ASCII en base 10 du caractère visé. Cf. ASCII et chr()
Si la cellule est morte, le calcul sera 32+0*(16+s) donc toujours 32, qui est le code ASCII du caractère Espace.
Si la cellule est vivante, le calcul sera 32+1*(16+s) donc toujours 48+s. A 48 (le code du chiffre 0) est rajouté le nombre de voisins, ce qui donne 49 (le code du chiffre 1), 50 (le code du chiffre 2), etc…
if i+1 and not(i+1)%l:print
On va à la ligne pour les index multiplicateurs de la largeur de la grille afin d'afficher le tableau en deux dimensions.
Les temps ci-après concernent l'exécution du programme légèrement modifié afin d'indiquer une moyenne (sur 100 cycles) des temps de calcul sans affichage de la grille en console :
from time import time t=time() cycles = 100 from random import random l=100 r=range(l*l) n=(1,-1,l,-l,l+1,l-1,-l+1,-l-1) g=list(int(random()*1.8) for i in r) for bench in range(cycles): p=list(g) for i in r: s=sum(p[i+x] for x in n if 0<i+x<l*l) if not p[i] and s==3:g[i]=1 if p[i] and(s<2 or s>3):g[i]=0 print str((time()-t) / cycles)
| Taille | Nombre de cellules | Secondes par cycle | Cycles par seconde |
|---|---|---|---|
50 | 5.000 | 0.0068 | 147 |
100 | 10.000 | 0.0267 | 37.2 |
500 | 250.000 | 0.6934 | 1.67 |
600 | 360.000 | 1.0087 | 0.99 |
Cette version utilise certaines syntaxes courtes, un tableau à deux dimensions et affiche l'état de toutes les cellules un certain nombre de fois.
19 lignes, les trois lignes d'affichage en console comprises.
from random import random l = 500 rng = range(1, l+1) d = (0,1, 0,-1, 1,0, -1,0, 1,1, 1,-1, -1,1, -1,-1) w = [[0]*(l+2)]*(l+2) for i in rng: for j in rng: w[i][j] = int(random()*1.8) for t in range(5): w2 = list(w) for i in rng: for j in rng: sum = 0 for y in range(0,len(d),2): sum += w2[i+d[y]][j+d[y+1]] if w2[i][j] == 0 : if sum == 3 : w[i][j] = 1 elif sum < 2 or sum > 3: w[i][j] = 0 print str(w[i][j]), print print
Un problème à résoudre pour l'optimisation du code était de trouver un moyen court et efficace d'éviter les cases inexistantes. Lorsqu'une cellule est au bord de la grille, elle n'a pas huit voisins, le processus doit donc s'assurer de ne pas demander l'état de cases en dehors du tableau.
Pour éviter l'ajout de conditions, lourdes car à calculer pour chaque case pour chaque cycle et prenant plusieurs lignes, il a été choisi d'ajouter au tableau de côté l une bordure d'une cellule d'état 0.
Le tableau réel est donc de côté l+2…
[[0]*(l+2)]*(l+2)
…et le processus de mise à jour et l'affichage ne concerne que les case de (1, 1) à (l, l) :
range(1, l+1)
Toutes les cellules mises à jour ayant alors bien huit voisines et les bordures n'ayant aucune influence sur le résultat des règles car toujours définies à 0, il n'est plus besoin d'ajouter une quelconque condition durant le processus.
Cette version s'exécute (hors affichage en console) en 0.9613 secondes par cycle (1.04 cycles par seconde) pour une grille de 500×500, soit 250.000 cellules.