Соревнование закончилось ещё позавчера, но во мне до сих пор бушуют эмоции. По сложности и непредсказуемости ICFPC соперничает с самой жизнью, и в этом году организаторы, кажется, подобрались к цели максимально близко — может быть, даже чересчур близко. Я не смогу уместить все детали в один репортаж, так что вместо одного поста будет шесть:

1. предисловие (это то, что вы сейчас читаете);
2. день первый;
3. день второй;
4. день третий;
5. день четвёртый;
6. итоги и выводы.

Погодите, а что такое ICFPC?

Это соревнование по программированию, приуроченное к ежегодной Международной конференции по функциональному программированию (International Conference on Functional Programming, ICFP). Вопреки названию, программировать можно на любом языке, не обязательно функциональном. Соревнование длится 72 часа, но также есть отдельный приз для тех, кто за первые сутки преуспеет больше остальных.

Основная «фишка» ICFP Programming Contest — это задачи. Они, мягко говоря, нетривиальные. Как правило, задачу придумывают академики, и корни её зачастую уходят в какую-нибудь зубодробительную область вроде оптимизационных проблем, теории алгоритмов, робототехники, орбитальной механики или чего-нибудь такого. Впрочем, за пару часов можно успеть нахвататься достаточно основ, чтобы хоть как-то поучаствовать в соревновании.

Кроме того, задачи обычно «нерешаемые», и оценки не количественные, а качественные: команда А решила задачу лучше, чем команда Б. Нередко это выливается в прямое противостояние команд (например, кто займёт больше «шахт» на карте), хотя бывают и простые гонки на то, кто дальше продвинется (например, по профилю оригами угадает, какие складки оно образует на листе).

За две недели до контеста

Так уж повелось, что незадолго до начала соревнования организаторы «разогревают» публику несколькими намёками на то, что может быть в задании. Как правило, это пара коротких твитов, которые станут понятны лишь после начала контеста.

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

Итак, за две недели до соревнования организаторы ретвитнули обращение своего знакомого учёного Ивана Зайцева, работающего на радиотелескопе в Пеговке (смотреть сто́ит ради одних только антуража и атмосферы):

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

Учёный создал страничку на ReadTheDocs (берегитесь — спойлеры!) и чат в Discord, поощряя будущих участников ICFPC работать вместе и помочь ему расшифровать послание. Народ быстро пришёл к выводу, что квадраты слева — это кодировка для чисел, показанных справа. На картинке мы видим ноль, единицу и так далее до восьми. Каждая точка внутри «квадрата» обозначает бит, и квадраты 3×3 кодируют четыре бита (диапазон чисел [3; 15]). Сразу же появилась гипотеза о том, как кодируются числа больше пятнадцати.

На следующий день было получено новое сообщение, показывавшее больше интервалов чисел. Вчерашняя гипотеза подтвердилась. Затем последовали сообщения с отрицательными числами, отношением равенства, функциями инкремента и декремента, суммы, произведения, целочисленного деления, введены понятия переменных, булевых значений и несколько отношений порядка. Всё это кульминировало тремя сообщениями, два из которых описывали конвертирование чисел из «квадратного» представления в «линейное» и обратно, а третье, непохожее на все предыдущие, выглядело как картина:

Таким образом, инопланетяне две недели описывали нам некий язык выражений, и напоследок предлагают пообщаться. Зачем всё это? Какое отношение это имеет к контесту? Согласитесь, сделать задачу продолжением тизеров было бы весьма убого и даже несколько нечестно: некоторые уже потратили две недели на «въезжание» в контекст и, таким образом, имели преимущество над вновь прибывшими.

О том, что произошло в первый день соревнования, читайте в следующем посте.