Дискретная модель, представляющая собой сетку произвольной размерности, каждая клетка которой в каждый момент времени может принимать одно из конечного множества состояний, для которой определено правило перехода клеток из одного состояния в другое.
Простейший клеточный автомат — это одномерный ряд клеток, каждая из которых в каждый момент времени может находиться в одном из двух состояний (назовём их 0 и 1). В определённый момент все клетки синхронно переходят в новое состояние. Это состояние зависит от текущего состояния данной клетки и двух её ближайших соседей. Правило, определяющее новые состояния всех клеток, — это функция, которая каждому трёхзначному двоичному числу (текущему состоянию трёх клеток) ставит в соответствие 0 или 1 — новое состояние центральной клетки.
Правило можно задать с помощью таблицы истинности. Всего существует 256 вариантов правил (различных логических функций для трёхразрядного числа). Некоторые из них не очень интересны, например, те, которые дают в ответе только 0 или только 1. А некоторые порождают длинную «жизнь» простейшего клеточного автомата и даже описывают процессы, происходящие в реальности.
Сначала научимся визуализировать состояние нашего клеточного автомата (потом можно будет заменить эту функцию графической, а пока использьзуем простой текстовый вариант).
Напишите функцию draw_line(a), которая получает на вход список из 0 и 1 и печатает строку, где на месте 0 будут пробелы, а на месте 1 символы @.
B: Из двоичной системы — в десятичную
Напишите функцию bin_to_dec(a),
которая получает на вход список из 0 и 1, интерпретирует его элементы как цифры двоичного числа и даёт на выходе соответствующее десятичное число. Эта функция пригодится для вычисления нового состояния каждой клетки.
C: Из десятичной системы — в двоичную
Напишите функцию dec_to_bin8(n), получающую на вход целое неотрицательное число и возвращающую список из 8 элементов — разрядов соответствующего двоичного числа, индекс элемента — это номер разряда.
(Если число больше 255, то старшие биты отбрасываются). Эта функция пригодится для задания правила перехода в новое остояние.
D: Вычисляем новую строку
Напишите функцию new_line(a, rule), которая получает на вход старый список из нулей и единиц и двоичный код правила (список из 8 элементов, вычисленный функцией из задачи С), и вычисляет новый список из 0 и 1, получающийся из старого с использованием заданного правила.
Правило вычисления нового состояния клетки мы можем записать в виде таблицы истинности, аргументы которой — состояния левой, центральной и правой клеток, а результат — новое состояние центральной клетки, например:
$A[i - 1]$
$A[i]$
$A[i + 1]$
$newA[i]$
0
0
0
0
0
1
0
0
1
1
2
0
1
0
1
3
0
1
1
1
4
1
0
0
1
5
1
0
1
0
6
1
1
0
0
7
1
1
1
0
Заметим, что аргумент функции можно интерпретировать как двоичное число от 0 до 7. Соответственно, правило можно задать в виде списка из 8 чисел — 0 или 1. А новое состояние клетки — это элемент списка с индексом, соответствующим текущему состоянию трёх клеток.
Как по текущему состоянию «клетки» и её соседей вычислить её новое состояние — подробно описано в статье в разделе «Что означают коды Вольфрама» (можно использовать функцию из задачи В). Для первой «клетки» соседними будут вторая и последняя, для последней — предпоследняя и первая. Используйте функцию из задачи А для визуализации исходного и нового списков.
Исходный список можно сделать случайным с помощью функции randint из модуля random.
E: Жизнь простейщего клеточного автомата — текстовый вариант
Напишите программу, которая создаёт ряд клеток — список заданного размера, состоящий из 0 и одной 1 в середине списка — и по заданному правилу печатает «протокол» жизни этих клеток.
Программа получает на вход два числа: $N$ — длину ряда клеток и $M$ — время жизни клеточного автомата. В следующей строке задаётся десятичное число — номер правила. Программа должна напечатать $M + 1$ строку — последовательные состояния одномерного клеточного автомата.
F: Жизнь простейщего клеточного автомата — графический вариант
Напишите программу, которая рисует последовательные состояния одномерного клеточного автомата в графическом режиме.
Можно использовать модуль drawzero или модуль tkinter. Каждое состояние 0 или 1 показывайте с помощью прямоугольника соответствующего цвета. Напишите новую функцию для визуализации текущего состояния системы вместо текстовой функции из пункта A и используйте её в своей программе. Начальный список сделайте случайным с помощью функции randintиз модуля random.
Программа, рисующая один прямоугольник с использованием tkinter:
from tkinter import Tk, Canvas, mainloop
SIZE = 10 # размер прямоугольника
N = 100 # число клеток
XMAX = N * SIZE # ширина холста
YMAX = 400 # высота холста
# Создаётся графическое окно, на которое ссылается переменная root
root = Tk()
# Создаётся холст размером XMAX на YMAX, на который ссылается переменная canv
canv = Canvas(root, width=XMAX, height=YMAX, bg="lightblue")
# Холст размещается в окне
canv.pack()
# создаётся прямоугольник без обводки со стороной SIZE в точке (x, y):
x = 0
y = 0
canv.create_rectangle(x, y, x + SIZE, y + SIZE, fill="blue", width=0)
# Графическое окно выводится на экран и готово реагировать на события
root.mainloop()