Каждый год в конце июля мы с друзьями берём отпуска и на три дня погружаемся в безбашенную задачу, стараясь победить, наконец, в ICFP Programming Contest. Не стал исключением и 2018-й.

В этот раз команда состояла из Akon32, ForNeVeR, portnov, ulidtko и меня. По сложившейся за последние годы очерёдности, код писали на Haskell.

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

В итоге задача оказалось о программировании футуристичных 3D-принтеров. Печать в них выполняется с помощью нанороботов, а висящие части модели поддерживаются энергетическим полем. Изначально робот всего один, но путём почкования можно получить ещё 39.

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

Видео начинается примерно с третьего шага программы, где нанороботов уже два. Светло-серая подложка показывает, что модель поддерживается энергополем. Как видите, эффективностью наше решение не блещет :(

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

Вечер пятницы

Соревнование началось в 16:00 UTC, и первые полчаса ушли на чтение задания и преодоление первичного шока. Как обычно, у Портнова нашлась подходящая цитата: «мы знаем, что эта задача не имеет решения; нам интересно как её решать!»

Первым делом нам нужно было научиться читать входные файлы с описаниями фигур. Решили сразу оптимизировать представление в памяти и хранить фигуру как битовый массив, где каждый бит показывает, заполнена ячейка пространства или нет. Очень здравая мысль, но спустя сутки все равно пришлось выяснять, отчего это у нас решалка не умещается в 16 гигов RAM и треть времени проводит за обновлением этого самого массива.

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

1. собирать послойно, но на каждом слое двигаться только в пределах bounding rectangle этого конкретного слоя, экономя таким образом время;

2. включать энергетическое поле только если заполняется никак не закреплённая клетка.

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

Я, чтобы не терять время совсем уж впустую, принялся разглядывать все подряд модели в надежде почерпнуть из них знания про corner cases и, возможно, как-то классифицировать проблемы. О том, что по окончании lightning-раунда модели наверняка поменяются, я не подумал. Впрочем, мне повезло и в полном раунде фигуры были примерно те же.

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

Суббота

Проснувшись сильно позже запланированного, я обнаружил, что Akon32 уже написал скрипт для подготовки архивов с решениями, Портнов занят алгоритмом послойной сборки с движением в bounding rect слоя, а ForNeVeR пытается придумать что-нибудь похитрее. Оказалось также, что проснувшийся посреди ночи ulidtko написал кусок движка, но до рабочего состояния пока не довёл. Через десяток минут появился лидерборд, до конца lightning-раунда оставалось 7 часов, и я быстренько нашёл себе очередную задачу.

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

Спустя пару часов проснулся ulidtko и попытался убедить нас перевести движок на свободные монады, чтобы не так сильно страдать от (неизбежных на ICFPC) изменений условий. Не встретив особого энтузиазма, он ушёл работать дальше.

В T+21:34 Порнов получил наконец первые решения, а спустя час был готов первый сабмишен, но мы почему-то решили повременить с его отправкой. В итоге за 4 минуты до окончания lightning-раунда обнаружилось, что файлы решений названы неправильно; ещё девять минут ушло на перепаковку-перезаливку-ресабмит, к тому же ошиблись с контрольной суммой…

Короче говоря, в lightning мы так и не поучаствовали.

Начался «полный раунд» соревнования. Пришло обновление задания: появились команды по удалению материи и работе с целыми слоями и областями пространства, а количество роботов увеличилось до 40 (в lightning было 20). Соответственно поменялся и набор задач: теперь помимо сборки нужно было также разбирать и даже пересобирать уже существующие фигуры. Например, нам предлагалось превратить корабль класса Constitution в Galaxy:

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

Первым делом нужно было добавить новые команды в AST, чем я и занялся. Параллельно поставил считаться задачки для очередного сабмишена. Портнов в это время занялся профилировкой солвера: тот не умещался в память уже на 90-й задаче (из 186-и) и тратил кучу времени на обновление битового массива. ForNeVeR продолжал бодаться с Haskell и тестами.

Закончив с новыми командами, я взялся писать алгоритм для проверки «заземлённости» клеток пространства. По условию, клетка не нуждается в поддержке энергетическим полем, если существует путь по заполненным клеткам от неё к «подложке», на которой строится фигура. Первая версия солвера отслеживала, какие клетки заземлены, а какие нет, но не распознавала ситуаций, когда вновь заполненная клетка соединяет заземлённую часть фигуры с незаземлённой. Из-за этого поле могло единожды включиться где-то в начале печати и не выключаться до самого окончания.

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

В воскресенье

…меня ожидало разочарование: рекурсивный алгоритм оказался багованный, признавая клетки незаземлёнными даже когда очевидно, что это не так. Я снова поздно проснулся, уже почти обед, голова еле варит, а тут ещё эти баги, блокирующие работу коллег!

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

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

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

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

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

…который на самом деле просто кучка шпал:

Но в итоге к вечеру закончил и получил 25% экономии энергии на некоторых задачах. Правда, Портнов тем временем реализовал заполнение линий с помощью двух ботов и получил экономию в разы… Потом оказалось, что его стратегия лучше всего работает, когда в линии нет пробелов, поэтому наши подходы удалось объединить. Собственно, видео в начале поста демонстрирует совместную работу этих двух стратегий.

Перед уходом Akon32 и ForNeVeR написали в трекере длинные посты о том, что делали и на чём остановились. Наступила ночь, и все разошлись спать.

В понедельник

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

Повозившись немного с массивами в Bash, я перешёл на Perl. Обнаружил, что забыл про этот язык примерно всё, но отступать было уже некуда. Во время финального, как мне казалось, теста, скрипт полчаса разгребал решения, выбирая лучшие, а потом удалил их. Запастись гигабайтами в /tmp было проще, чем отлаживать прочие такие сюрпризы — на часах уже T+67, 5 часов до конца контеста — поэтому я просто удалил из кода все вызовы rm.

План-минимум на остаток дня заключался в том, чтобы:

1. доделать солвер задач на разборку, чтобы он удалял по три клетки сразу (как сборщик);
2. поправить алгоритм, «зигзагом» проходящийся по слою, чтобы в случае «пробелов» в слое бот не метался лишний раз из угла в угол.

Портнов в это время работал над ускоренным заполнением уже не строк, а целых прямоугольников.

Параллельно со всеми этими работами нам нужно было слить все предыдущие решения в один архив, для чего мы с Портновым устроили map-reduce: половину архивов мержил я, а половину он.

Солвер на всех задачах работал примерно час, на мерж двух архивов уходило 20 минут. Рассчитали дедлайн, после которого уже бесполезно что-либо пилить, т.к. все равно посчитаться не успеет. До него оставалось три часа, и мы дружно принялись за работу.

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

Тут мне не придумалось ничего лучше, кроме как старый добрый A*. К моменту наступления дедлайна удалось достичь феноменального — алгоритм был неспособен пройти 9 клеток по прямой:

icfpc2018-exe: Can’t find path from (17,1,12) to (8,1,12)

Что-либо делать было уже бесполезно, но дожидаться конца контеста сложа руки было решительно невозможно, поэтому я продолжил возню с A*.

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

Памятуя об ошибке, которую мы допустили в lightning-раунде, скачал архив, посчитал хеш… Не сходится! T+71:53, решительно непонятно, где напортачил, перепроверяю хеш оригинального архива и обнаруживаю, что залил совершенно другой файл. Снова молниеносные клики в браузере, копирование ссылок и хешей, сабмит… Фух! T+71:55, архив отправлен. На всякий случай уже в более спокойном темпе отправляю его же, аккуратно проверяя, что скопировал именно те ссылки и именно тот хеш.

В T+72:04 пришло подтверждение, что финальный сабмишен принят. Радостно отчитываюсь об этом в командный чатик и снова начинаю дышать.

Теперь нужно было дождаться сентября, когда во время ICFP организаторы объявят победителей.

Рефлексия

Зря откладывали первые сабмишены. Следовало бы сразу написать для этого скрипты и для проверки отправить «дефолтные» решения, полученные от организаторов. В этом году был реальный шанс попасть в lightning, а мы его проворонили.

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

Личное: распорядок дня должен быть жёстким. В этом году я что-то расслабился и просыпался позже, чем планировал, что не могло не сказываться на качестве работы.

Результат

Наше путешествие по лидерборду выглядело так:

В итоге мы заняли 67 место из 107 команд; это лучше нашего среднего (если считать 2016-й удачной случайностью ☺).

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

P.S. Извините, что настолько задержал с отчётом. Практически весь его я успел написать сразу же после соревнования, но хотелось ещё немного вылизать текст; я отложил его на несколько дней, потом до выходных, потом на следующие выходные… Сейчас, перед публикацией, уже ничего не правил: впечатления давно улеглись, и мне уже нечего сюда добавить. Пожалуй, это тоже часть рефлексии: публиковать отчёты нужно сразу, по горячим следам, иначе ничего, кроме хронологии, в них не попадёт.