Это вторая часть моей серии отчётов об ICFPC 2020. Остальные части ищите здесь:

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

Флешбэк: сбор команды

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

Мне удалось. В этом году Цодингтим представляли аж восемь человек — четыре «старожила» и четыре «новичка»:

1. Akon32, для которого это был уже четвёртый контест;
2. ForNeVeR, тоже выступавший далеко не впервые;
3. IngvarJackal, который не знает Haskell и собирался помогать советами;
4. mr146, коллега ForNeVeR-а, имеющий богатый опыт в куче других соревнований, но ещё не игравший в ICFPC;
5. pink-snow, тоже никогда не игравший в ICFPC, но уже здорово вложившийся в разгадку тизеров;
6. portnov, известный вам по моим предыдущим отчётам;
7. unclechu, единственный из всей команды пишущий на Haskell за деньги, но никогда не игравший в ICFPC;
8. я.

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

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

17-е июля, пятница, T+00:00. Старт

Нажимаем F5, и сайт организаторов генерирует мемасик (выделение моё):

Starts a few seconds ago on July 17, 2020 @ 13:00 UTC

А задания нет. Ну, ладно, нам не впервой — в былые годы сайт организаторов вообще ложился под наплывом интересующихся. Просто жмём F5.

T+00:05. Радиоастроном Иван Зайцев публикует очередной пост, мол, пришла целая пачка сообщений, помогайте расшифровывать. Оказалось, что организаторы ещё 25 минут назад твитнули, что отказываются от своей задачи в пользу Пеговки. А Пеговка призывает скооперироваться в Дискорде и понять, чего от нас хотят инопланетяне.

Настроение в командном чате обескураженное и подавленное:

<xxx> Сорян, а где код-то писать нужно?
<xxx> Кажется, тут просто какая-то угадайка? Или не?
<yyy> xxx: код можно писать для того, чтобы упростить декодирование. Но, похоже, пока что контест состоит в том, чтобы апдейтить сайт на readthedocs
<xxx> И кто выиграет в таком соцсоревновании?
<zzz> Иван Зайцев!

ICFPC, конечно, непредсказуем, но у команд все равно формируются некие ожидания. Будет задача. Она будет непомерно сложной, быть может, в принципе не решаемой ни за какое время, не говоря уж о 72-х часах. Команды будут соревноваться, и многие должны будут проиграть, чтобы единицы могли победить.

Организаторы же сломали все ожидания. Вместо задачи — рекомендация разобраться, в чём состоит задание. О сложности не известно ничего. Команды должны работать вместе, а не соревноваться. Всё это настолько сильно шло вразрез с предыдущими ICFPC, что я растерял весь запал, скопившийся за год ожидания.

Просто сидел и злился. Если бы я играл один, на этом месте я бы сдался.

Но со мной была команда, и никто другой не ушёл. Спустя 45 минут мне немного полегчало, товарищи тоже сбросили с себя оковы первого впечатления, и мы взялись за дело. mr146 погрузился в декодирование новых сообщений, записывая мысли в гуглодок. Я взялся помогать, но нелюбовь к загадкам взяла своё, и я переключился на другую задачку.

pink-snow обнаружил, что за тестовый сабмишен выдают один балл. Надо заметить, что система сабмишенов пока что никак не вязалась с заданием: она ожидала POST-запроса по адресу и с параметром, указанными в командной строке. В ответ нам возвращали тот же параметр. Отказываясь верить в то, что задание ограничено разгадыванием сообщений, я трачу время на эксперименты с API: шлю туда 42, потом случайные числа, потом большие случайные числа. В ответ всегда приходит то, что было отправлено.

<я> xxx: рандомное чиселко уже 6 минут тестируется
<xxx> минору сломал пришельцев случайным числом
<xxx> межпланетарный дипломатический конфликт получился

Спустя полтора часа организаторы публикуют очередной пост, где сообщают, что Зайцев принимает некое огромное сообщение. Тем временем Портнов с N-ой попытки таки доносит мысль, что пора писать код. Из дешифрованных сообщений понятно, что перед нами некий «космолисп» — как бы Лисп, но вместо скобочек польская запись и оператор частичного применения. К примеру, вот так записывается список двух элементов [1, 2]:

ap ap cons 1 cons 2 nil

Также в «космолиспе» есть арифметика, комбинаторы SKI и целый ряд функций ввода-вывода: некоторые рисуют картинки, другие что-то отправляют инопланетянам и возвращают ответ. После короткого обсуждения становится понятно, что выражения легко разбираются в бинарное дерево, где ap являются узлами, а все остальные токены — листьями. Я сажусь писать функцию reduce, «редуцирующую» любое выражение в как можно меньшее.

Тем временем прошло уже четыре часа с начала контеста. ForNeVeR, начитавшись расшифровок сообщений, отправляется спать, а организаторы наконец-то публикуют соломинку, связывающую «загадки» с HTTP API: Swagger-документ описывает, как можно отправить инопланетянам сообщение и получить ответ. Становится очевидно, что пятнадцатое сообщение, описывающее команду send, напрямую мапится в это API. unclechu отправляется писать биндинги.

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

Очевидно, что нам нужно как можно скорее запустить galaxy и понять, чего от нас хотят инопланетяне. Рождается несколько идей:

1. навалиться всем вместе и довести функцию reduce до рабочего состояния, реализовав всё необходимое для вычисления galaxy;

2. оттранслировать galaxy.txt в какой-нибудь «настоящий» Лисп, например, Scheme, и выполнить;

3. оттранслировать galaxy.txt в Haskell и выполнить.

Тут наконец-то «выстреливает» тот факт, что у нас большая команда: мы выбираем все опции сразу. mr146 и я занимаемся reduce, pink-snow берётся за трансляцию в Haskell, а portnov — в Racket. Спустя пару часов последние две идеи отпадают: GHC не осиливает вывести типы рекурсивных функций, а Racket считает, что все функции в galaxy.txt не принимают аргументов, и отказывается что-либо вычислять. Высказав напоследок идею о том, как это исправить, Портнов отправляется спать.

pink-snow берётся думать, как поверх ещё не дописанной reduce сделать функцию, которая вычисляла бы galaxy. Дело в том, что сама galaxy ничего толком не делает, она просто вызывает вспомогательную функцию, которая вызывает другие, и так для графа из 1338-и функций. reduce умеет упрощать только отдельные выражения, но не умеет подставлять в них тела других функций. Почему-то никому не приходит в голову просто расширить reduce, чтобы она покрывала и вызовы функций тоже. Вместо этого я убеждаю pink-snow написать цикл, в котором дерево будет сначала упрощаться с помощью reduce, а затем в него будут подставляться все константы — и так до тех пор, пока дерево меняется. Эта моя глупость нам ещё аукнется…

Пока pink-snow думает, мы с mr146 реализуем в reduce все используемые в galaxy функции, кроме рисования картинок и отправки HTTP запроса. Биндинги к HTTP ещё не готовы, поэтому я ухожу спать, оставив соратникам моё видение задач на следующий день:

1. объединив HTTP-биндинги от unclechu с функцией от pink-snow, получить полноценную «вычислялку» выражений;
2. протестировать её на нескольких сообщениях, результат которых нам известен заранее;
3. запустить наконец galaxy.txt.

Послушают ли меня коллеги? Удастся ли нам реализовать задуманное? Успеем ли мы — впервые в нашей истории! — что-то отправить на lightning round? Читайте в следующем посте :)