Die Verwendung von Spezialwerkzeugen für andere Zwecke führt häufig zu negativen Rückmeldungen von Fachleuten. Das Lösen bedeutungsloser, aber interessanter Aufgaben trainiert jedoch das Querdenken und ermöglicht es Ihnen, das Werkzeug aus verschiedenen Blickwinkeln auf der Suche nach einer geeigneten Lösung zu erkunden.
Und weiter. Seien wir ehrlich: SQL immer für den beabsichtigten Zweck zu verwenden, ist eine grüne Langeweile. Erinnern Sie sich, welche Beispiele in allen Lehrbüchern enthalten sind, beginnend mit demselben Artikel von Codd ? Lieferanten und Teile, Mitarbeiter und Abteilungen ... Und wo ist das Vergnügen, wo ist der Spaß? Eine der Inspirationsquellen ist für mich der Vergleich von prozeduralen und deklarativen Lösungen.
Lassen Sie mich nicht erklären, was das Leben von John Conway ist. Ich kann nur sagen, dass man - wie sich herausstellt - mit dem zellularen Automaten des Lebens eine universelle Turing-Maschine bauen kann. Es scheint mir, dass dies eine grandiose Tatsache ist.
Ist es also möglich, das Spiel Life mit einer SQL-Anweisung zu implementieren ?
Okay, lass uns anfangen.
Unser Feld wird eine Tabelle mit den Koordinaten lebender Zellen sein und überhaupt keine zweidimensionale Anordnung, wie Sie vielleicht vorschnell denken. Diese Ansicht ist für SQL natürlicher, vereinfacht den Code und ermöglicht es Ihnen, nicht an Feldgrenzen zu denken. Darüber hinaus hängt die Geschwindigkeit der Berechnungen (die uns hier jedoch kaum beunruhigt) nur von der Anzahl der lebenden Zellen und nicht von der Größe des Feldes ab.
Apropos Matrizen
, :
, , — . , 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;
. . : . . .
, , , . .
Also das Feld:
CREATE TABLE cells(
x integer,
y integer
);
INSERT INTO cells VALUES
(0,2), (1,2), (2,2), (2,1), (1,0); -- glider
Um die Nachbarn zu zählen, anstatt die prozeduralen Schleifen zu verdrehen, verschieben wir unsere "Matrix" um eine Zelle in alle acht Richtungen und summieren die Anzahl der lebenden Zellen in jeder 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;
Schichten können auch mit einer Abfrage erstellt werden, aber es wird wahrscheinlich nicht einfacher.
Bei den Nachbarn bleibt zu entscheiden, welche Zellen sterben und welche geboren werden sollen:
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;
Hier ist eine vollständige Verbindung notwendig, damit einerseits ein neues Leben in einer leeren Zelle entstehen kann und andererseits lebende Zellen "in den Vororten" zerstört werden können. Wir haben drei Bedingungen, um in die Probe zu gelangen: Entweder ist die Zelle leer und hat genau drei Nachbarn (dann muss sie zum Leben erweckt werden und den Status NEU erhalten), oder sie lebt und hat zwei oder drei Nachbarn (dann überlebt sie und erhält den Status STAY), oder sie lebt, aber hat weniger als zwei oder mehr als drei Nachbarn (dann ist es zum Tode verurteilt und erhält den DIE-Status).
Jetzt müssen wir das Spielfeld mit Informationen über die neue Generation von Zellen aktualisieren. Hier bieten sich die Funktionen von PostgreSQL an: Wir tun alles, was wir brauchen, in derselben SQL-Anweisung.
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');
Eigentlich ist die ganze Logik des Spiels geschrieben!
Es ist bereits einfach, die Anzeige des Ergebnisses in Form einer dem Auge vertrauten zweidimensionalen Matrix an diesen Algorithmus anzuhängen. Und wie das i-Tüpfelchen können Sie die Abfrage mit dem Befehl psql beenden,
\watchsodass sich die Generationen auf dem Bildschirm jede Sekunde gegenseitig ändern.
Hier ist die gesamte Abfrage mit minimal verdaulicher Ausgabe. Kopieren, einfügen und genieß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