Le jeu de la vie de Conway en programmation par ensemble de réponse
*
Le jeu de la vie de Conway est un automate cellulaire bien connu. Les règles du jeu de la vie sont les suivantes: on dispose d’une grille à deux dimensions dont les cases, appelées cellules, sont soit mortes soit vivantes. À chaque itération, la grille est mise à jour de la façon suivante, en regardant l’état des 8 cellules du voisinage de chaque cellule de la grille:
- Une cellule morte possédant exactement trois cellules voisines vivantes devient vivante
- Une cellule vivante ne possédant pas exactement deux ou trois cellules vivantes meurt
L’objectif de ce petit billet de blog, est d’encoder ces règles en programmation par ensemble de réponses.
Les atomes cell/2 listent les cellules de la grille du jeu de la vie.
L’atome alive(I, X, Y) est dans l’ensemble de réponse quand la cellule \(X, Y\) est vivante à l’itération \(I\).
Les données d’entrées sont un ensemble d’atomes alive(0, . , .) pour les cellules vivantes à l’état initiale (\(I = 0\)). Les autres cellules sont considérées comme mortes.
Ici, pour l’exemple j’ai encodé le très classique oscillateur à trois cellules vivantes alignées.
#const size=10. % size of the grid
#const steps=1.
% Define the grid cells
cell(X, Y) :- X = 1..size , Y = 1..size.
1 { alive(I, X, Y) ; dead(I, X, Y) } 1 :- cell(X, Y) , I = 1..steps.
% Moore neighborhood
moore((-1,-1); (-1,0); (-1,1); (0,-1); (0,1); (1,-1); (1,0); (1,1)).
neighbor(X, Y, X + DX, Y + DY) :-
cell(X, Y),
moore((DX, DY)).
% Count living neighbor
neighbors_alive(I, X, Y, N) :-
cell(X, Y),
I = 0..steps,
N = #count { NX, NY : neighbor(X, Y, NX, NY) , alive(I, NX, NY) }.
% Apply Conway game of life rules
% Any live cell with fewer than two live neighbors dies (underpopulation)
dead(I + 1, X, Y) :-
alive(I, X, Y),
neighbors_alive(I, X, Y, N),
N < 2.
% Any live cell with two or three live neighbors lives on
alive(I + 1, X, Y) :-
alive(I, X,Y),
neighbors_alive(I, X, Y, N),
N >= 2,
N <= 3.
% Any live cell with more than three live neighbors dies (overpopulation)
dead(I + 1, X, Y) :-
alive(I, X, Y),
neighbors_alive(I, X, Y, N),
N > 3.
% Any dead cell with exactly three live neighbors becomes alive (reproduction)
alive(I + 1, X, Y) :-
dead(I, X, Y),
neighbors_alive(I, X, Y, N),
N = 3.
% Any dead cell with another number of living neighbors remains dead.
dead(I + 1, X, Y) :-
dead(I, X, Y),
neighbors_alive(I, X, Y, N),
N <> 3.
:- alive(I, X, Y), dead(I, X, Y).
% Input data
alive(0, 5, 5).
alive(0, 4, 5).
alive(0, 6, 5).
dead(0, X, Y) :- cell(X, Y) , not alive(0, X, Y).
#show alive/3.
clingo version 5.8.0
Reading from /tmp/babel-5r8Txs/clingo-3DDXxF
Solving...
Answer: 1 (Time: 0.013s)
alive(0,5,5) alive(0,4,5) alive(0,6,5) alive(1,5,4) alive(1,5,5) alive(1,5,6) alive(2,4,5) alive(2,5,5) alive(2,6,5)
SATISFIABLE
Models : 1
Calls : 1
Time : 0.013s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.013s
| x | |||||||||
| x | |||||||||
| x | |||||||||
| x | x | x | |||||||
| x | |||||||||
| x | |||||||||
| x | |||||||||