Попробую рассказать о процессе написания квайнов на Brainfuck.
Процитирую свою статью Мультиязыковые квайны
Квайноподобную конструкцию (здесь и далее речь только о языках, где можно разделить данные и код) можно поделить на две части:
1) сегмент данных (важный момент, эта часть остаётся незаполненной до того момента, когда код будет завершён, после этого он кодируется).
2) сегмент кода
Сегмент данных — это некий шифр, который можно расшифровать двумя способами, в результате расшифровки первым способом получится строковое
представление собственно сегмента данных, при расшифровке вторым способом получится строковое представление сегмента кода. Объединив результаты этих расшифровок, мы получим строку, в которой содержится весь исходный код программы.
Обратите внимание на выделенный текст. В брейнфаке нет переменных, есть только и исключительно исполняемый код. С другой стороны, есть лента, которой можно и нужно пользоваться для хранения информации.
Поэтому, для брейнфака схема квайна будет выглядеть так.
1) Код, который записывает на ленту данные
2) Код, который читает с ленты данные и выводит код из п.1
3) Код, который читает с ленты данные и выводит код из п.2 и п.3
Соответственно код из п.1 можно получить «шифрованием» кода из п.2 и п.3, когда он будет написан.
В каком виде записывать данные на ленту? Напрашивается запись в виде ascii-кодов символов.
Напишем функцию на Питоне, которая получает строку и возвращает программу на брейнфаке, записывающую эту строку на ленту.
def to_brainfuck(st): return '>'+''.join('+'*ord(c)+'>' for c in st) >>> print to_brainfuck('ku') >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> Обратите внимание на ">" в начале программы, пустая ячейка в начале ленты нужна на тот случай, если туда придётся возвращаться. Пустая ячейка это единственный способ остановить цикл в Брейнфаке. Если реализация брейнфака работает с бесконечной в обоих направлениях лентой, ">" в начале можно опустить.
Теперь вернёмся в начало ленты
<[<]и распечатаем её содержимое:
>[.>]Программа выведет на экран «ku»
Как написать код для п.1 и п.3 нашей схемы мы уже примерно знаем.
Теперь п.2, самая сложная часть.
Итак, нужно написать программу, которая используя содержимое ленты выведет ту строчку, которую вывела комманда print to_brainfuck(‘ku’), фактически аналог питоновской функции to_brainfuck на брейнфаке.
Печатать брейнфак умеет только те символы, которые есть на ленте. Комманда "." печатает содержимое ячейки на которой стоит каретка. Следовательно нам нужно записать символы "+" и ">" на ленту.
>+++++++++++++++++++++++++++++++++++++++++++> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.Обратите внимание на ">" в начале — оставляем пустую ячейку-маркер между тем, что уже есть на ленте и всякой служебной информацией, которую мы туда записываем. Так же обратите внимание на "." в конце. Помните ">" в самом начале программы? Вот тут её и выведем.
вернёмся на начало ленты
[<]<[<]>теперь напишем вложенный цикл. внутренний цикл «отщипывает» по одному от содержимого очередной ячейки и при каждом таком отщипывание выводит "+", внешний цикл выводит ">" и переходит к следующей ячейке
[ [ [>]> доходим до того места на ленте, где лежит "+" . печатаем "+" <<[<]>- возвращаемся к обрабатываемому символу и отнимаем единицу ] >[>]>> после того, как символ кончился, доходим до места, где лежит ">" . печатаем ">" [<]<[<]> возвращаемся к следующему символу ] итак, мы можем написать программу А, заполняющую ленту и программу Б, бегущую по заполненной ленте и выводящую программу А.
Правда у программы Б есть один недостаток, после её деятельности на ленте ничего не остаётся, а нам содержимое ленты нужно для последующей печати.
Изменим программу Б так, чтобы при каждом уменьшении содержимого ячейки на одном конце ленты, она увеличивала содержимое ячейки на другом конце. Новый код ставлю под старым и выравниваю, чтобы были видны проделанные изменения:
[[[>]>. << [<]>-]>[>]>>. [<]<[<]>] было [[[>]>. [>]<+[<]< [<]>-]>[>]>>. [>]+ [<]<[<]>] стало После выполнения программы, содержимое ячеек с копией на 1 больше чем нужно. Не будем ничего переделывать, просто поправим и распечатаем
>>>[->]<<[<]>>>[.>] этот код мне не очень нравится, кажется можно сильно короче, что-то вроде:
>>>[-.>] только без выведения ascii-0 в конце, но сходу не придумывается.
Соединяем всё вместе
вносим символы "k" и "u" на ленту >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> вносим символы "+" и ">" на ленту, а так же выводим ">" >+++++++++++++++++++++++++++++++++++++++++++> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++. отмечаем начало области, в которую будем копировать символы >+ возвращаемся на начало ленты [<]<[<]> описанный выше вложенный цикл, основная часть программы [[[>]>.[>]<+[<]<[<]>-]>[>]>>.[>]+[<]<[<]>] отнимаем по единице от каждого символа и выводим символы >>>[->]<<[<]>>>[.>] итак, у нас есть программа, которая забивает на ленту коды символов «k» и «u», затем распечатывает ту свою часть, которая их забивает, затем распечатывает сами символы. Т.е. в данный момент это уже почти квайн, программа распечатывает свою первую часть, а вместо второй она распечатывает «ku». А всё почему? Потому что именно строку «ku» мы скормили вначале питоновской функции to_brainfuck. А должны были текст программы. Но его тогда ещё не было. Зато теперь есть!
Теперь самый приятный момент. Берём ту часть программы, которую мы написали руками и скармливаем функции to_brainfuck. Объединяем две части и квайн готов:
>>> s=""">+++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+[<]<[<]>[[[>]>.[>]<+[<]<[<]>-]>[>]>>.[>]+[<]<[<]>]>>>[->]<<[<]>>>[.>]""" >>> def brainfuck(st): return '>'+''.join('+'*ord(c)+'>' for c in st) >>> print brainfuck(s)+s >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+[<]<[<]>[[[>]>.[>]<+[<]<[<]>-]>[>]>>.[>]+[<]<[<]>]>>>[->]<<[<]>>>[.>]
Получившийся квайн не слишком компактен из за выбранного способа кодирования, на каждый символ «сегмента кода» приходится около 50 символов «сегмента данных». Можно значительно уменьшить сегмент данных если прибегнуть к другим способам кодирования, разумеется, в этом случае сильно увеличится та часть программы, которую нужно писать руками.
Да, ещё один забавный момент. Т.к. брейнфак игнорирует все символы, кроме тех восьми, которые являются его коммандами, можно перед шифрованием как-нибудь интересно отформатировать код и/или добавить туда какие-нибудь надписи. Квайн от этого не перестанет быть квайном.
>+++++++++++++++++++++++++++++++++++++++++++> + + + Quine for Habrahabr + + + + + +++++++++++++++++++++++++++++++++++++++++++++ + + + + + + + + + . > + [ < ] < [ < ] > [ [ [ > ] > . [ > ] < + [ < ] < [<]>-]>[>]>>.[>]+[<]<[<]>]>>>[->]<<[<]>>>[.>] Внутри квадрата можно ещё чего-нибудь добавить. Полный текст квайна не привожу, т.к. такие игры с форматированием в разы увеличивают размеры «сегмента данных» и квайн становится совсем уж огромным. Спасибо за внимание.
Кто-нибудь до конца дочитал? 🙂
ссылка на оригинал статьи http://habrahabr.ru/post/193764/
Добавить комментарий