«Жизнь» на большом поле
Игра «Жизнь» Джона Конуэя идёт на поле из H строк по W клеток. Каждая клетка жива или мертва. За одно поколение все клетки меняются одновременно: живая клетка, у которой два или три живых соседа, остаётся жить, мёртвая, у которой ровно три живых соседа, оживает, а все остальные клетки в новом поколении мертвы. Соседи клетки — восемь клеток вокруг неё. За краем поля клеток нет: можно считать, что там всегда мертво.
Сколько клеток будет живо через k поколений? В одном из тестов стартовое поле — фотография «Вода и горы» после дизеринга Флойда — Стейнберга из статьи о векторизации: чёрные пиксели — живые клетки.
Вход
В первой строке H, W и k (1 ≤ H, W ≤ 600, 0 ≤ k ≤ 100). Дальше H строк по W символов: # — живая клетка, . — мёртвая.
Выход
Одно число — сколько клеток живо после k поколений.
Примеры
Пример 1
6 6 4 .#.... ..#... ###... ...... ...... ......
5
Пример 2
5 5 12 ..... ..#.. ...#. .###. .....
4
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Посчитайте объём работы: 600 × 600 клеток, сто поколений, у каждой клетки восемь соседей. Сколько это шагов интерпретатора Python, если каждую клетку обходить циклом?
2Подсказка 2
Поколения идут строго одно за другим: следующее не посчитать, пока нет предыдущего. Но внутри одного поколения клетки друг от друга не зависят — все новые значения считаются по старому полю. Как посчитать сразу всех соседей всех клеток?
3Идея
Векторизация по полю, цикл по поколениям. Число живых соседей всех клеток сразу — это сумма восьми сдвинутых копий поля, ровно как размытие 3 × 3 в статье. Окружим поле рамкой из мёртвых клеток, и каждая сдвинутая копия станет срезом этого массива. Новое поле — одно логическое выражение над целыми массивами: «соседей три» или «соседей два и клетка жива».
4Разбор
На Python с numpy: массив padded размером (H + 2) × (W + 2) из нулей, в каждом поколении в его середину кладётся текущее поле, а число соседей — сумма восьми срезов вида padded[:-2, 1:-1]. Все восемь срезов — представления одного массива, без копирования; складываются они в uint8, где восьми хватает с запасом. Новое поле — (n == 3) | ((n == 2) & (alive == 1)). Внутри numpy это несколько проходов по 360 тысячам байт, и поколение занимает доли миллисекунды.
На Go векторизовать незачем: обычный двойной цикл по клеткам — машинный код, и сто поколений поля 600 × 600 он проходит за десятые доли секунды. Нужны только два буфера — старое поле и новое — и рамка из мёртвых клеток, чтобы не проверять границы.
4+Решение
5Сложность
O(k·H·W) при любом способе: 3,6·107 обновлений клеток. Разница — в цене одного обновления: в цикле Python это десятки шагов интерпретатора, в numpy и в Go — несколько машинных команд.
6Типичные ошибки
- Цикл Python по клеткам. Верен, но не укладывается во время — это
wrong.py. - Поле в одном массиве. Если записывать новые значения прямо в то же поле, соседи справа и снизу будут считаться уже по новому поколению. Нужно второе поле — или, как в numpy, новое поле целиком из старого.
np.roll. Самый известный способ посчитать соседей в numpy — сдвигиnp.roll. Ноrollпереносит то, что ушло за край, на другую сторону: поле становится бубликом, и клетки у левого края видят соседей у правого. В этой задаче за краем мертво, и ответ разойдётся уже на втором примере: на бублике глайдер проходит сквозь угол и летит дальше — пять клеток вместо блока из четырёх.- Сумма булевых массивов. Если поле хранить как
boolи складывать сдвиги, numpy сложит их как «или»:True + Trueв булевом массиве —True. Соседей тогда никогда не больше одного, не оживает ни одна клетка, и ответ всюду ноль. Перед сложением нужен целый тип.