Итоги новогоднего конкурса - Журнал "Компьютерра"

21 мая 2012 года

Итоги новогоднего конкурса

Автор: Владимир Пинаев
Опубликовано в журнале "Компьютерра" №1 от 04 февраля 2003 года

Мозги, давно отвыкшие от подобного напряжения, наконец вскипели и выдали что-то похожее на решение…
Константин Едренкин
АААААААААААА! Все равно не сдамся! (восклицание после очередной не очень удачной попытки)
Николай Логвинов
В полночь таки пришло озарение :) Высылаю последний на сегодня вариант. — Роман Шевцов
Давно не получал столько заряда бодрости, сколько получил, пытаясь найти решение задачи. Будет здоро-
во, если будут еще такие конкурсы. — Олег Момотов
Неужто, можно еще короче???? — Жуков Дмитрий
Из писем участников

Редакция поздравляет победителей и награждает каждого из них трехмесячной подпиской.

Вкратце напомним о новогодней конкурсной задаче («КТ» #471). Участники должны были написать интроспективную программу, то есть программу, печатающую свой собственный текст. Причем, чтобы не учитывать индивидуальные пристрастия читателей журнала, для ее решения был придуман специальный язык PIBAS, который включает в себя:

операторы присваивания и вывода;
операцию конкатенации строк и функцию вырезки подстроки;
задание строковых констант через двойные кавычки или апострофы.

По правилам конкурса для каждой программы измерялась ее длина в символах. Чтобы победить, необходимо было представить самую короткую интроспективную программу.

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

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

1. вспомогательная переменная A=”…”;

2. задание строк со значениями кавычек B=’’’’;C=”’”;

3. Вывод ?…

Рис.1 Структура решения

Покажем, что в операторе вывода нетрудно напечатать все, что ему предшествует. Но при этом разрешим себе использовать кавычки только того вида, которые не совпадают с ограничивающими кавычками первого оператора присваивания (рис. 2).

?’A=’+B+A+B+’;B=’+C+B+C+’;C=’+B+C+B

Рис. 2. Оператор вывода.

Итак, то, что предшествует оператору вывода, мы смогли напечатать. А как же напечатать сам оператор вывода? Но у нас еще есть резерв, а именно — мы пока не определили содержимое вспомогательной строки A. Так давайте добавим в оператор вывода печать строки A и поместим весь оператор вывода в эту строку (рис. 3).

A=”;?’A=’+B+A+B+’;B=’+C+B+C+’;C=’+B+C+B+A”;
B=’’’’;
C=”’”;
?’A=’+B+A+B+’;B=’+C+B+C+’;C=’+B+C+B+A

Рис. 3. Простая
интроспективная программа.

Если, как полагается в языке PIBAS, выписать наше решение в одну строчку, мы получим интроспективную программу из 92 символов. Совсем неплохо для начала! С таким решением мы заняли бы на конкурсе 26-е место.

Возникает вопрос, а зачем в язык PIBAS включена функция вырезания подстроки? Заметим, что в нашем решении в строке A присутствует несколько апострофов. Поэтому строку C можно исключить, а требуемый апостроф вырезать из строки A. Как и в первом решении, весь оператор вывода с небольшой приставкой включен в строку A (рис. 4).

A=”’;?’A=’+B+A+B+’;B=’+$(A,1,1)+B+A”;
B=’’’’;
?’A=’+B+A+B+’;B=’+$(A,1,1)+B+A

Рис. 4. Интроспективная программа
с функцией вырезки подстроки.

Длина этого решения составляет уже всего 73 символа, что соответствует девятому месту в итоговом протоколе конкурса.
Собственно, примерно такая программа, по мнению автора, и должна была победить. Но участники конкурса проявили недюжинную смекалку и существенно укоротили решение.

Стоит отметить программу из 68 символов (присланную несколькими участниками), в которой использовано всего два оператора (рис. 5).

A=”’;?$(A+A,32,34)+$(A+A,29,34)+”’+”’A=’”;
?$(A+A,32,34)+$(A+A,29,34)

Рис. 5. Интроспективная программа
из двух операторов.

А победителем новогоднего конкурса заслуженно стал Иван Басов. Седьмого декабря он первым прислал решение из 65 (!) символов (рис. 6). Мы поздравляем Ивана с победой и надеемся, что потраченной время с лихвой окупится повышением производительности труда в новом году!

A=’”;?B+A+$(B+”;B=”+A,3,5)+B+A’;
B=”A=’”;
?B+A+$(B+”;B=”+A,3,5)+B+A

Рис. 6. Самая короткая
интроспективная программа.

В дальнейшем еще шесть участников — Артем Родичев, Михаил Климов, Ярослав Мирошниченко, Сергей Беляев, Павел Толпегин и А. Тремба — прислали аналогичные решения. Полные протоколы конкурса доступны на www. pic200x.chat.ru.
В журнальной заметке невозможно написать обо всех идеях и предложениях, которые высказали наши читатели. Заметим только, что конкурс «КТ» получил продолжение в некоторых учебных заведениях — об этом нам сообщили студенты МАТИ и Владимир Антипов, учитель из Новомосковска Тульской области.
В заключение приведем диаграмму, отражающую длины всех решений.

версия для печати другие статьи автора оставить комментарий (0)
ТАКЖЕ В РАЗДЕЛЕ 01 сентября 2005 года Веселые фракталы 02 июня 2005 года Операция «Кооперация» или Пусть 1+1 будет 3 02 февраля 2005 года Старые игры на Гугловый лад 21 июня 2003 года Пи-клуб, питомник пижонов 31 марта 2003 года Размножение биоморфов 04 февраля 2003 года Компьютеррный гороскоп		MARKETGID Загрузка...