Дискретная модель, представляющая собой сетку произвольной размерности, каждая клетка которой в каждый момент времени может принимать одно из конечного множества состояний. Клетки переходят из одного состояния в другое по определённому правилу.
Простейший клеточный автомат — это одномерный ряд клеток, каждая из которых в каждый момент времени может находиться в одном из двух состояний (назовём их 0 и 1). В определённый момент все клетки синхронно переходят в новое состояние. Это состояние зависит от текущего состояния данной клетки и двух её ближайших соседей. Правило, определяющее новые состояния всех клеток, — это функция, которая каждому трёхзначному двоичному числу (текущему состоянию трёх клеток) ставит в соответствие 0 или 1 — новое состояние центральной клетки.
Правило можно задать с помощью таблицы истинности. Всего существует 256 вариантов правил (различных логических функций для трёхразрядного числа). Некоторые из них не очень интересны, например, те, которые дают в ответе только 0 или только 1. А некоторые порождают длинную «жизнь» простейшего клеточного автомата и даже описывают процессы, происходящие в реальности.
Сначала научимся визуализировать состояние нашего клеточного автомата (потом можно будет заменить эту функцию графической, а пока использьзуем простой текстовый вариант).
Напишите функцию draw_line(a), которая получает на вход список из 0 и 1 и печатает строку, где на местах, соответствующих 0 из данного списка, будут пробелы, а на местах, соответствующих 1, — символы @.
Список менять не нужно.
[1, 0, 0, 1, 1, 1, 0, 1, 0, 1]
@ @@@ @ @
IDE
Вызов функции для тестирования:
a = eval(input())
a_copy = a[:]
res = draw_line(a)
if a != a_copy:
print("Фунция не должна модифицировать передаваемые параметры")
if res is not None:
print("Функция НЕ должна возвращать значение")
B: Из двоичной системы — в десятичную
Напишите функцию bin_to_dec(a),
которая получает на вход список из 0 и 1, интерпретирует его элементы как цифры двоичного числа и даёт на выходе соответствующее десятичное число. Эта функция пригодится для вычисления нового состояния каждой клетки.
[1, 1, 1, 1, 1, 0, 0, 1, 1, 0]
998
IDE
Вызов функции для тестирования:
a = eval(input())
print(bin_to_dec(a))
C: Из десятичной системы — в двоичную
Напишите функцию dec_to_bin8(n), получающую на вход целое неотрицательное число и возвращающую список из 8 элементов — разрядов соответствующего двоичного числа, индекс элемента — это номер разряда.
(Если число больше 255, то старшие биты отбрасываются). Эта функция пригодится для задания правила перехода в новое остояние.
1
[1, 0, 0, 0, 0, 0, 0, 0]
30
[0, 1, 1, 1, 1, 0, 0, 0]
IDE
Вызов функции для тестирования:
n = int(input())
res = dec_to_bin8(n)
if type(res) == list:
print(' '.join(map(str, res)))
else:
print("Функция должна возвращать список")
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. А новое состояние клетки — это элемент списка с индексом, соответствующим текущему состоянию трёх клеток.
Как по текущему состоянию «клетки» и её соседей вычислить её новое состояние — подробно описано в статье в разделе «Что означают коды Вольфрама» (можно использовать функцию из задачи В).
Чтобы избежать «краевых эффектов», замкнём цепочку клеток в кольцо. То есть для первой «клетки» соседними будут вторая и последняя, для последней — предпоследняя и первая.
Используйте свою функцию из задачи B.
Исходный список можно сделать случайным с помощью функции randint из модуля random.
a = eval(input())
rule = eval(input())
res = new_line(a, rule)
if type(res) == list:
print(' '.join(map(str, res)))
else:
print("Функция должна возвращать список")
E: Жизнь простейшего клеточного автомата — текстовый вариант
Напишите программу, которая создаёт ряд клеток — список заданного размера, состоящий из 0 и одной 1 в середине списка — и по заданному правилу печатает «протокол» жизни этих клеток.
Программа получает в первой строке на вход два числа: $N$ — длину ряда клеток и $M$ — время жизни клеточного автомата. В следующей строке задаётся десятичное число — номер правила. При переводе десятичного числа в список из 0 и 1, задающий правило, нулевой разряд числа становится нулевым элементом списка, первый — первым элементом, ..., седьмой — седьмым элементом. Например, приведённая выше таблица истинности соответствует правилу № 30.
Программа должна напечатать $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()