Использование специальных инструментов не по назначению часто вызывает негатив со стороны профессионалов. Однако решение бессмысленных, но интересных задач тренирует нестандартное мышление и позволяет изучить инструмент с разных точек зрения в поиске подходящего решения.
И еще. Будем честны: всегда использовать SQL по назначению тоска зеленая. Вспомните, какие примеры приводятся во всех учебниках, начиная с той самой статьи Кодда? Поставщики да детали, сотрудники да отделы Агде же удовольствие, где же фан? Для меня один из источников вдохновения сравнение процедурных решений с декларативными.
Я, позвольте, не буду объяснять, что такое Жизнь Джона Конвея. Скажу только, что оказывается используя клеточный автомат Жизни, можно построить универсальную машину Тьюринга. Мне кажется, это грандиозный факт.
Так вот, можно ли реализовать игру Жизнь одним оператором SQL?
Окей, приступим.
Поле у нас будет таблицей с координатами живых клеток, а вовсе не двумерным массивом, как можно сгоряча подумать. Такое представление более естественно для SQL, оно упрощает код и позволяет не думать о границах поля. К тому же скорость расчетов (которая, правда, вряд ли нас тут сильно волнует) будет зависеть только от числа живых клеток, а не от размеров поля.
Кстати о матрицах
Такое же представление удобно
использовать для представления матриц, особенно разреженных:
Простой пример, эффективно взрывающий процедурно настроенный мозг, умножение матриц. Напомню, что произведением матрицы A(LM) на матрицу B(MN) является матрица С(LN), элементы которой ci,j = k = 1...M ai,kbk,j.
Процедурный алгоритм использует тройной вложенный цикл по i, j, k. А SQL-запросу достаточно простого соединения:
Запрос стоит внимательно изучить и понять. С непривычки это совсем даже непросто. Здесь нет циклов: запрос оперирует множествами элементов и их соединением. Здесь нет размерности матрицы. Здесь не нужно хранить в таблице нулевые элементы.
Но после того, как мозг взорвался, код ставится очевидным и ничуть не более сложным, чем процедурный. Это важный момент.
CREATE TABLE matrix ( rw integer, cl integer, val float);
Простой пример, эффективно взрывающий процедурно настроенный мозг, умножение матриц. Напомню, что произведением матрицы A(LM) на матрицу B(MN) является матрица С(LN), элементы которой ci,j = k = 1...M ai,kbk,j.
Процедурный алгоритм использует тройной вложенный цикл по i, j, k. А SQL-запросу достаточно простого соединения:
SELECT a.rw, b.cl, sum(a.val * b.val)FROM a JOIN b ON a.cl = b.rwGROUP 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 generationWHERE 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.yORDER BY lines.y\watch 1
