"Life" no PostgreSQL

Recentemente no Habré foi publicado um artigo Sea battle in PostgreSQL . Devo admitir: adoro resolver problemas em SQL que não se destinam a SQL. Especialmente uma instrução SQL. E concordo totalmente com os autores:



O uso de ferramentas especiais para outros fins frequentemente causa feedback negativo dos profissionais. No entanto, resolver problemas sem sentido, mas interessantes, treina o pensamento lateral e permite que você explore a ferramenta de diferentes pontos de vista em busca de uma solução adequada.



E mais longe. Sejamos honestos: sempre usar SQL para a finalidade pretendida é um tédio verde. Lembra-se de quais exemplos são dados em todos os livros didáticos, começando com o mesmo artigo de Codd ? Fornecedores e peças, funcionários e departamentos ... E onde está o prazer, onde está a diversão? Para mim, uma das fontes de inspiração é comparar as decisões processuais com as declarativas.



Não me deixe explicar o que é a Vida de John Conway. Direi apenas que - ao que parece  - usando o autômato celular da Vida , você pode construir uma máquina de Turing universal. Parece-me que este é um fato grandioso.



Então, é possível implementar o jogo Life com uma instrução SQL?



Ok, vamos começar.



Nosso campo será uma tabela com as coordenadas das células vivas, e não uma matriz bidimensional, como você pode pensar em uma mente precipitada. Essa visão é mais natural para SQL, simplifica o código e permite que você não pense nos limites dos campos. Além disso, a velocidade dos cálculos (o que, no entanto, dificilmente nos preocupa aqui) dependerá apenas do número de células vivas, e não do tamanho do campo.



Falando em matrizes
, :



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;


. . : . . .



, , , . .



Portanto, o campo:



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


Para contar vizinhos, em vez de torcer loops procedurais, vamos mover nossa "matriz" uma célula em todas as oito direções e somar o número de células vivas em cada posição.



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;


Os turnos também podem ser construídos com uma consulta, mas provavelmente não o tornará mais fácil.



Tendo vizinhos, resta decidir quais células devem morrer e quais devem nascer:



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;


A conexão plena é necessária aqui para que, por um lado, uma nova vida possa surgir em uma cela vazia e, por outro, para destruir as células vivas "nos subúrbios". Temos três condições para entrar na amostra: ou a célula está vazia e tem exatamente três vizinhos (então ela deve ganhar vida e receber o status NOVO), ou está viva e tem dois ou três vizinhos (então ela sobrevive e recebe o status STAY), ou está viva, mas tem menos de dois ou mais de três vizinhos (então ele está condenado à morte e recebe o status de DIE).



Agora precisamos atualizar o campo de jogo usando informações sobre a nova geração de células. É aqui que os recursos do PostgreSQL são úteis: faremos tudo o que for necessário na mesma instrução 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');


Na verdade, toda a lógica do jogo está escrita!



Já é fácil anexar a este algoritmo a exibição do resultado na forma de uma matriz bidimensional familiar ao olho. E, como a cereja do bolo, você pode encerrar a consulta com o comando psql \watchpara que as gerações mudem umas às outras na tela a cada segundo.



Aqui está toda a consulta, com saída minimamente digerível. Copie, cole e divirta-se!



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