Numpy, matplotlib et Game of life

Documentation:

Pour ce TP et les suivants, il est nécessaire d’utiliser la version Python installée sous ~herbrete/public/python:

  • pour l’activer: taper source ~herbrete/public/python/bin/activate dans un terminal. Votre prompt change indiquant que vous êtes maintenant dans l’environnement nommé (python)
  • pour le déactiver: taper deactivate dans la terminal

Utilisation de numpy

Le module numpy permet la représentation de données sous la forme de tableaux multidimensionels à données homogènes. Il fournit des opérations de base sur ces tableaux: tri, recherche, filtrage, etc. Ce module est utlisé par de nombreux autres modules, dont scipy (calcul scientifique), matplotlib (représentation de données), pandas (analyse de données),…

Afin d’utiliser le module numpy, il est nécessaire de l’importer. Les exercices suivants seront réalisés dans l’interpréteur REPL.

import numpy as np   # raccourci

Tableaux 1D

a = np.array([1,2,3])
a
a[0]
a[2]
a[5]
a.dtype
a.size

Comment est construit le tableau référencé par a? Que contient-il? Quelle la taille de a?

np.array([1, 0.2])
_.dtype

À quoi fait référence _? Quel est le type de chacun des éléments du tableau?

np.array([1, "youpi"])
_.dtype

Quel est le type du tableau et de ses éléments?

np.zeros(5)
np.ones(4, dtype=int)
np.empty(6)
np.full(10, 8)
np.random.random(10)
np.random.choice(range(255), 10)
np.arange(4)
np.arange(2,9,2)

Que fait np.empty? Et np.arange? (rappel: help)

np.linspace(-1, 1, num=10)

Que retourne np.linspace?

Tableaux multi-dimensionnels

a.ndim
a.shape

Combien a possède-t-il de dimensions? Quelle est la taille de chacune de ses dimensions?

b = np.array([[[0, 1, 2, 3],
               [4, 5, 6, 7]],
              [[0, 1, 2, 3],
               [4, 5, 6, 7]],
              [[0 ,1 ,2, 3],
               [4, 5, 6, 7]]])
b.ndim
b.shape
b.size

Combien b possède-t-il de dimensions? Quelle est la taille de chacune? Combien b contient-il de valeurs?

np.ones((2,3))

Quelle information donne le paramètre (2,3) de np.ones ci-dessus?

Opérations sur les tableaux

aa = a
a[0] = 0
aa
acopy = a.copy()
a[0] = 1
acopy

Que fait l’opérateur d’affectation = sur les tableaux? Que fait la méthode copy()?

c = np.array([2,5,3,1,8,4,6])
c.sort()
c

np.concatenate((a,c))
_.shape

a + acopy
a - acopy
a * acopy
acopy / a
acopy // a
a + c
b * a

Comment fonctionnent les opérateurs sur les tableaux?

a + 1.5
a * 10
a ** 2
2 ** a
3.5 / a
a // 2
b ** 2

Comment fonctionne le broadcasting qui permet d’opérer sur des tableaux et des valeurs?

np.max(c)
np.argmax(c)
np.min(c)
np.argmin(c)
np.sum(c)
np.mean(c)

Que renvoient les méthodes argmin et argmax?

Manipulations de matrices

np.ones((3,4))
np.zeros((2,3), dtype=int)
np.random.random((2,3))

Quel est le type des paramètres (3,4) et (2,3)?

m = np.array([[1,2],[3,4]])
m

Quelle est la dimension de la matrice m?

v = np.array([1, 1])
v

Quelle est la dimension du vecteur v?

np.max(m)
np.min(m)
np.max(m, axis=0)
np.max(m, axis=1)

À quoi correspond axis? Et les valeurs axis=0 et axis=1?

m + v
m - v
v - m
v * m
v / m

Comment fonctionne le broadcasting sur les matrices?

m @ v
v @ m

Que fait l’opérateur @? Quelle est la différence entre l’opérateur * et l’opérateur @?

m.transpose()

Que retourne la méthode transpose()?

Programmation du jeu de la vie de Conway

Le jeu de la vie a été introduit par John Horton Conway en 1970. Le modèle de calcul sous-jacent: les automates cellulaires, bien que disposant de règles de calcul très simples, est Turing-complet.

Principe du jeu

Le jeu se déroule sur une grille 2D de taile $N \times N$ avec $N \ge 3$. Les cases de la grille peuvent contenir un 1 (case habitée) ou un 0 (case vide). À chaque tour de jeu, l’état de chaque case est mis à jour. une case reste habitée si elle possède suffisamment de voisins, mais pas trop sinon elle se vide. Une case vide, devient habitée si elle possède suffisamment de voisins mais pas trop. Vous pouvez expérimenter la dynamique du jeu sur ce simulateur.

Dans cette partie, nous utiliserons à la fois le module numpy et le module matplotlib (plus précisément son sous-module pyplot):

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

Calculer les cases voisines

Les voisins d’une case sont les 8 cases qui l’entourent. Les cases situées au bord de la grille ont une partie de leurs voisins sur le bord opposé.

Considérons une grille de taille $N=5$

  1. quels sont les voisins de la case (1,2)?
  2. quels sont les voisins de la case (3,4)?
  3. programmer la fonction voisins ci-dessous (on supposera 0 <= i < N et 0 <= j < N)
def voisins(i,j,N):
    """retourne la liste des voisins de la case (i,j) dans une grille de taille N"""
    pass
Solution 
def voisins(i, j, N):
    """retourne la liste des voisins de la case (i,j) dans une grille de taille N"""
    return [((i+x) % N, (j+y)%N) for x in [-1,0,1] for y in [-1,0,1] if x != 0 or y !=0]

Tester votre fonction pour les cases (1,2) et (3,4) dans une grille de taille $N=5$

Calculer le nombre de cases voisines habitées

Les règles d’évolution d’une case dépendent du nombre de cases voisines habitées. Programmer les deux fonctions ci-dessous. La grille g est représentée par un tableau numpy de taille $N \times N$.

def habitee(g, N, i, j):
    """indique si la case (i,j) est habitée dans la grille g de taille N"""
    pass
Solution 
def habitee(g, N, i, j):
    """indique si la case (i,j) est habitée dans la grille g de taille N"""
    return g[i,j] == 1

def nb_voisins_habites(g, N, i, j):
    """retourne le nombre de voisins de la case (i,j) qui sont habités dans la grille g de taille N"""
    pass
Solution 
def nb_voisins_habites(g, N, i, j):
    """retourne le nombre de voisins de la case (i,j) qui sont habités dans la grille g de taille N"""
    n = 0
    for (x, y) in voisins(i, j, N):
        if habitee(g, N, x, y):
            n +=1
    return n

Définir une grille g de taille $N=5$ remplie de 0, sauf dans la 3ème ligne entre les indices 1 à 3 inclus, où elle contient des 1. Vous pouvez afficher votre grille avec la commande plt.imshow(g) suivie de plt.show().

Solution 
N = 5
g = np.zeros((N, N), dtype=int)
g[2,1:4] = 1
plt.imshow(g)
plt.show()

Tester vos fonctions habitee et nb_voisins_habites sur différentes cellules de la grille g.

Calculer le prochain état d’une case (ou cellule)

À chaque tour du jeu, l’état de chacune des cellules de la grille est réévalué en appliquant les règles suivantes:

  • une case reste habitée si elle est entourée par 2 ou 3 voisins habités
  • une case devient habitée si elle est entourée par 3 voisins habités
  • sinon, la case devient vide

Programmer la fonction etat_suivant ci-dessous qui calcule le nouvel état d’une cellule de la grille.

def etat_suivant(g, N, i, j):
    """retourne l'état suivant de la case (i,j) dans la grille g de taille N"""
    pass
Solution 
def etat_suivant(g, N, i, j):
    """retourne l'état suivant de la case (i,j) dans la grille g de taille N"""
    nvh = nb_voisins_habites(g, N, i, j)
    if habitee(g, N, i, j) and nvh in [2,3]:
        return 1
    elif nvh == 3:
        return 1
    else:
        return 0

Tester votre fonction sur différentes cases de la grille g définie précédemment.

Calculer le prochain état de la grille

L’étape suivante consiste à programmer la fonction grille_suivante qui calcule le prochain état d’une grille entière en utilisant la fonction etat_suivant.

def grille_suivante(g, N):
    """retourne une nouvelle grille de taille N qui contient l'état suivant de la grille g de taille N"""
    pass
Solution 
def grille_suivante(g, N):
    """retourne une nouvelle grille de taille N qui contient l'état suivant de la grille g de taille N"""
    ng = np.empty((N, N))
    for i in range(N):
        for j in range(N):
            ng[i,j] = etat_suivant(g, N, i, j)
    return ng

Calculer et afficher la grille suivante de la grille g définie précédemment. Vérifier que le résultat obtenu est correct sur 1 ou 2 autres itérations.

Simulation du jeu de la vie

Copier les fonctions programmées précédemment dans un script python exécutable game_of_life.py, et ajouter la fonction ci-dessous à la suite de vos fonctions. Cette fonction retourne une animation des nframes premiers états du jeu de la vie sur la grille g de taille N.

def jeu_de_la_vie(g, N, nframes=30):
    """retourne une animation des nframes premiers états du jeu de la vie sur la grille g de taille N"""
    fig = plt.figure()
    im = plt.imshow(g, interpolation='none', cmap='binary')
    def animate(_):
        cur = im.get_array()
        future = grille_suivante(cur, N)
        im.set_array(future)
    return FuncAnimation(fig, animate, frames=nframes, repeat=False)

Programmer en fin de fichier un programme principal qui:

  • prend en paramètre obligatoire sur la ligne de commande la taille N de la grille
  • accepte le paramètre optionnel --nframes X qui permet de choisir le nombre d’états successifs à simuler (par défaut: 30)
  • accepte le paramètre optionnel --seed S qui permet de choisir une graine aléatoire (par défaut: None)

Ce programme doit créer une grille aléatoire de taille $N \times N$ contenant des 0 et des 1 à partir de la graine aléatoire S. Puis il crée une animation des nframes premiers états de la grille à l’aide de la fonction jeu_de_la_vie. Enfin, il affiche l’animation en invoquant plt.show().

if __name__ == '__main__':
    pass
Solution 
if __name__ == '__main__':
    parser = argparse.ArgumentParser()
    parser.add_argument('N', nargs=1, help='taille de la grille')
    parser.add_argument('--nframes', nargs=1, help='nombre de frames animées')
    parser.add_argument('--seed', nargs=1, help='graine aléatoire')
    args = parser.parse_args()

    N = int(args.N[0])
    print('nframes', nargs.nframes)
    nframes = int(args.nframes[0]) if args.nframes else 30
    seed = int(args.seed[0]) if args.seed else None

    if args.seed:
        np.random.seed(seed)
    grid = np.random.choice([0,1], (N, N))
    anim = jeu_de_la_vie(grid, N, nframes)
    plt.show()

Tester votre script avec différentes valeurs de paramètres de ligne de commande. Attention, le temps de calcul croît rapidement avec la taille de la grille et le nombre d’états à simuler.