ICFPC 2026

Снова лето, снова ICFPC! Это соревнование по программированию с «жизненными» задачами, то есть не сводящимися к какому-то одному алгоритму. Часто посреди контеста приходят «правки» с усложнениями, что тоже прибавляет реализма. ICFPC длится три дня, обычно с обеда пятницы до обеда понедельника. Так было и в этот раз.

Я традиционно взял под это дело отпуск и участвовал с ребятами из codingteam. Состав в последние годы остаётся неизменным: Akon32, ForNeVeR, foxtran, gsomix, portnov и я. Из-за проблем с доступом к сайту я потерял часть пятницы, а Портнов не смог участвовать вовсе.

Задание в этом году заключалось в том, чтобы писать разные алгоритмы на своеобразном 2D-ассемблере. Программа состоит из комнат, соединённых коридорами. В каждой комнате находится человечек, у него есть три регистра памяти для целых чисел. Двигаясь по комнате, он читает расположенные на полу инструкции, влияющие на регистры и направление движения. Коридоры служат для передачи информации между комнатами. Для чтения ввода нужно подключиться к комнате I и получать от неё значения, для вывода — отправлять значения в комнату O. Программа выглядит так:

+-+>v   
|I|+---+
+-+|s@U|
   |/ M|
 v<|W *|
+-+|2 +|
|O||^M<|
+-++---+

Организаторы заботливо предоставили онлайн-редактор с подсветкой синтаксиса; в нём эта программа выглядит гораздо понятнее:

Это наше решение первой задачи, в которой требовалось вывести \(n\)-е треугольное число, то есть сумму \(1 + 2 + \cdots + n\). Видно комнаты I и O, коридоры (<, > и v), а в основной комнате видно человечка @ (который изначально движется вправо) и всякие операции:

• U читает значение из комнаты I и поворачивает человечка в сторону, противоположную использованному коридору, в данном случае — вниз;
• M и W перекладывают числа между регистрами;
• +, * и / — арифметика;
• < и ^ меняют направление движения человечка;
• 2 — записывает двойку в основной регистр человечка;
• s отправляет значение в комнату O.

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

Итак, в пятницу я пободался с доступом к сайту, прочитал textbook и первые задачи, а потом сразу отвлёкся на отцовские дела.

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

Начал с простого — ячейки на одно значение:

В процессе работы над этой маленькой программкой я приуныл окончательно. Совершенно не хотелось провести в онлайн-редакторе все три дня. Грустный, пошёл заниматься домашними делами.

Суббота началась с головной боли и отсутствия интереса к задаче. Прогулка под дождём немного меня взбодрила, поэтому к обеду я снова оказался за компьютером.

Чуток повозился с (неудачной) оптимизацией нашего решения треугольных чисел, и тут пришёл Он. Спаситель. Свет наш Форневерушка. Он принёс Идею: написать оптимизатор расположения комнат и коридоров. Решения оценивались не только по скорости выполнения, но ещё и по размеру — между шириной и высотой решения выбирается наибольшее и возводится в квадрат. Значит, решение надо вписывать в квадратное поле наименьшего размера.

Надо заметить, что из-за отсутствия Портнова и интереса к задаче мы впервые за все годы соревнований не взялись писать типы и парсеры в первый же час. Обычно за это принимается Портнов, и к моменту, когда остальные дочитали условие и зафлудили чат первыми идеями, он уже что-то пушит. В этот же раз спустя 24 часа после начала у нас не было ни единой строчки кода.

Поэтому я быстренько договорился с Форневером о типах данных, он пошёл читать про разводку электрических схем, а я занялся парсером. Типы для коридоров затем пришлось переделывать дважды. Во-первых, я не учёл, что коридоры могут быть извилистыми и их нельзя представить одними только координатами входа и выхода. Во-вторых, нужно хранить ещё и направления входа и выхода, т.к. без этого в плотной раскладке невозможно понять, с какой именно комнатой соединён коридор. Короче, за типы данных мне троечка с натяжкой.

Парсить нечто похожее на ASCII-арт оказалось сложнее, чем я думал. Традиционные для Хаскеля парсер-комбинаторы тут не подходят; во всяком случае, я не придумал, как их применить. Готовых библиотек тоже не нашлось. Встречал штуки, умеющие парсить конкретный тип ASCII-арта с целью превратить его в SVG, но более универсальных парсеров найти не удалось. Значит, надо писать свой.

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

Дальше я занялся собственно разбором и удалением комнат. В последние годы соревнований я пришёл к выводу, что юнит-тесты окупаются даже если на всё про всё есть лишь три дня; поэтому я сразу подтянул tasty и принялся обкладывать будущий код проверками.

Непозволительно много времени было потрачено на двумерные массивы. repa и hmatrix сходу показались сложными, поэтому я написал свою собственную реализацию поверх vector. Естественно, кое-где перепутал местами индексы и потерял время на отладку. Надо бы на будущее освоить hmatrix.

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

У меня был код, находящий верхнюю левую непустую клетку; в данном случае это была бы > в третьем столбце второй строки. Бежать от неё по направлению коридора легко: видим >, бежим вправо, находим v, бежим вниз, после > поворачиваем вправо, после ^ — вверх, а там дальше пустая ячейка, то есть это конец коридора. А вот как от > добраться ко входу? По одной только ячейке невозможно понять, с какого направления в неё приходят. Значит, надо оглядываться, находить |, делать вывод о том, что надо двигаться вниз, добегать до ^ и там опять разбираться, что к чему. Сложно!

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

Написание парсера принесло мне море удовольствия; единственный минус состоял в том, что работа была закончена лишь вечером воскресенья. Форневер к тому времени уже что-то накидал напополам с нейронкой, поэтому я сдал парсер ему, а сам пошёл смотреть на наши успехи.

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

ллмщики: всё плохо, пока что успел сделать только багованный движок на ссишке и неоптимально решить все задачи первых трёх семестров

ручные кодеры: я красавчик, я осилил индексирование двумерного массива!

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

Настал понедельник — последний день соревнования, к тому же короткий, до обеда. Форневер в воскресенье показал неутешительные результаты оптимизатора, превращавшего вот такую красоту:

…в вот это:

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

Поиграв с коэффициентами алгоритмов, я смог немного обуздать «пессимизацию», но окончательно побороть её не удалось. Решив погонять оптимизатор на других задачах, я пошёл смотреть наши лучшие решения и обнаружил, что они и так уже отлично упакованы! Выходит, что парсер и оптимизатор мы делали зря ☹

В наших решениях оставался потенциал для оптимизации самих комнат — в некоторых было очень много свободного пространства:

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

Если проигнорировать ограничения, то это какой-то полный перебор, а если делать полноценно, то что-то сложное и непонятное. Примерно за час до окончания контеста я решил, что уже ничего не придумаю и не сделаю, и пошёл обедать. Сокомандники же до последнего руками оптимизировали решения; gsomix сабмитил даже в самую последнюю минуту.

Контест оставил о себе двоякое впечатление. Удачные задания на ICFPC всегда сильно крупнее отведённых им трёх дней; в этом плане этот год очень удачный. Но из-за недостатка то ли знаний о компиляторах и логических схемах, то ли ресурса, задача этого года показалась чересчур крупной. Относительно большой набор команд, 2D, правила соединения коридоров с комнатами, правила выбора коридора при отправке/получении данных — все эти усложнения мешали заняться собственно генерацией программ.

Онлайн-редактор с одной стороны понижал порог входа и давал возможность с первых минут «пощупать задачу руками», а с другой — сильно поднимал порог входа для автоматизированных решений и поэтому мешал над ними работать.

Мне удалось два дня подряд с упоением программировать, но никакой коллаборации над кодом не было. Я что-то там накодил в своём болотце, перекинул через забор Форневеру, он скомбинировал со своим, и всё. Остальная команда в это время либо решала задачи руками, либо изобретала свой собственный 2D-компилятор на Фортране. Да, была коллаборация над решениями, я что-то за кем-то оптимизировал, но особого удовольствия от этой деятельности не получил.

На момент заморозки лидерборда мы занимали 48-е место из 267-и. Наш код можно посмотреть у нас на гитхабе.

Такие вот у меня впечатления. Почитайте ещё пост Форневера, там более подробно рассказано про команду в целом. И раз вы сюда дочитали, надеюсь увидеть вас в leaderboard следующего ICFPC ☺