Этюды для программистов

2. Жизнь диктует свои законы, или Клеточные автоматы и машинная графика

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

Чтобы проследить за историей развития колонии, разместим в пустыне клетки Жизни в их начальном положении. Смена поколений будет происходить по следующим правилам.

1. Соседями клетки считаются все клетки, находящиеся в восьми ячейках, расположенных рядом с данной по горизонтали, вертикали или диагонали.

2. Если у некоторой клетки меньше двух соседей, она погибает от одиночества. Если клетка имеет больше трех соседей, она погибает от тесноты.

3. Если рядом с пустой ячейкой окажется ровно три соседние клетки Жизни, то в этой ячейке рождается новая клетка.

4. Гибель и рождение происходят в момент смены поколений. Таким образом, гибнущая клетка может способствовать рождению новой, но рождающаяся клетка не может воскресить гибнущую, и гибель одной клетки, уменьшив локальную плотность населения, не может предотвратить гибель другой.

На рис. 2.1 показана история еще одной колонии клеток Жизни.

Тема. Напишите программу, моделирующую колонию Жизни. Исходными данными служит начальное расположение клеток, а в качестве результата нужно получить вид сверху всех поколений колонии. Для вывода истории можно воспользоваться обычным устройством построчной печати (АЦПУ), но такой способ дает весьма неприглядные изображения. Если в вашем распоряжении имеется графопостроитель или графический терминал, воспользуйтесь их возможностями для получения более изящной картинки.

Рекомендации исполнителю. Хотя этого и не видно из примеров, некоторые колонии разрастаются невероятным образом при весьма скромных начальных размерах. Есть другие колонии, которые медленно перемещаются по пустыне, переходя на все новые и новые территории. Ваша программа должна обрабатывать большие колонии без чрезмерной траты памяти или времени. Многократный просмотр большого массива для построения следующих поколений — это банальный подход; здесь программистская задача состоит в выборе более экономичных структур данных и алгоритмов. Вам, возможно, захочется испытать какой-либо метод, отслеживающий только занятые квадраты. Растущая или движущаяся колония может выйти из поля зрения, если его положение и границы зафиксированы, поэтому, вероятно, понадобится еще и метод вывода, перемещающий нашу точку зрения вслед за изменениями колонии[6].

Инструментовка. Для этой задачи подойдет язык APL благодаря наличию в нем операций над векторами и матрицами, однако можно использовать почти любой язык высокого уровня, если в нем предусмотрена работа с массивами. На примере этой задачи хорошо изучать, как сказывается использование языка ассемблера: насколько замедляется программирование и каков выигрыш в эффективности внутреннего цикла. Наконец, для тех, кто имеет доступ к оборудованию ЭВМ, интересным экспериментом могла бы быть микропрограммная реализация; машина при этом превращается в колонию Жизни.

Длительность исполнения. Одному исполнителю на 3 недели.

Развитие темы. Колония может все время расти, непрерывно меняя свое расположение, форму или число клеток. Однако чаще колония становится в конце концов стационарной, начиная циклически повторять один и тот же конечный набор состояний. Длина цикла называется периодом колонии. (По этому определению период мертвой и пустой колонии равен единице.) Измените вашу программу так, чтобы она выявляла стационарные колонии и сообщала о них. Можете ли вы придумать хоть какой-нибудь алгоритм, не использующий запоминания всех предыдущих поколений, который мог бы распознать любую стационарную колонию?

История колонии... Жизнь зачаровывает, если ее просматривать как фильм (это одно из соображений в пользу графического терминала), но она будет еще увлекательней, если предстанет в цвете. Каждой клетке при рождении может быть приписан некоторый цвет, определяемый, возможно, ее поколением или генами, переданными ей родителями. Циклические, но при этом движущиеся колонии (а таких немало) великолепны в своем сверкающем многоцветном наряде.

Любая колония имеет преемника, но не у каждой есть предшественник. Такие изолированные колонии называются садами Эдема. Сад Эдема можно увидеть, только если поместить его на плоскость в качестве начальной конфигурации. Подумайте, как использовать вашу программу для нахождения сада Эдема.

Беркс (ред.) (Burks A. W. (Ed.)). Essays on Cellular Automata. University of Illinois Press, Urbana, IL, 1970.

Кодд (Codd E. F.). Cellular Automata. Academic Press, New York, NY, 1968.

Обе эти книги значительно серьезнее статей Гарднера в Scientific American. Вторая из названных книг познакомит вас с основами предмета, а книга Беркса представляет собой сборник разнородных статей, охватывающих всю область клеточных автоматов. После изучения этих книг читателю будет доступен практически весь математический материал.

Гарднер (Gardner Martin). Mathematical Games. Scientific American, 223, 10, pp. 120–123, October 1970, and 224, 2, pp. 112–117, February 1971. [Имеется перевод: Гарднер М. Математические досуги. — Мл Мир, 1972, с. 458.]

Мартин Гарднер описал игру Жизнь в своей колонке журнала, и это вызвало такой отклик читателей, что он вынужден был немедленно (по меркам ежемесячного журнала) посвятить ей еще одну колонку. Игра Жизнь, несомненно, принесла славу Джону Хортону Конвею, ее талантливому и продуктивному изобретателю. В более поздних статьях содержится много дополнительного материала об игре Жизнь, а также о других работах Конвея.

Уэйнрайт (ред.) (Wainwright R. Т. (Ed.)). Lifeline. 1280 Edcris Road, Yorktown Heights, NY 10598.

Lifeline — ежеквартальный журнал, посвященный Жизни и родственным темам. Ориентированный на фанатиков этой игры, журнал содержит всевозможную информацию о Жизни, и его чтение может оказаться захватывающим занятием.