"Life" sur PostgreSQL

Récemment sur Habré, un article a été publié Sea battle dans PostgreSQL . Je dois admettre: j'aime résoudre des problèmes en SQL qui ne sont pas destinés à SQL. Surtout avec une instruction SQL. Et je suis tout à fait d'accord avec les auteurs:



L'utilisation d'outils spéciaux à d'autres fins entraîne souvent des commentaires négatifs de la part des professionnels. Cependant, résoudre des tâches insignifiantes mais intéressantes entraîne une réflexion latérale et vous permet d'explorer l'outil de différents points de vue à la recherche d'une solution appropriée.



Et plus loin. Soyons honnêtes: toujours utiliser SQL pour son usage prévu est un ennui vert. Rappelez-vous quels exemples sont donnés dans tous les manuels, en commençant par ce même article de Codd ? Fournisseurs et pièces, employés et départements ... Et où est le plaisir, où est le plaisir? Pour moi, l'une des sources d'inspiration est de comparer les décisions procédurales avec les décisions déclaratives.



Permettez-moi de ne pas expliquer ce qu'est la vie de John Conway. Je dirai seulement que - il s'avère  - en utilisant l'automate cellulaire de la vie , vous pouvez construire une machine de Turing universelle. Il me semble que c'est un fait grandiose.



Alors, est-il possible d'implémenter le jeu Life avec une seule instruction SQL?



D'accord, commençons.



Notre champ sera un tableau avec les coordonnées des cellules vivantes, et pas du tout un tableau à deux dimensions, comme vous pourriez le penser dans un esprit téméraire. Cette vue est plus naturelle pour SQL, elle simplifie le code et permet de ne pas penser aux limites des champs. De plus, la rapidité des calculs (qui, cependant, ne nous inquiète guère ici) ne dépendra que du nombre de cellules vivantes, et non de la taille du champ.



En parlant de matrices
, :



CREATE TABLE matrix (
  rw  integer,
  cl  integer,
  val float
);


, , — . , A(L×M) B(M×N) (L×N), ci,j = ∑k = 1...M  ai,k × bk,j.



i, j, k. SQL- :



SELECT a.rw, b.cl, sum(a.val * b.val)
FROM a
    JOIN b ON a.cl = b.rw
GROUP BY a.rw, b.cl;


. . : . . .



, , , . .



Donc le champ:



CREATE TABLE cells(
    x integer,
    y integer
);
INSERT INTO cells VALUES
    (0,2), (1,2), (2,2), (2,1), (1,0); -- glider


Pour compter les voisins, au lieu de tordre les boucles procédurales, déplaçons notre "matrice" d'une cellule dans les huit directions et additionnons le nombre de cellules vivantes dans chaque position.



WITH shift(x,y) AS (
    VALUES (0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1)
),
neighbors(x,y,cnt) AS (
    SELECT t.x, t.y, count(*)
    FROM (
        SELECT c.x + s.x, c.y + s.y
        FROM cells c
            CROSS JOIN shift s
    ) t(x,y)
    GROUP BY t.x, t.y 
)
SELECT * FROM neighbors;


Les décalages peuvent également être construits avec une requête, mais cela ne facilitera probablement pas les choses.



Ayant des voisins, il reste à décider quelles cellules doivent mourir et lesquelles doivent naître:



WITH shift(x,y) AS (
    ...
),
neighbors(x,y,cnt) AS (
    ...
),
generation(x,y,status) AS (
    SELECT coalesce(n.x,c.x),
           coalesce(n.y,c.y),
           CASE
                WHEN c.x IS NULL THEN 'NEW'
                WHEN n.cnt IN (2,3) THEN 'STAY'
                ELSE 'DIE'
           END
    FROM neighbors n
        FULL JOIN cells c ON c.x = n.x AND c.y = n.y
    WHERE (c.x IS NULL AND n.cnt = 3)
          OR
          (c.x IS NOT NULL)
)
SELECT * FROM generation;


Une connexion complète est ici nécessaire pour que, d'une part, une nouvelle vie puisse surgir dans une cellule vide, et d'autre part, pour détruire les cellules vivantes «en banlieue». Nous avons trois conditions pour entrer dans l'échantillon: soit la cellule est vide et a exactement trois voisins (alors elle doit prendre vie et recevoir le statut NEW), soit elle est vivante et a deux ou trois voisins (alors elle survit et reçoit le statut STAY), soit elle est vivante, mais a moins de deux ou plus de trois voisins (alors il est condamné à mort et reçoit le statut DIE).



Nous devons maintenant mettre à jour le terrain de jeu en utilisant des informations sur la nouvelle génération de cellules. C'est là que les capacités de PostgreSQL sont utiles: nous ferons tout ce dont nous avons besoin dans la même instruction SQL.



WITH shift(x,y) AS (
    ...
),
neighbors(x,y,cnt) AS (
    ...
),
generation(x,y,status) AS (
    ...
),
del AS ( 
    DELETE FROM cells
    WHERE (x,y) IN (
        SELECT x, y FROM generation WHERE status = 'DIE'
  )
),
ins AS (
    INSERT INTO cells
        SELECT x, y FROM generation WHERE status = 'NEW'
)
SELECT *
FROM generation
WHERE status IN ('STAY','NEW');


En fait, toute la logique du jeu est écrite!



Il est déjà aisé de rattacher à cet algorithme l'affichage du résultat sous la forme d'une matrice bidimensionnelle familière à l'œil. Et, comme la cerise sur le gâteau, vous pouvez terminer la requête avec la commande psql \watchafin que les générations se changent à l'écran toutes les secondes.



Voici la requête entière, avec un résultat minimalement digestible. Copiez, collez et profitez-en!



WITH shift(x,y) AS (
    VALUES (0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1)
),
neighbors(x,y,cnt) AS (
    SELECT t.x, t.y, count(*)
    FROM (
        SELECT c.x + s.x, c.y + s.y
        FROM cells c
            CROSS JOIN shift s
    ) t(x,y)
    GROUP BY t.x, t.y 
),
generation(x,y,status) AS (
    SELECT coalesce(n.x,c.x),
           coalesce(n.y,c.y),
           CASE
                WHEN c.x IS NULL THEN 'NEW'
                WHEN n.cnt IN (2,3) THEN 'STAY'
                ELSE 'DIE'
           END
    FROM neighbors n
        FULL JOIN cells c ON c.x = n.x AND c.y = n.y
    WHERE (c.x IS NULL AND n.cnt = 3)
          OR
          (c.x IS NOT NULL)
),
del AS ( 
    DELETE FROM cells
    WHERE (x,y) IN (
        SELECT x, y FROM generation WHERE status = 'DIE'
  )
),
ins AS (
    INSERT INTO cells
        SELECT x, y FROM generation WHERE status = 'NEW'
),
dimensions(x1,x2,y1,y2) AS (
    SELECT min(x), max(x), min(y), max(y)
    FROM generation
    WHERE status IN ('STAY','NEW')
)
SELECT string_agg(CASE WHEN g.x IS NULL THEN ' ' ELSE '*' END, '' ORDER BY cols.x)
FROM dimensions d
    CROSS JOIN generate_series(d.x1,d.x2) cols(x)
    CROSS JOIN generate_series(d.y1,d.y2) lines(y)
    LEFT JOIN generation g ON g.x = cols.x AND g.y = lines.y AND g.status IN ('STAY','NEW')
GROUP BY lines.y
ORDER BY lines.y
\watch 1



All Articles