👌🏻 👎🏻 🐉 PostgreSQL上的“生活” ♒️ 🙏🏿 🏛️

最近在哈布雷（Habré）上发表了PostgreSQL中的《海战》（Sea Battle）。我必须承认：我喜欢解决SQL不适用于SQL的问题。特别是一条SQL语句。我完全同意作者的观点：

将专用工具用于其他目的通常会引起专业人员的负面反馈。但是，解决无意义但有趣的任务会训练横向思维，并使您可以从不同的角度探索该工具以寻找合适的解决方案。

并进一步。坦白地说：始终将SQL用于其预期目的是无聊的。还记得从科德的同一篇文章开始的所有教科书中都提供了哪些示例吗？供应商和零件，员工和部门...乐趣在哪里，乐趣在哪里？对我而言，灵感的来源之一是将程序决策与陈述性决策进行比较。

让我不要解释约翰·康威的生平。我只能说-事实证明 -使用生命自动细胞，您可以构建通用的图灵机。在我看来，这是一个宏大的事实。

那么，是否可以用一个SQL语句实现游戏Life？

好的，让我们开始吧。

我们的字段将是一个包含活细胞坐标的表，而不是一个二维数组，就像您在脑子里想的那样。这种视图对于SQL更自然，它简化了代码，并且使您不必考虑字段边界。另外，计算的速度（但是，在这里几乎不会让我们担心）将仅取决于活细胞的数量，而不取决于场的大小。

谈到矩阵

, :

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

, , — . , A(L×M) B(M×N) (L×N), c_i,j = ∑_{k = 1...M} a_i,k × b_k,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;

. . : . . .

, , , . .

所以这个领域：

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

为了计算邻居，而不是扭曲过程循环，让我们在所有八个方向上移动“矩阵”一个单元并求和每个位置的活动单元数。

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;

移位也可以通过查询来构造，但可能不会使其变得更容易。

有了邻居，剩下的事情就是决定哪些细胞应该死亡以及哪些细胞应该出生：

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;

这里必须有完整的连接，以便一方面可以在一个空的牢房中产生新的生命，另一方面可以摧毁“郊区”的活细胞。我们有三个条件可以进入样本：该单元为空并且恰好具有三个邻居（那么它必须活着并获得NEW状态），或者它还活着并且有两个或三个邻居（那么它存活并获得STAY状态），或者它还活着，但是拥有少于两个或三个以上的邻居（然后注定要死亡并获得DIE身份）。

现在，我们需要使用有关新一代电池的信息来更新运动场。这就是PostgreSQL功能派上用场的地方：我们将在同一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');

实际上，所有游戏逻辑都已编写！

将结果显示以眼睛熟悉的二维矩阵的形式附加到该算法已经很容易了。而且，就像锦上添花一样，您可以使用psql命令结束查询，\watch以便世代在屏幕上每秒发生变化。

这是整个查询，具有最少的可摘要输出。复制，粘贴和享受！

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

PostgreSQL上的“生活”

More articles: