В стиле SQL - 7 (жизнь)

[egorius]

Давеча фейсбук подсунул рекламу, которую я не только не скрыл незамедлительно, но и — первый раз такое! — с интересом посмотрел. Это был университет бесполезных знаний, а в особенности меня, конечно, заинтересовали «бесполезные языки программирования».

Одна из статей там посвящена написанию игры Жизнь на APL в одну строчку. Если — вдруг — вы еще не знаете, что такое Жизнь, сошлюсь на другую статью на том же сайте — она написана интересно, с картинками и интригующими подробностями про Машину Тьюринга.

Окей, вполне допускаю, что APL — это хорошо, но зачем, когда у нас есть SQL?

Только вместо Oracle на этот раз я буду использовать PostgreSQL — времена меняются.

Поле у нас будет таблицей с координатами живых клеток, а не двумерным массивом. Этот прием я уже показывал в прошлых сериях; такое представление более естественно для SQL, оно упрощает код и позволяет не думать о границах поля.

create table cells(
  x integer,
  y integer
);
insert into cells values
  (0,2),(1,2),(2,2),(2,1),(1,0); -- glider

Для подсчета соседей воспользуемся той же самой идеей, что и в статье про APL. Вместо того, чтобы крутить процедурные циклы, сдвинем нашу «матрицу» по всем восьми направлениям и просуммируем количество живых клеток в каждой позиции.

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