Дискретная модель, представляющая собой сетку произвольной размерности, каждая клетка которой в каждый момент времени может принимать одно из конечного множества состояний. Клетки переходят из одного состояния в другое по определённому правилу.
Простейший клеточный автомат — это одномерный ряд клеток, каждая из которых в каждый момент времени может находиться в одном из двух состояний (назовём их 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.
Программа должна получать на вход номер правила и выводить на экран графическое окно с изображением последовательных состояний простейшего клеточногл автомата. Количество клеток, время их жизни, размеры окна и прямоугольничков, показывающих состояния клеток, задайте в программе с помощью переменных, значения которых согласованы друг с другом.
Пример рисования закрашенного прямоугольника в drawzero:
from drawzero import *
x = 500
y = 500
width = 200
hight = 100
tick()
filled_rect("green", (x, y), width, hight)
tick()
Важно! Функция tick() включает режим анимации. Картинка будет обновляться после каждого вызова этой функции. Поскольку прямоугольничков нужно нарисовать много, обновляйте картинку либо после каждой строки, либо вообще когда всё будет нарисовано (но не после каждого прямоугольничка!)
Программа, рисующая один прямоугольник с использованием 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()
Клеточный автомат Конвея (игра «Жизнь»)
Тесты к этим задачам пока не подгружены.
Теперь рассмотрим двумерное пространство клеток. Каждая клетка в каждый момент времени может находиться в одном из двух состояний — «живое» и «мёртвое» (соответственно 1 и 0). В определённый момент все клетки синхронно переходят в новое состояние. Новое состояние зависит от текущего состояния данной клетки и 8 её соседей — по стороне и по диагонали (будем включать саму клетку в число её соседей, так удобней).
Правила, которые определяют состояние клетки автомата Конвея в момент времени k+1:
если живая клетка на такте k имеет меньше 3 и больше 4 соседей (в минимальной окрестности из 9 клеток, включающей её саму), то на такте k+1 она умирает (здесь простая аналогия с реальной жизнью — недостаток питания или перенаселенность),
в пустой клетке на такте k+1 появляется живая клетка, если у исходной клетки в минимальной окрестности ровно 3 соседа (три родителя!).
Можно исследовать жизнь клеточных автоматов и с другими правилами.
Для описания состояний клеток мы будем использовать не двумерный массив, а множество координат «живых» клеток.
G: Подсчёт числа соседей
Пусть имеется клетчатое поле.
Каждая клетка имеет две координаты: x и y . Координаты «живых» клеток будем хранить в множестве set_of_things. Например, если множество состоит из трёх элементов {(3, 3), (4, 3), (5, 3)}, это значит, что клетки с координатами (3, 3), (4, 3), (5, 3) — «живые», а остальные — «мёртвые».
Напишите функцию neighbours(set_of_things, x, y), которая получает на вход множество координат «живых» клеток и коордигаты x, y текущей клетки. Функция должна вычислять число «живых» соседей у клетки с координатами (x, y) (считая и саму клетку (x, y)).
Размеры поля пока не нужны.
neighbours({(3, 3), (4, 3), (5, 3)}, 4, 3)
3
neighbours({(3, 3), (4, 3), (5, 3)}, 4, 2)
3
neighbours({(3, 3), (4, 3), (5, 3)}, 3, 4)
2
IDE
Вызов функции для тестирования:
set_of_things = eval(input())
x, y = map(int, input().split())
set_copy = set_of_things.copy()
res = neighbours(set_of_things, x, y)
if set_of_things != set_copy:
print("Фунция не должна модифицировать передаваемые параметры")
else:
print(res)
H: Состояние поля на следующем шаге
Напишите функцию create_new_things(set_of_things, N), использующую функцию neighbours(set_of_things, x, y) (возможно, модифицированную), которая получает на вход исходное множество «живых» клеток автомата Конвея и размер поля (число N — сторона квадратного поля). Функция должна давать в ответе новое множество «живых» клеток, получающееся на следующем шаге.
Если клетка оказалась на краю поля, то её соседями будут клетки с другой стороны поля. То есть соседними будут левый и правый столбцы клеток, а также верхний и нижний ряды клеток. «Планета», на которой живут клетки, имеет форму тора.
create_new_things({(3, 3), (4, 3), (5, 3)}, 10)
{(4, 2), (4, 4), (4, 3)}
create_new_things({(4, 2), (4, 4), (4, 3)}, 10)
{(3, 3), (4, 3), (5, 3)}
IDE
Вызов функции для тестирования:
set_of_things = eval(input())
N = int(input())
res = create_new_things(set_of_things, N)
if type(res) != set:
print("Фунция должна давать в ответе множество")
else:
p_res = sorted(res)
for i in range(len(p_res)):
print(*p_res[i])
I: Состояние поля через время T
Напишите функцию game(set_of_things, N, T), вычисляющую состояние поля через T тактов. Функция получает на вход исходное множество set_of_things, число N — количество клеток в стороне квадратного поля, число T — количество тактов времени, которое прожили клетки. Функция должна давать в ответе новое множество «живых» клеток, получающееся через время T.
set_of_things = eval(input())
N = int(input())
T = int(input())
res = game(set_of_things, N, T)
if type(res) != set:
print("Фунция должна давать в ответе множество")
else:
p_res = sorted(res)
for i in range(len(p_res)):
print(*p_res[i])
J: Рисуем состояние поля в drawzero
Напишите функцию draw_things(set_of_things, N), рисующую в окне состояние поля, соответствующее множеству set_of_things. Функция получает на вход множество set_of_things и число N — количество клеток в стороне квадратного поля. Функция должна разбить графическое окно модуля drawzero (его размер равен 1000 пикселей) на $N^2$ клеточек и нарисовать в центре каждой клетки закрашенный круг.
Функция не должна модифицировать исходные данные.
Вызов функции для тестирования:
set_of_things = eval(input())
N = int(input())
draw_things(set_of_things, N)
from drawzero import *
# Добавьте все необходимые функции
N = int(input())
set_of_things = {(0, 2), (1, 0), (1, 2), (2, 1), (2, 2)}
sleep_time = 0.5 # Задержка в секундах
tick() # Включаем режим анимации
draw_things(set_of_things, N)
tick() # Обновляем картинку
sleep(sleep_time) # Пауза
while True:
set_of_things = create_new_things(set_of_things, N)
clear()
draw_things(set_of_things, N)
tick()
sleep(sleep_time)
L: Интерактивно задаём начальное состояние клеток
Недостаток предыдущей программы в том, что начальное состояние нужно задавать в тексте программы через координаты клеток. Можно сделать так, чтобы начальные условия задавались визуально с помощью мышки.
Напишите функцию edit_things(pos, set_of_things, N), где pos — координаты мышки в окне. Эта функция должна вычислять номер клетки, соответствующий заданным координатам, и, если такая клетка есть в множестве set_of_things, то удалять её из множества и рисовать на её месте круг цветом фона, а если нет — то добавлять её в множество и рисовать как живую клетку.
Код для тестирования:
from drawzero import *
# Добавьте все необходимые функции
N = int(input())
set_of_things = set()
while True:
tick()
for event in mousebuttonsdown:
if event.button == 1:
edit_things(event.pos, set_of_things, N)