Веселая головоломка по информатике, бросающая вызов вашей изобретательности

В 1991 году я ехал в фургоне с другими студентами университета, когда возвращался с соревнований по программированию. Мы были в хорошем настроении, потому что только что заняли первое место на юго-востоке США. Мы были измотаны и возбуждены одновременно.

Мы не только читали цитаты из Монте-Пайтона, ели нездоровую пищу и вызывали ужасное пение друг друга, но и обсуждали алгоритмы. Возникла одна тема, которая меня заинтриговала: можно ли написать программу, которая печатает собственный исходный код?

Мы договорились о некоторых правилах. Программе не разрешено читать исходный код из внешнего источника. Вам не разрешается придумывать новый язык программирования для решения проблемы; вы должны использовать уже существующий язык программирования.

Для решения требуется исходный код, который при компиляции и выполнении генерирует идентичный исходный код на выходе. Ваш код может использовать библиотечные подпрограммы, поставляемые с языком, и ему не нужно распечатывать их исходный код (который в любом случае может быть недоступен).

Оказывается, это была не оригинальная идея. Позже мы узнали, что программа, которая распечатывает собственный исходный код, называется quine в честь логика Уилларда ван Ормана Куайна.

Остановись и подумай об этом. Как бы вы приготовили хайн?

Наша первая попытка

Неважно, какой язык программирования вы используете. Для обсуждения здесь давайте выберем почтенный, вездесущий C. Представленные здесь идеи будут работать на любом языке программирования общего назначения.

Если вы будете стрелять от бедра, вы, вероятно, начнете с чего-то вроде этого:

Вы еще не решили проблему, потому что эта программа распечатывает все, кроме операторов printf. В этом нет ничего страшного, правда? Нетрудно написать printf, выводящий другой printf, как показано в строке 7 здесь:

Строка 7 печатает первый printf в строке 4, которая, в свою очередь, печатает первую строку программы. И вы можете добавить дополнительный код после строки 7 для печати содержимого строк 5 и 6. Но тогда вы столкнетесь с проблемой. Теперь вам нужно написать код, который печатает строку 7. Итак, вам нужен printf, который печатает printf, который, в свою очередь, как вы догадались, распечатывает еще один printf.

Вы уже замечаете чувство опускания? Мы движемся к бесконечному регрессу, к башне черепах, каждая черепаха стоит на спине другой черепахи и спускается вниз без конца. Чем больше кода мы напишем, тем больше нам придется написать, чтобы распечатать его. И да, чтобы быть утомительным, лебедка должна быть конечной по размеру! Программа действительно должна уместиться внутри настоящего компьютера и работать на нем.

Я призываю вас остановиться, уделить время и поработать над этой проблемой. Посмотрите, сможете ли вы выбраться из бесконечной ловушки. Когда будете готовы к спойлерам, продолжайте читать.

Некоторые подсказки

Есть много разных решений этой проблемы, но у них, как правило, есть одна общая черта. Большинство из них объявляют переменную, содержащую текст программы за исключением данных переменной. Затем программа должна распечатать эту переменную двумя разными способами:

  1. Он печатает переменную в виде строки.
  2. Он печатает переменную как объявление переменной, которое соответствует тому, что указано в программе.

Это может быть осложнено тем фактом, что объявление переменной зажато между некоторым кодом, который идет до него, и некоторым кодом, который идет после него.

Этого может быть достаточно для вас, чтобы создать свой собственный хайн.

Еще одна идея: часто бывает удобно создать отдельную программу, которая считывает шаблон исходного кода как ввод и генерирует исходный код quine как вывод. Это может сделать работу намного менее утомительной.

Еще раз рекомендую вам попробовать себя в этом. Попробуйте, прежде чем продолжить.

Образец раствора

Если вы запутались, здесь я вкратце расскажу, как построить образец решения. Как я предложил в подсказке выше, я начинаю с файла шаблона с именем raw.c, который имеет исходный код, за исключением самого объявления данных. Я помещаю символ $ в строку 5 в качестве заполнителя для того места, где я хочу, чтобы было сгенерировано объявление данных. Да, $ - это синтаксическая ошибка, и эта программа не компилируется. Это шаблон программы, а не программы.

Изучите это, прежде чем приступить к пониманию того, как это работает. Переменная s - это текстовая переменная, которая будет содержать исходный код программы. Он будет сгенерирован другой программой, как показано ниже.

Цикл for в строке 6 печатает все символы ASCII в s, пока мы не достигнем значения непечатаемого символа 1. Этот символ представляет расположение символа $ в исходном коде.

В строках 7 и 8 печатается объявление массива символов в синтаксисе C, которое выглядит как {n,n,n,n,…,0}, где n - значения ASCII в целочисленной форме.

И, наконец, цикл for в строке 9 печатает символы исходного кода, которые появляются после $ в строке 5.

Теперь нам нужна другая программа, которая принимает raw.c в качестве входных данных и генерирует решение в качестве выходных данных. Я мог бы написать эту программу-генератор и на C, но это было бы скучно, правда? Напишем это на Python.

Вот что я придумал, называется factory.py.

Эта программа считывает файл raw.c, находит символ $ и заменяет его непечатаемым значением ASCII 1 в качестве контрольного значения.

Вывод формируется в строковую переменную quine в трех частях:

  1. Необработанный текст перед $.
  2. Объявление закодированного массива в форме {n,n,...1,n,n,...,0}.
  3. Необработанный текст после $.

Затем программа Python записывает результат в quine.c. Это настоящая лоза! Вот код:

Строка 5 довольно длинная. Чтобы увидеть все, взгляните на эту суть GitHub.

Попробуйте сами. Загрузите quine.c по сути, скомпилируйте его, запустите и посмотрите на результат. Он будет идентичен исходному коду.

Создайте свой!

Как я уже сказал, есть много других способов решить эту проблему. Используйте свое творчество и получайте удовольствие. Сделайте это на нескольких языках программирования.

В качестве дополнительной задачи вы можете увидеть, кто из ваших друзей-компьютерщиков может создать самую маленькую квинку на данном языке программирования.

Удачного взлома!

Ресурсы