«Жизнь» на PostgreSQL

Использование специальных инструментов не по назначению часто вызывает негатив со стороны профессионалов. Однако решение бессмысленных, но интересных задач тренирует нестандартное мышление и позволяет изучить инструмент с разных точек зрения в поиске подходящего решения.

И еще. Будем честны: всегда использовать SQL по назначению — тоска зеленая. Вспомните, какие примеры приводятся во всех учебниках, начиная с той самой статьи Кодда? Поставщики да детали, сотрудники да отделы… А где же удовольствие, где же фан? Для меня один из источников вдохновения — сравнение процедурных решений с декларативными.

Я, позвольте, не буду объяснять, что такое Жизнь Джона Конвея. Скажу только, что — оказывается — используя клеточный автомат Жизни, можно построить универсальную машину Тьюринга. Мне кажется, это грандиозный факт.

Так вот, можно ли реализовать игру Жизнь одним оператором SQL?

Окей, приступим.

Поле у нас будет таблицей с координатами живых клеток, а вовсе не двумерным массивом, как можно сгоряча подумать. Такое представление более естественно для SQL, оно упрощает код и позволяет не думать о границах поля. К тому же скорость расчетов (которая, правда, вряд ли нас тут сильно волнует) будет зависеть только от числа живых клеток, а не от размеров поля.

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

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; 

Сдвиги (shift) тоже можно сконструировать запросом, но, пожалуй, проще от этого не станет.

Имея соседей, остается решить, какие клетки должны погибнуть, а какие — родиться:

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, чтобы поколения сменяли друг друга на экране каждую секунду.

Вот весь запрос целиком с минимально удобоваримым выводом. Copy, paste, and enjoy!

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