Здравствуйте, извините за неканоническое использование шаблона "Спортивное программирование и...".

Недавно мне стало интересно, как много авторов задач для соревнований по программированию пишут задачи о языках программирования (кроме меня :-D). Я робко надеялась не оказаться одинокой в своей любви к этой тематике, но действительность превзошла все мои ожидания. Конечно, задачи о языках программирования встречаются реже, чем задачи о компьютерах, процессорах, платах, чипах, параллельных вычислениях, базах данных и прочих околокомпьютерных вещах, но все-таки гораздо чаще, чем, скажем, о драконах :-)

1. TopCoder

В свое время (то есть до 2006 года, к которому относится самая свежая из найденных мной задач) на TopCoder промелькнуло несколько задач о ЯП. В большинстве своем (7/9) они достаточно однотипны: дается исходный код программы на си- или паскалеподобном языке, требуется его проанализировать и доложить результаты.

Сложно сказать, в чем именно причина пересыхания ручейка задач о ЯП. Навскидку могу предложить несколько вариантов:

• смена алго-координатора (или его эстетического вкуса).
• отсутствие особого интереса к теме среди авторов. Придумать задачу о чем-то абстрактном гораздо проще, чем на какую-то определенную тему, тем более на такую.
• фокус на алгоритмической стороне задачи, а не на деталях длинной и неаппетитной реализации.
• ограниченность выразительных средств задачи: если, к примеру, требовать не анализировать заданные программы, а генерировать свои, то задача сразу становится сложнее, как минимум за счет того, что ответ должен определяться однозначно (система тестирования на TopCoder не позволяет как-то обрабатывать возвращаемое значение, например, интерпретировать программу и сравнить ее вывод с эталонным выводом, сравниваются обязательно сами возвращаемые значения). А это значит, что нужно накладывать искусственные ограничения на программу — минимальная возможная длина, лексикографическое первенство среди всех программ с такой длиной и т.д. Найти алгоритм, гарантирующий минимальную длину программы, и доказать его правильность — задача явно не одного СРМа :-)
• в постановке задачи "сгенерируйте программу, которая делает нечто", это "нечто" должно хорошо параметризоваться входными данными (то есть наборов входных данных должно быть много, и они должны отличаться нетривиальным образом); навскидку придумывается разве что "выводит заданное сообщение", да "вычисляет заданное арифметическое выражение" — не очень интересно.

2. Codeforces

На Codeforces с задачами на ЯП все обстоит довольно неплохо — кроме моего прошлогоднего раунда, нашлись задачи 93C - Аземблер (о генерации программы на языке типа Ассемблера) и 39A - Вычисления в C*++ (об операциях a++ и ++a). В целом это дело наживное — возможности системы позволяют делать задачи достаточно разнообразными, дело только за фантазией авторов.

P.S. И сразу же подкрепление этого тезиса — сегодняшняя задача 195C - Попробуй поймай об обработке исключений в языке Vasya Programming Language. Ну как тут не поверить в ноосферу? :-)

3. Challenge24

Я уже упоминала, что я очень люблю этот контест? Ну, значит, повторюсь: я очень его люблю, не в последнюю очередь за разнообразие тем и формата задач. Последнее время (если быть точной, последние четыре года) либо в финале, либо в отборочном раунде обязательно присутствует задача, в которой нужно либо писать программы на каком-нибудь странном языке, либо писать его интерпретатор. Ну то есть как "писать" программы — в 2011 году программы сдавались на "перфокартах", и команды языка кодировались жирными черными точками-"отверстиями" на них. В 2009 году в роли странного языка выступал Piet, и программы были изображениями, хоть и записанными в текстовом формате.

Следует отметить, что для Ch24 такой формат задач подходит практически идеально. Во-первых, он сильно отличается от типичных задач соревнований, то есть у алго-красных на нем не такое огромное преимущество — хотя формат, в котором у них преимущества нет вообще, я пока не представляю :-) Во-вторых, он очень хорошо реализует сразу два принципа Ch24 — первые (небольшие) тесты можно решить вручную, для более сложных уже придется писать какую-то автоматизацию, и сабмиты участников можно сравнивать по "качеству" (длине сгенерированного кода), тем самым реализуя относительный скоринг. Наконец, длина и командность соревнования позволяет давать задачи, для решения которых нужно сначала написать интерпретатор языка, а только потом переходить к программам.

4. IPSC

Еще один контест, формат которого практически не ограничивает фантазию авторов: для каждой задачи нужно всего два теста, причем они могут значительно отличаться по смыслу (в отличие от Challenge24, в котором тесты к задаче отличаются в основном размерами и сложностью). В результате каждый год (кроме, увы, последнего) организаторы балуют участников какой-нибудь затейливой задачей о ЯП.

5. Другие источники задач

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

• Первый же взгляд на acm.timus.ru являет нам тэг "unusual problems" и задачу Introspective Program, требующую написать квайн на загадочном языке PIBAS.
• Взгляд чуть более внимательный находит Language Ocean с восточного четвертьфинала NEERC 2011, в которой необходимо реализовать вывод типов переменных и проверку корректности этих типов.
• И задачу Time Limit Exceeded, в которой приходится интерпретировать заданную программу и безжалостно ее прерывать после первых десяти миллионов команд.
• И задачу Brainfuck, требующую сгенерировать кратчайшую программу на варианте Brainfuck без циклов.
• Целая серия задач от УрГУ (Ural State University) знакомит участника с языком D++ (который не имеет ничего общего ни с Meta D++, ни с DigiSystems D++, ни с D++ для распределенных вычислений).
• Задача H. Рекурсия c восьмой интернет-олимпиады для школьников сезона 2007-08 предлагала участникам выяснить, можно ли вызвать какую-то из процедур заданной программы на языке Ж+- с такими параметрами, чтобы она ушла в бесконечную рекурсию.

А какие задачи о языках программирования знаете вы?