El uso de herramientas especiales para otros fines a menudo provoca comentarios negativos de los profesionales. Sin embargo, la resolución de tareas sin sentido pero interesantes entrena el pensamiento lateral y permite explorar la herramienta desde diferentes puntos de vista en busca de una solución adecuada.
Y además. Seamos honestos: siempre usar SQL para su propósito previsto es un aburrimiento verde. ¿Recuerda qué ejemplos se dan en todos los libros de texto, comenzando con el mismo artículo de Codd ? Proveedores y repuestos, empleados y departamentos ... ¿Dónde está el placer, dónde está la diversión? Para mí, una de las fuentes de inspiración es comparar las soluciones procedimentales con las declarativas.
No me dejo explicar qué es la vida de John Conway. Solo puedo decir que, resulta que utilizando el autómata celular de Life , puedes construir una máquina de Turing universal. Me parece que este es un hecho grandioso.
Entonces, ¿es posible implementar el juego Life con una declaración SQL?
Bien, comencemos.
Nuestro campo será una tabla con las coordenadas de células vivas, y no una matriz bidimensional, como podría pensar en una mente precipitada. Esta vista es más natural para SQL, simplifica el código y le permite no pensar en los límites de los campos. Además, la velocidad de los cálculos (que, sin embargo, aquí apenas nos preocupa) dependerá únicamente del número de células vivas, y no del tamaño del campo.
Hablando de matrices
, :
, , — . , A(L×M) B(M×N) (L×N), ci,j = ∑k = 1...M ai,k × bk,j.
i, j, k. SQL- :
. . : . . .
, , , . .
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;
. . : . . .
, , , . .
Entonces el 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 los vecinos, en lugar de girar los bucles de procedimiento, movamos nuestra "matriz" una celda en las ocho direcciones y sumemos el número de células vivas en cada posición.
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;
Los turnos también se pueden construir con una consulta, pero probablemente no lo hará más fácil.
Teniendo vecinos, queda decidir qué células deben morir y cuáles deben nacer:
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;
La conexión total es necesaria aquí para que, por un lado, pueda surgir una nueva vida en una celda vacía y, por otro, para destruir las células vivas "en los suburbios". Tenemos tres condiciones para ingresar a la muestra: o la celda está vacía y tiene exactamente tres vecinos (luego debe cobrar vida y recibir el estado NUEVO), o está viva y tiene dos o tres vecinos (luego sobrevive y recibe el estado STAY), o está viva, pero tiene menos de dos o más de tres vecinos (entonces está condenado a muerte y recibe el estatus de DIE).
Ahora necesitamos actualizar el campo de juego utilizando información sobre la nueva generación de células. Aquí es donde las capacidades de PostgreSQL son útiles: haremos todo lo necesario en la misma declaración 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 realidad, ¡toda la lógica del juego está escrita!
Ya es fácil adjuntar a este algoritmo la visualización del resultado en forma de una matriz bidimensional familiar para el ojo. Y, como la guinda del pastel, puede finalizar la consulta con el comando psql
\watchpara que las generaciones se cambien entre sí en la pantalla cada segundo.
Aquí está la consulta completa, con un resultado mínimamente digerible. ¡Copia, pega y disfruta!
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