Архивы: по дате | по разделам | по авторам

Новогодний конкурс интроспективных программ

Архив

автор : Владимир Пинаев 27.11.2002

Каждый из нас лишь выиграет, создавая время от времени «игрушечные» программы с заданными искусственными ограничениями, заставляющими нас до предела напрягать свои способности. ... Искусство решения мини-задач на пределе своих возможностей оттачивает наше умение для реальных задач.
Д. Кнут [1]

Наверное, нет такого программиста, который бы не слышал о знаменитой задаче, сформулированной еще Винером. Смысл этой задачи состоит в написании программы, при работе которой на устройстве вывода появляется полная копия ее исходного текста. Причем любые обращения к файлам с исходными текстами или использование всевозможных системных штучек (например, знание некоего адреса сегмента памяти, где может храниться исходный текст исполняемой программы) запрещены. Такая программа называется интроспективной. Чаще всего при описании этого «орешка» ссылаются на известную книгу Чарльза Уэзерелла [2]. Хорошо известна и теорема (см., например, [3]) о том, что практически любой язык программирования позволяет написать такую программу.

«Компьютерра» в прошлом году уже обращалась к теме интроспективных программ. В статье «Квин-программы, или... 1 LIST» («КТ» ##381, 382) Константин Кноп привел с десяток решений на различных языках программирования. Мы же поставим задачу несколько иначе: требуется написать не любую, а как можно более короткую интроспективную программу!

Чтобы уравнять всех участников нашего конкурса, ниже будет определен некий простой язык программирования PIBAS, который содержит все необходимые средства для написания интроспективной программы. Этот язык, равно как и сама задача, был предложен участникам четвертьфинальных соревнований центрального региона России, проводившихся в Рыбинске в рамках студенческого командного чемпионата мира по программирования сезона 2002/2003 года. (Кстати, в эти дни в Санкт-Петербурге проводится полуфинал студенческого командного чемпионата мира по программированию по Северно-Восточному региону.)

Итак, мы предлагаем читателям написать как можно более короткую (по числу символов) интроспективную программу на языке PIBAS.

Лучшее решение будет опубликовано на страницах журнала.

Чтобы проверить свое решение, читатели могут либо скачать с сайта www.pic200x.chat.ru интерпретатор (автор Михаил Копачев) языка PIBAS, либо воспользоваться тестирующей оболочкой на сайте acm.timus.ru, где под номерами 1224-1232 размещены задачи рыбинского четвертьфинала, либо написать свой интерпретатор. Решения принимаются до 25 декабря включительно по адресу vpinaev@mail.ru с пометкой в теме письма «Introspective program».

Описание языка PIBAS

Программа на языке PIBAS состоит из одного или нескольких операторов, разделенных символом «;» (точка с запятой). Программа записывается в одну строку, длина которой не превышает 32 тысяч символов.
В языке имеются два вида операторов: оператор присваивания значения строковой переменной и оператор вывода строкового выражения.
Оператор присваивания имеет вид: <строковая переменная>=<строковое выражение>.
Строковая переменная задается одиночной заглавной латинской буквой.
Строковое выражение - это либо строковая переменная, либо строковая константа, либо функция вырезания подстроки, либо конкатенация строковых выражений через символ «+» (плюс).
Строковая константа - это строка любых печатных символов, заключенная в двойные («”») или одинарные («‘») кавычки за исключением кавычки того вида, которая используется для ее ограничения.

Примеры: ‘Rybinsk’, “O’ key!”, “I don’t know solution”.
Функция вырезания подстроки имеет вид: $(<строковая переменная>,<положительное число без знака>,<положительное число без знака>).

Первым параметром задается строковая переменная, из значения которой производится вырезка. Второй параметр задает номер начального символа вырезаемой подстроки, а третий параметр задает длину этой подстроки. Нумерация символов внутри строки начинается с единицы.
Оператор вывода имеет вид: ?<строковое выражение>.

Суммарная длина всех выведенных строк не должна превышать 32 тысяч символов.

Программа на языке PIBAS	Результат работы
?” Hello, “+’World!’	Hello, World!
A=’World, Hello!’;?$(A,8,5);?”, “;B=$(A,1,5)+’!’;?B	Hello, World!

Литература

[1] Лекции лауреатов премии Тьюринга: Пер. с англ./Под ред. Р. Эшенхерста. - М.: Мир, 1993.

[2] Уэзерелл Ч. Этюды для программистов. - М.: Мир, 1982.

[3] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. - М.: МЦНМО, 1999.