Qualifier des structures du Jeu de la vie⚓︎

Règles⚓︎

Une cellule possède huit voisins, qui sont les cellules adjacentes horizontalement, verticalement et diagonalement.

À chaque itération, l'état d'une cellule est entièrement déterminé par l'état de ses huit cellules voisines, selon les règles suivantes :

Une cellule morte possédant exactement trois cellules voisines vivantes devient vivante (elle nait).
Une cellule vivante possédant deux ou trois cellules voisines vivantes le reste, sinon elle meurt.

Modélisation⚓︎

On utilise pour représenter une grille rectangulaire, une liste de listes d'entiers égaux à 0 ou 1.

0 désigne une cellule morte.
1 désigne une cellule vivante.

🐍 Script Python

MOTIF_A0 = [
    [0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
]

MOTIF_A1 = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
]

🐍 Script Python

MOTIF_B0 = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0],
]

MOTIF_B1 = [
    [0, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
]
MOTIF_B2 = [
    [0, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
]

Structures⚓︎

Un motif peut être qualifié de stable, de périodique, de vaisseau ou autre.

Motif stable

Un motif stable est identique à lui-même à la génération suivante.

Exemple :

🐍 Script Python

CARRE_STABLE = [
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
]

TODO ajouter des figures de plusieurs motifs stables

Motif périodique

Un motif périodique est identique à lui-même après plusieurs générations.

Exemple :

🐍 Script Python

CLIGNOTANT_0 = [
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
]

CLIGNOTANT_1 = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
]

TODO ajouter des figures de plusieurs motifs périodiques, avec des gif

Vaisseau

Un vaisseau est identique à lui-même, mais décalé, après plusieurs générations.

🐍 Script Python

PLANEUR_0 = [
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
]

PLANEUR_1 = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
]

PLANEUR_2 = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0],
]

PLANEUR_3 = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 1, 0, 1, 1],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0],
]

Autre vaisseau

Le problème⚓︎

Écrire quatre fonctions :

successeur(motif) doit renvoyer la transformation du motif à l'étape suivante.
est_stable(motif) doit renvoyer un booléen, la réponse à la question :
- Le motif est-il identique à lui-même après une génération ?
est_periodique(motif) doit renvoyer un booléen, la réponse à la question :
- Le motif est-il identique à lui-même après plusieurs générations ?
- On garantit que dans les tests, moins de 20 générations suffisent à discriminer les structures périodiques.
est_vaisseau(motif) doit renvoyer un booléen, la réponse à la question :
- Le motif est-il identique à lui-même, mais déplacé, après plusieurs générations ?
- On garantit que dans les tests, moins de 20 générations suffisent à discriminer les vaisseaux.

Dans tous les cas, le motif donné en paramètre aura au moins deux lignes et deux colonnes et sera entouré de cellules mortes. La sortie pourrait ne pas l'être, d'où l'utilisation de la fonction encadre qu'il faudra utiliser.

def encadre(motif):bksl-nl "Renvoie le même motif, mais entouré de cellules mortes"bksl-nl h, l = len(motif), len(motif[0])bksl-nl resultat = []bksl-nl resultat.append([0] py-str (l+2))bksl-nl for ligne in motif:bksl-nl resultat.append([0] + ligne + [0])bksl-nl resultat.append([0] py-str (l+2))bksl-nl return resultatbksl-nlbksl-nldef decale(motif, di, dj):bksl-nl "Renvoie une copie décalée du motif, quitte à perdre de l'information"bksl-nl h, l = len(motif), len(motif[0])bksl-nl resultat = [[0]py-strl for i in range(h)]bksl-nl for i in range(h - di):bksl-nl for j in range(l - dj):bksl-nl resultat[i + di][j + dj] = motif[i][j]bksl-nl return resultatbksl-nlbksl-nldef correspond(motifpy-und0, motifpy-und1):bksl-nl if len(motifpy-und0) != len(motifpy-und1):bksl-nl return Falsebksl-nl else:bksl-nl h = len(motifpy-und0)bksl-nl if len(motifpy-und0[0]) != len(motifpy-und1[0]):bksl-nl return Falsebksl-nl else:bksl-nl l = len(motifpy-und0[0])bksl-nl for i in range(h):bksl-nl for j in range(l):bksl-nl if motifpy-und0[i][j] != motifpy-und1[i][j]:bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nldef successeur(motif):bksl-nl ...bksl-nlbksl-nldef estpy-undstable(motif):bksl-nl ...bksl-nlbksl-nldef estpy-undperiodique(motif):bksl-nl ...bksl-nlbksl-nldef estpy-undvaisseau(motif):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlMOTIFpy-undA0 = [bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 1, 0, 0, 0],bksl-nl [0, 1, 0, 1, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlMOTIFpy-undA1 = [bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlassert correspond(successeur(MOTIFpy-undA0), MOTIFpy-undA1)bksl-nlbksl-nlbksl-nlMOTIFpy-undB0 = [bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 1, 1, 1, 0],bksl-nl [0, 1, 1, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlMOTIFpy-undB1 = [bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 1, 0, 1, 0],bksl-nl [0, 1, 0, 1, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlMOTIFpy-undB2 = [bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 1, 0, 1, 0],bksl-nl [0, 1, 0, 1, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlassert correspond(successeur(MOTIFpy-undB0), MOTIFpy-undB1)bksl-nlassert correspond(successeur(MOTIFpy-undB1), MOTIFpy-undB2)bksl-nlbksl-nlbksl-nlbksl-nlCARREpy-undSTABLE = [bksl-nl [0, 0, 0, 0],bksl-nl [0, 1, 1, 0],bksl-nl [0, 1, 1, 0],bksl-nl [0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlassert correspond(encadre(CARREpy-undSTABLE), successeur(CARREpy-undSTABLE))bksl-nlbksl-nlbksl-nlCLIGNOTANTpy-und0 = [bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlCLIGNOTANTpy-und1 = [bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 1, 1, 1, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlassert correspond(encadre(CLIGNOTANTpy-und0), successeur(CLIGNOTANTpy-und1))bksl-nlassert correspond(encadre(CLIGNOTANTpy-und1), successeur(CLIGNOTANTpy-und0))bksl-nlbksl-nlbksl-nldef encadre(motif):bksl-nl "Renvoie le même motif, mais entouré de cellules mortes"bksl-nl h, l = len(motif), len(motif[0])bksl-nl resultat = []bksl-nl resultat.append([0] py-str (l + 2))bksl-nl for ligne in motif:bksl-nl resultat.append([0] + ligne + [0])bksl-nl resultat.append([0] py-str (l + 2))bksl-nl return resultatbksl-nlbksl-nldef decale(motif, di, dj):bksl-nl "Renvoie une copie décalée du motif, quitte à perdre de l'information"bksl-nl h, l = len(motif), len(motif[0])bksl-nl resultat = [[0] py-str l for i in range(h)]bksl-nl for i in range(h - di):bksl-nl for j in range(l - dj):bksl-nl resultat[i + di][j + dj] = motif[i][j]bksl-nl return resultatbksl-nlbksl-nldef correspond(motifpy-und0, motifpy-und1):bksl-nl if len(motifpy-und0) != len(motifpy-und1):bksl-nl return Falsebksl-nl else:bksl-nl h = len(motifpy-und0)bksl-nl if len(motifpy-und0[0]) != len(motifpy-und1[0]):bksl-nl return Falsebksl-nl else:bksl-nl l = len(motifpy-und0[0])bksl-nl for i in range(h):bksl-nl for j in range(l):bksl-nl if motifpy-und0[i][j] != motifpy-und1[i][j]:bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nldef successeur(motif):bksl-nl "motif est garanti encadré de 0"bksl-nl h, l = len(motif), len(motif[0])bksl-nl resultat = [[0] py-str l for i in range(h)]bksl-nl for i in range(1, h - 1):bksl-nl for j in range(1, l - 1):bksl-nl somme = (bksl-nl + motif[i + 1][j]bksl-nl + motif[i - 1][j]bksl-nl + motif[i][j + 1]bksl-nl + motif[i][j - 1]bksl-nl + motif[i + 1][j + 1]bksl-nl + motif[i - 1][j + 1]bksl-nl + motif[i - 1][j - 1]bksl-nl + motif[i + 1][j - 1]bksl-nl )bksl-nlbksl-nl if motif[i][j] == 0:bksl-nl if somme == 3:bksl-nl # naissancebksl-nl resultat[i][j] == 1bksl-nl else:bksl-nl if 2 <= somme <= 3:bksl-nl # reste en viebksl-nl resultat[i][j] = 1bksl-nlbksl-nl # cas i := 0, puis i := h - 1bksl-nl for j in range(1, l - 1):bksl-nl if (motif[1][j - 1] + motif[1][j] + motif[1][j + 1] == 3):bksl-nl # naissancebksl-nl resultat[0][j] = 1bksl-nl if (motif[h - 2][j - 1] + motif[h - 2][j] + motif[h - 2][j + 1] == 3):bksl-nl # naissancebksl-nl resultat[h - 1][j] = 1bksl-nl bksl-nl # cas j := 0, puis j := l - 1bksl-nl for i in range(1, h - 1):bksl-nl if (motif[i - 1][1] + motif[i][1] + motif[i + 1][1] == 3):bksl-nl # naissancebksl-nl resultat[i][0] = 1bksl-nl if (motif[i - 1][l - 2] + motif[i][l - 2] + motif[i + 1][l - 2] == 3):bksl-nl # naissancebksl-nl resultat[i][l - 1] = 1bksl-nl bksl-nl return resultatbksl-nlbksl-nlbksl-nldef estpy-undstable(motif):bksl-nl return correspond(motif, successeur(motif))bksl-nlbksl-nldef estpy-undperiodique(motif):bksl-nl ...bksl-nlbksl-nldef estpy-undvaisseau(motif):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlMOTIFpy-undA0 = [bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 1, 0, 0, 0],bksl-nl [0, 1, 0, 1, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlMOTIFpy-undA1 = [bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlassert correspond(successeur(MOTIFpy-undA0), MOTIFpy-undA1)bksl-nlbksl-nlbksl-nlMOTIFpy-undB0 = [bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 1, 1, 1, 0],bksl-nl [0, 1, 1, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlMOTIFpy-undB1 = [bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 1, 0, 1, 0],bksl-nl [0, 1, 0, 1, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlMOTIFpy-undB2 = [bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 1, 0, 1, 0],bksl-nl [0, 1, 0, 1, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlassert correspond(successeur(MOTIFpy-undB0), MOTIFpy-undB1)bksl-nlassert correspond(successeur(MOTIFpy-undB1), MOTIFpy-undB2)bksl-nlbksl-nlbksl-nlbksl-nlCARREpy-undSTABLE = [bksl-nl [0, 0, 0, 0],bksl-nl [0, 1, 1, 0],bksl-nl [0, 1, 1, 0],bksl-nl [0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlassert correspond(encadre(CARREpy-undSTABLE), successeur(CARREpy-undSTABLE))bksl-nlbksl-nlbksl-nlCLIGNOTANTpy-und0 = [bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 0, 1, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlCLIGNOTANTpy-und1 = [bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 1, 1, 1, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl [0, 0, 0, 0, 0],bksl-nl]bksl-nlbksl-nlassert correspond(encadre(CLIGNOTANTpy-und0), successeur(CLIGNOTANTpy-und1))bksl-nlassert correspond(encadre(CLIGNOTANTpy-und1), successeur(CLIGNOTANTpy-und0))bksl-nlbksl-nlbksl-nl