$L$-система или система Линденмайера — это система последовательного переписывания команд.
$L$-система состоит
из алфавита символов, которые могут быть использованы для создания строк;
набора порождающих правил, которые задают правила подстановки вместо каждого символа;
начальной строки («аксиомы»), с которой начинается построение;
механизма перевода образованной строки в геометрические структуры.
$L$-системы предложил и развивал в 1968 Аристид Линденмайер, венгерский биолог и ботаник из Утрехтского университета.
Линденмайер использовал $L$-системы для описания поведения клеток растений и моделирования процесса развития растения.
$L$-системы использовались также для моделирования морфологии различных организмов и могут быть использованы для генерации самоподобных фракталов.
Ниже примеры растений, полученные при помощи $L$-систем.
Итерпретатор черепашьего языка
Эта часть отвечает за механизм перевода строки в геометрические структуры.
В предыдущий раз мы писали рекурсивные функции, порождающие те или иные фрактальные (самоподобные) структуры.
Можно пойти дальше и описать язык, порождающий последовательности команд управления черепашкой.
Теперь надо написать только одну функцию-интерпретатор, переводящую предложения нашего языка
на язык команд черепашки. А разные фракталы — это просто разные предложения на описанном нами языке.
Состояние черепашки описывается тройкой $(x, y, \alpha)$, где $x$, $y$ — декартовы координаты
черепашки, а $\alpha$ — угол (в градусах, отсчитываемый от положительного направления
оси $Ox$), в направлении которого черепашка движется (см. t.pos(), t.heading() и их set-варианты).
Теперь опишем команды в нашем новом фрактально-черепашьем языке.
Зафиксируем два числа: $d$ — величина шага и $\delta$ — величина изменения угла черепашки.
Тогда в нашем языке пока будут только следующие 4 команды:
F — сделать шаг длины $d$ в направлении угла $\alpha$ и нарисовать соответствующий отрезок (forward). При этом состояние из $(x, y, \alpha)$ переходит в $(x', y', \alpha)$, где $ x' = x + d\cdot\cos\alpha$, $y' = y + d\cdot\sin\alpha$;
f — всё то же самое, но отрезок не рисуется;
+ — повернуть налево на угол $\delta$. Состояние черепашки меняется на $(x, y, \alpha+\delta)$. Поворот
на положительный угол происходит против часовой стрелки;
- — повернуть направо на угол $\delta$. Состояние черепашки меняется на $(x, y, \alpha-\delta)$.
A: Интерпретатор черепашьего языка
Напишите функцию interpret, принимающую на вход фиксированную величину $d$, угол $\delta$, а также строку, состоящую из команд Ff+- без пробелов.
Функция должна проинтерпретировать программу черепашки в соответствии с языком, описанным выше.
100 90
F+F+F+F
100 45
F+F--F+F
50 30
FF+++f---FF+++f---FF
Генерация управляющих команд
Для порождения строк, управляющих черепашкой можно воспользоваться следующей универсальной конструкцией.
Пусть $V$ — некоторый алфавит, то есть просто формальное множество букв.
Например, алфавитом может быть наш набор команд: $V = \{F, f, +, -\}$.
Возьмём непустое слово $\omega$ в этом алфавите (то есть просто последовательность букв), которое мы будем называть аксиомой, axiom.
И наконец возьмём набор пар $P$ вида (буква, соответстующее_ему_слово), которые называются продукциями, productions.
Будем записывать продукции в виде $a \to \mu$.
При этом требуется, чтобы для каждой буквы $a$ была хотя бы одна продукция $a \to \mu$.
Обычно $P$ записывают в виде небольшого списка продукций, подразумевая, что для всех остальных букв задана продукция $a \to a$.
Тройка $G=(V,\omega,P)$ называется $L$-системой (или системой Линденмайера).
Идём дальше, у нас задана $L$-система $G=(V,\omega,P)$.
Говорят, что слово $\nu$ напрямую выводится (derive) из слова $\mu=a_1a_2\ldots a_n$ (и записывается $\mu \Rightarrow \nu$), если слово $\nu$ получается из слова $\mu$ заменой каждой буквы $a_i$ на какую-нибудь из продукций $a_i \to \ldots$.
И наконец, слово $\nu$ порождается $L$-системой $G$, если его можно вывести из начальной аксиомы $\omega$ за несколько шагов.
Заметим, что если не существует двух различных продукций вида $a\to\mu_1$ и $a\to\mu_2$, то $L$-система порождает просто последовательность слов,
которые последовательно получаются из аксиомы.
В питоне такие продукции удобно задавать с помощью словаря P, из которого выводимое слово «добывается» при помощи команды вида P.get(a, a).
Так, сложные определения в сторону, рассмотрим примеры.
В качестве алфавита будут выступать команды черепашьего языка: $V = \{F, f, +, -\}$.
Возьмём $\omega=$F, и единственную нетривиальную продукцию F$\to$FF.
Такая $L$-система порождает только скучный набор слов F, FF, FFFF и так далее.
Возьмём другую продукцию F$\to$F+F.
Эта $L$-система порождает последовательность слов F, F+F, F+F+F+F и так далее.
Самое время добавить магии :)
Возьмём продукцию F$\to$F+F-, $d=50$ и $\delta=90$ и проинтерпретируем последовательность, порождаемую $L$-системой нашей черепашкой.
Вот что получится (где-то вы эту кривую уже видели, да?):
F
Больше магии!
Возьмём $\omega=$F-F-F-F, и единственную нетривиальную продукцию F$\to$F-F+F+FF-F-F+F.
Возьмём $d=50$ и $\delta=90$ и проинтерпретируем нашей черепашкой последовательность слов, порождаемых $L$-системой.
B: Однозначное выведение
Напишите функцию derive, принимающую на вход словарь продукций, а также слово, и возвращающую слово, которое из него выводится.
При этом для каждой буквы $a$, не встречающейся в словаре продукций, мы считаем, что $a\to a$.
Формат ввода. В первой строке даётся целое число N — количество продукций.
В следующих N строках даются продукции в формате a word, где a — буква, а word — выводимое слово (которое может не быть словом в обычном понимании).
Гарантируется, что буквы в продукциях не повторяются.
Затем идёт число M — число тестов.
В следующих M строках идут слова, для каждого из которых нужно вывести следующее.
1
F F+F-
3
F
Hello, world!
FF+abc+FF--
F+F-
Hello, world!
F+F-F+F-+abc+F+F-F+F---
3
A hello
B world
o (o was here)
4
A B
hello world
BA IS REALLY COOL!
BATTERY INCLUDED
hello world
hell(o was here) w(o was here)rld
worldhello IS REhelloLLY COOL!
worldhelloTTERY INCLUDED
Для каждого из следующих наборов (число $n$, величины $d$ и $\delta$, а также $L$-система)
нарисуйте черепашкой картинку, которая получается после $n$ выведений из аксиомы.
Картинки нужно построить последовательно, выполняя turtle.resetscreen() между рисунками.
D: Снежинка Коха
Реализуйте при помощи $L$-системы снежинку Коха.
На вход даётся неотрицательное число $n$.
Постройте кривую «степени» $n$.
Картинки с примерами
0
1
5
E: Кривая Минковского
Реализуйте при помощи $L$-системы снежинку кривую Минковского.
На вход даётся неотрицательное число $n$.
Постройте кривую «степени» $n$.
Картинки с примерами
0
1
2
3
F: Интерпретатор черепашьего языка — 2
Для того, чтобы расширить возможности по генерации самоподобных картинок при помощи $L$-систем добавим в интерпретатор черепашки дополнительные синонимы.
Команды L и R должны работать так же, как и команда F, а команды l и r — аналогично команде f.
Добавим ещё две команды в черепаший язык — квадратные скобки [ и ].
Они должны интерпретироваться следующим образом:
[ — сохранить текущее состояние черепашки $(x, y, \alpha)$ в стек;
] — вынуть с верхушки стека запомненное ранее состояние и сделать его текущим.
Добавьте эти новые возможности в функцию interpret.
100 90
F+L+R+F
50 30
RF+++l---FF+++r---LF
50 90
FF[+FF-F][-FF+F]FF
G: Кривая дракона
Оказывается, кривую дракона очень легко построить, используя подобную технику. Нужно взять
$\delta=90$;
$\omega=$L;
$P=\{$L$\to$..., R$\to$...$\}$
Восстановите многоточия и постройте кривую Дракона.
На вход даётся неотрицательное число $n$.
Постройте кривую «степени» $n$.
Ориентация кривой важна, первый поворот — налево.
Картинки с примерами
0
1
2
3
4
5
10
18
H: Салфетка Серпинского
Используя два вида продукций (для L и R), придумайте правила вывода “салфетки Серпинского”. Угол поворота равен 60 градусов.
Первые 5 итераций на рисунке ниже:
На вход даётся неотрицательное число $n$.
Постройте кривую «степени» $n$.
I: Кривая Госпера
Используя два вида продукций (для L и R), придумайте правила вывода кривой Госпера. Угол поворота равен 60 градусов.
Первые 4 итерации на рисунке ниже:
На вход даётся неотрицательное число $n$.
Постройте кривую «степени» $n$.
Ориентация кривой важна, первый поворот — направо.
J: Кривая Гильберта
Кривая Гильберта — это непрерывная кривая, заполняющая целиком квадрат.
На первой картинке кривые Гильберта, с первого по четвёртый шаги.
В пределе получается кривая, которая заполняет квадрат целиком!
Впрочем первую такую кривую придумал в 1890 году (годом ранее) итальянский математик Джузеппе Пеано.
Для рисования кривой Гильберта пригодятся буквы, которые никак не интерпретируются черепашкой.
Например, A и B.
Придумайте правила вывода кривой Гильберта, используя два вида продукций — для A и B.
На вход даётся неотрицательное число $n$.
Постройте кривую «степени» $n$.
K: Случайное выведение
Можно отказаться от детерминированности правил вывода и добавить в этот процесс случайность.
Рассмотрим $L$-систему, в которой для одной и той же буквы есть несколько продукций $a\to\mu_1, a\to\mu_2, \ldots$.
Тогда при выведении букву $a$ мы будем заменять на случайно выбранное слово из $\mu_1, \mu_2, \ldots$.
Для этого можно использовать random.choice.
Формат ввода. В первой строке даётся целое число N — количество продукций.
В следующих N строках даются продукции в формате a word, где a — буква, а word — выводимое слово (которое может не быть словом в обычном понимании).
Затем идёт число M — число тестов.
В следующих M строках идут слова, для каждого из которых нужно вывести следующее.
Обратите внимание, что ответ носит случайный характер и может не совпадать с примером.
3
F FF
F -1-
F =2=
4
F,F
F,F
F,F
F,F
FF,-1-
=2=,-1-
=2=,FF
-1-,-1-
L: Растенье-подобная структура — 1
Для данного $n$ нарисуйте черепашкой картинку, которая получается после $n$ выведений из аксиомы.
Перед началом рисования поверните черепашку «головой» вверх.
Для данного $n$ нарисуйте черепашкой картинку, которая получается после $n$ выведений из аксиомы.
Ниже приведён пример запуска одной и той же программы с указанными правилами.
