Как мы участвовали в ICFPC 2024

В этом году ICFPC, ежегодное соревнование, приуроченное к конференции по функциональному программированию, проходило с 28 июня по 1 июля. Мы с Ильей участвовали в одиннадцатый раз подряд, и это был самый интересный контест за всю нашу историю. Наша команда традиционно называлась Sunspear и писали мы на C++.

Изначально нас затянуло во всю эту движуху, когда мы начитались отчетов про 2006 и 2007 годы. Изюминка тех лет была в том, что кроме основной задачи у тебя есть еще некоторый простор для тайны, не сразу всё открыто - бери и решай, а надо разобраться в какой-то системе, которую загадали организаторы, и только тогда ты сможешь продвинуться в решении основной задачи и заработать очки. Увы, этим путем идут редко какие организаторы (они разные каждый год), и обычно дается просто формальное описание задачи, а весь контест ты придумываешь и дорабатываешь алгоритм к этой задаче. За время нашего участия только в 2020 году была попытка сделать что-то хитрее, но вышло так себе - была входная задача, которая открывала целую кучу загадок, которые объясняли, в чем собственно основная задача и как её решать. Казалось бы - идеально интересно. Но входная задача была переусложнена, причем настолько, что организаторы были вынуждены прямо в процессе соревнования давать к ней подсказки, потом - схемы алгоритмов решения, и в результате - псевдокод решения, что совершенно не добавляло энтузиазма делать что-то самим.

Но хватит истории, расскажу про 2024. Перед контестом было несколько тизеров, и они заставили моё сердечко забиться, поскольку отсылали к 2006, 2007 и 2020 годам, но я на всякий случай не давала себе радоваться. И вот всё начинается, мы открываем правила - а там никакой задачи, только описание, как общаться с неким сервером. Сеттинг в этом году такой: древнее тайное общество, которому был посвящен 2006 контест, на самом деле покинуло Землю (могу понять), и видимо процветает где-то среди звёзд, а мы получили доступ к их космическому серверу. Всё, что известно - если отправить на сервер строку S'%4}).$%8, он отвечает какой-то кашей символов.

Если точнее, то не совсем “кашей”, известно, как кодируются строки - символ а преващается в S, b в !, с в “ и т.д. Кроме этого дан целый придуманный функциональный язык программирования, назовём его Alien, программу на котором можно отправлять серверу, но пока непонятно, зачем. Я в две строчки делаю черновое перекодирование строк, чтобы можно было писать и читать на человеческом. Оказывается, команда S'%4}).$%8 - это get index, и на неё сервер отвечает длинным описанием, что это образовательный сервер с несколькими курсами, проходя которые, ты зарабатываешь очки - ага, то есть вот они, задачи. При старте доступно только два курса, а сколько их всего - неизвестно.

Первый курс называется lambdaman, и это набор двумерных карт для пакмана лямбдамена, но без призраков, только стены и таблетки, ну и сам пакман лямбдамен. Нужно отправить решение каждой карты в виде последовательности ходов вверх-вниз-влево-вправо (символы UDLR), которая позволяет съесть все таблетки. Чем меньше длина сообщения, тем лучше. Заметьте, не количество ходов, а длина сообщения. То есть если отправлять не просто строку, а как-то сжать её программой на этом их языке, будет больше очков.

Второй курс - spaceship. Есть бесконечное двумерное поле и список координат, которые нужно посетить, а управляешь ты ускорением корабля. Здесь чем меньше ходов, тем лучше, то есть сжимать вроде как не обязательно.

Прочитав все эти правила и вдохновившись, я пошла заниматься малышом, а Илья стал налаживать инфраструктуру для будущего парсера и интерпретатора Alien, пока имплементируя только строки. Часа через четыре у нас была своя консоль, которая умела отправлять строки серверу и выводить раскодированные ответы и пачка классов для будущего интерпретатора.

Дальше Илья пошёл думать над spaceship, а я сделала ошибку. У меня есть проект-заготовка именно для ICFPC, который автоматизирует прогон задачек в тредах разными решателями с занесением в базу, выбором лучших и т.п. Ведь это формат каждого прошлого года - одна задача, к которой нужно сочинить алгоритм. Увидев задачки, я решила, что пришла пора его расчехлять, хотя фактически это было совершенно неуместно - сначала я потратила кучу времени (около 3 часов), чтобы переделать его для решения разнотипных задач, а весь оставшийся контест - на поддержку работоспособности этой системы. В общем, переусложнение ради функционала, который не нужен.

Из-за этого за первую настоящую задачу я взялась только через 8 часов от начала соревнования. Мне достался lambdaman, по сути своей задача коммивояжёра: посетить все точки из списка за минимальное количество ходов. Я подумала, что для быстрого результата хватит решения “в лоб” - просто каждый ход идти к ближайшей таблетке, а улучшением результатов займемся, когда придут какие-то мысли про сжатие строк. В целом такой подход обычно оправдывает себя на ICFPC, по крайней мере в моем случае - если я начинаю мудрить, то рискую вообще никак не решить задачу за отведенное время и имеющиеся силы.

В spaceship для выбора последовательности прохождения точек Илья тоже для начала решил использовать жадный алгоритм. Само же ускорение нужно было менять так, чтобы не просто пролетать через точки, а именно быть на них в конце хода. За один ход ускорение можно менять только на +/-1 по каждой оси, так что Илье пришлось делать “кружение” вокруг точек: к примеру, если кораблю до точки было лететь по одной оси 2 хода, а по другой целых 5, то не всегда он мог так затормозиться по первой оси, чтобы оказаться в нужной точке через 5 ходов. Приходилось пролетать эту точку (часто по обоим осям) и заходить на второй круг (и больше).

Илья успел продумать этот алгоритм и пошел спать, заметив перед этим, что многие команды обгоняют нас по задаче hello - еще одна задача, очки за которую давали, когда мы просто посылали серверу допустимые команды, типа get index, get lambdaman, get scoreboard и т.д. При этом мы вроде как уже послали всё из известного, и единственная возможность - это решить get language_test, то есть проверку интерпретатора языка. Эта команда возвращает программу на языке Alien, которую, очевидно, надо выполнить, чтобы получить очки. Илья правда не верил в то, что за такое короткое время так много команд написали интерпретатор Alien, но потом оказалось, что это правда.

Я дописала lambdaman, и оказалось, что несколько задач не решаются, поскольку карты для них сервер отправляет в виде Alien программы, которую мы не умеем пока выполнять. Тем не менее, первые очки по задаче я заработала, подняв нас на 133 место (не густо), и тут бы идти спать, но мне не давала покоя задача hello. Я с полчаса подбирала разные команды в надежде найти что-то, что мы упустили, а все остальные нет, и уверилась в мысли, что все просто написали интерпретатор. Я решила его начать, вдруг это действительно быстро, и мы сможем получше выступить на lightning division (отсечка по очкам за первые 24 из 72 часов соревнования). Однако мой мозг совершенно отказывался воспринимать парадигмы функционального программирования, и пришлось потратить несколько часов, изучая, что это и как это. Уложив наконец в голове, как всё это должно работать, я пошла ~~спать~~ будить малыша, и лишь отправив его с бабушками на прогулку, добралась до кровати в полубессознательном состоянии. О том, чтобы закончить интерпретатор к lightning division, речи уже не шло.

Пока я спала, Илья доделал spaceship, тем самым позволив нам войти в первую сотню в lightning division. Было бы ещё больше очков, но несколько задач Илья не успел решить, поскольку неоптимально хранил данные и зависал - он починил этот баг всего через час после lightning division, обидно. Со spaceship тоже оказалось всё не просто - во-первых, одна карта была в виде программы на Alien, во-вторых, несколько последних задач имели настолько большое решение, что его не принимал сервер (было ограничение в 1 мегабайт на текст решения одной задачи), то есть их тоже нужно отправлять не в сыром виде, а программой на Alien, чего мы пока не умели.

После отправки части решений spaceship нам открылся третий курс - 3d, и это что-то с чем-то! 3d, как вы правильно догадались, означает three-dimensional, но вот какой нюанс: третье измерение - это не пространство, а время. Есть двумерное поле, на котором можно располагать клеточки входных значений, клеточки результата, арифметические операторы, операторы сравнения и операторы перемещения (но нет операторов сравнения на “больше” и “меньше”). У каждого оператора есть входы и выходы, например, оператор сложения берет два аргумента слева и сверху от себя, складывает, и на следующий ход результат кладет направо и вниз, а аргументы со входа исчезают. Оператор перемещения, как следует из названия, перемещает свой вход в выход, при этом аргументом не обязано быть число, он может перемещать и другие операторы… ох уж это функциональное программирование! И наконец, есть оператор прыжка во времени, который перемещает входное значение в клетку по заданным относительным координатам в пространстве и времени. Причем с помощью нескольких таких операторов можно отправлять несколько значений в прошлое, но нужно следить, чтобы все они прыгали синхронно в одну точку времени, иначе программа считается некорректной.

Критерий оценки - объём программы в пространстве/времени. То есть, чем меньшую занимает площадь решение и чем короче время цикла до прыжка во времени, тем лучше. Это совершенно взрывает мозг, потому что выходит, что супер-эффективно использовать циклы. Например, чтобы найти максимальное из двух чисел (известен их диапазон), нужно во временном цикле увеличивать каждое из них на 1, пока какое-нибудь не достигнет максимума. Очень непривычно думать в таких терминах.

На этом языке нужно было составить решение для 12 задачек, от простых (найти факториал числа, взять модуль, найти максимальное из двух чисел и т.п.) до сложных (найти синус; проверить, что в закодированной числом строке, состоящей из кучи открывающихся и закрывающихся скобочек, скобочки расставлены правильно).

Илья с упоением взялся за этот курс, потратив на него всё оставшееся время соревнования. Идею писать графический интерфейс для составления решений вручную он отбросил - не факт, что это окупилось бы. Даже просчет ходов, который он написал для отладки готовых решений, в целом можно было бы не делать - лучшим инструментом оказался конструктор LEGO Duplo с наклеечками.

Я же пошла воевать с интерпретатором Alien, проходя несколько раз в цикле стадии “всё понятно, работаем” и “господи, я вообще не понимаю, как это должно работать”. “Что же там такого сложного?”, спросите вы. Ну в принципе когда концепцию понял, уже ничего, за исключением того, что надо заставить мозг развернуться странным, каким-то неестественным образом, и думать не в терминах объектов и функций над ними, а только лишь функций, которые даже не знают, с чем из “реального мира” они работают (со строками там, или может числами), в основном они вызывают своё тело (другую функцию) с каким-то аргументом, который тоже скорее всего функция, и только где-нибудь глубоко в этой цепочке происходит настоящее действие - конкатенация строк, умножение, сравнение и т.д. Поэтому отладка была непростой: чтобы найти, что где-то что-то идёт не так, нужно вручную по пунктам проверить, как всё должно работать, а это долго, муторно и неприятно. Мрачности мне добавляли мысли, что проклятые функциональщики наверняка за 20 минут написали конвертер кода Alien в какой-нибудь Haskell и вообще в ус не дуют, а я вынуждена страдать.

Наконец программа language_test репортует: “вы прошли проверку! чтобы получить очки, отправьте на сервер команду language_test некоторое число” - я ликую, но рано - сервер не принимает результат. Эндорфины не дают всё бросить, и я из последних сил снова иду чинить баги. Оказывается, при операциях над int происходит переполнение, 32 бит не хватает. Заменяю на int64 (позже я перейду на int бесконечной длины), успех! Любопытно, что language_test я победила ровно через минуту после экватора соревнования, догнав остальные команды по задаче hello. Как перестать бояться и полюбить функциональное программирование.

Вспоминаю, что теперь можно раскодировать задачки, которые сервер прислал на языке Alien, и получить за них очки, но не тут то было - мой интерпретатор ломается о каждую из них, кроме единственной spaceship. Отправляю хотя бы её. Вместе с language_test это поднимает нас в рейтинге всего на 14 пунктов, и мы всё равно стоим ниже результата lightning division - значит, остальные команды работают лучше. Иду спать роскошные 6 часов.

Наступают последние сутки соревнования. Расправившись с бытовыми делами и малышом, выгребаю последние баги в интерпретаторе и решаю все задачи lambdaman, кроме последней, она наглухо зависает. Очень долго и внимательно вглядываюсь в её код, пытаясь понять, что к чему. Илья поднимает вопрос, имеет ли смысл тратить на неё время, и мы решаем, что лучше приложить усилия в другом направлении. Организаторы в какой-то момент открыли доступ всем командам ко всем курсам, и нам доступен новый курс - efficiency. Иду туда в надежде на что-то новое, но там пачка задачек-программ на Alien, каждая из которых возвращает некоторое число, которое требуется прислать на сервер в качестве решения. И ни одна из них не решается моим интерпретатором, просто наглухо зависает, как и lambdaman21.

Смотрю своим уже опытным глазом на первую из них и понимаю, что это всего лишь программа вида f(f(1)) и так 20 с чем-то вложенных f, где f(x) = x + x + x + x. То есть программа возвращает значение (4x)N, где N - глубина вложенности. Почему же всё зависает? Ведь даже шестиклассник сможет вручную посчитать результат для x = 1 и N = 20, хоть и не быстро. Оказалось, дело в ленивых вычислениях: в обычной программе мы бы решали эту задачу с конца, то есть сначала вычислили бы f(1) = 4, результат бы подставили в следующий f(4) = 16 и так далее до самого верха стека, всего 20 вызовов функции, а здесь же мы вынуждены идти сверху вниз, и вот что выходит. Мы берем самый первый вызов f с аргументом из остальных вложенных 19 f, и подставляем этот аргумент в функцию, не вычисляя его (ленивые вычисления-я-а-а), получается 19 f + 19 f + 19 f + 19 f. Пытаемся вычислить первое слагаемое, это f от восемнадцати вложенных f, подставляем аргумент, получаем 18 f + 18 f + 18 f + 19 f + 19 f + 19 f. Нетрудно догадаться, что в результате мы находим (4x)N как сумму из одного с копейками триллиона единичек, причем ладно бы нужно было триллион раз выполнить сложение, на каждое такое сложение приходится куча операций по изменению дерева выполняемой программы. Безумие 🙂

В описании курса efficiency любезно оставлена подсказка, что кроме call-by-name стратегии подстановки аргументов в функцию (когда мы буквально копируем аргумент во все места использования и вычисляем его каждый раз независимо), бывает еще call-by-need, который делает то же самое, но с кешированием: если подставленный аргумент хоть раз был вычислен с определенными входами, он больше не будет вычисляться от них же, а вернется сохраненное значение. Всё просто и логично, подумала я, и пошла реализовывать. Через полчаса поняла, что всё совершенно не просто, и что на самом деле я ничего не поняла. Совершенно уставший мозг отказывался думать, мысли блуждали по кругу. Пошла спать, но уснуть не смогла. Открыла следующие задачи из efficiency, и узнала в них знакомый паттерн, как в lambdaman21, с которым я так до конца не разобралась, решила снова к ней вернуться.

Почахнув над кодом lambdaman21, я поняла, что это цикл на Alien. В языке Alien нет готовой инструкции для цикла, но с помощью трёх лямбд, if и такой-то матери можно его сделать, что и продемонстрировали нам организаторы. В 21 задаче цикл бежит от какого-то ооочень большого (12210-разрядного) числа до 0, находит остаток от деления его на 4, в зависимости от результата добавляет один из четырех захардкоженых символов в некую строку (которая и является результатом выполнения программы), и дальше делит число на 4. Батюшки, да это же алгоритм разжатия Alien int в строку, состоящую из 4 разных символов, именно то, что требуется мне для сжатия задач lambdaman! Редактирую вручную Alien код разжатия под мои нужды, пишу сжатие на C++, загружаю новые результаты, Илья параллельно загружает ручное решение первых трёх задач 3d. Наконец-то поднимаемся со 129 места, куда успели укатиться, на 67. До конца соревнования 8 часов, по идее нужно немного поспать и сделать финальный рывок, но сон не идет.

Трачу часа 4 на попытки осознать call-by-need стратегию и сделать кеширование, даже как будто понимаю, реализую идею, но она не работает. Сил на отладку нет, бросаю. Илья периодически приносит очередное решение 3d, позволяя нам не терять место. Суммарно он решил еще 3 задачи. Я беру пример и тоже вручную решаю несколько первых задач efficiency, пока они не очень разрастаются по размеру. В какой-то момент понимаю, что вообще-то lambdaman21 я тоже полностью поняла, просто мой интерпретатор не может его вычислить (по той же причине, что и efficiency), а вот C++ может 🙂 Перевожу код lambdaman21 из Alien в C++, получаю наконец-то карту задачи! Решаю её своим не самым умным алгоритмом, и шагаю лишь на пару мест вверх - подумать только, все вокруг её тоже решили.

На что-то крупное уже сил нет, и до конца соревнования остается минут 40. Можно было бы к примеру попытаться сжать последние задачи spaceship, чтобы получить за них хоть какие-то очки, но мы понимаем, что просто не в состоянии это сейчас сделать. На этом мы с Ильей жмём друг другу руки и ICFPC для нас заканчивается. Мы заняли 64 место из 470 зарегистрированных команд, правда хоть что-то сделали лишь 250 из них. Не самый впечатляющий результат, но я не могу сказать, что где-то мы кардинально приняли неверное решение и потеряли много времени. Но все равно в будущие годы надо заставлять себя перед тем, как бежать решать/приделывать/придумывать что-то, сначала остановиться и подумать - а точно ли оно нужно?

Это был отличный контест в плане организации: простые описания задач на одном экране, широкий спектр возможностей приложить усилия и получить очки, грамотно продуманное прохождение - организаторы правильно оценили сколько на какие подзадачи должно уйти времени, расставили задачи в правильном порядке, где нужно дали подсказки, где не нужно - промолчали. Никаких тягомотных и скучных обвязок для обмена с сервером, никаких json-ов, только чистое удовольствие от решения задач и разглядывания глазами кода Alien 🙂 Посмотрим, что нас ждет в следующем году.