не могу понять, что делать с зацикливанием. Это как шизофрения и гениальность. Уберешь одно, второе пропадет

Неделя после окончания контеста. Все, включая автора этих строк, выспались и успели вернуться к жизни. Однако надо всё таки рассказать, как прошли последние сутки ICFPC. Если кратко, то были две интересные вещи: блокчейн и постпроцессор.

О блокчейне. После окончания 24-часового раунда организаторы дополнили правила и предложили командам соревноваться между собой. Старожилам моментально понравилось — от этого веяло духом лампового ICFPC 2017 года, где нужно было разгибать оригами и загибать оригами позаковыристее для других команд. А здесь было нужно за короткое время решать привычные задания на покраску карты роботами, а также генерировать новые карты для других команд. Одно из таких заданий, выбранное случайно из 10 лучших, попадало в новый блок блокчейна и всё повторялось. Наш генератор заданий предлагал соперникам вот такие гармоничные карты:

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

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

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

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

Принцип работы постпроцессора прост как палка: взять решение, сгенерированное другим алгоритмом, разбить на части и переставить их в более оптимальном порядке, выкидывая ненужные ходы. Вот как это работает на мелкой карте № 42 (999 → 907 ходов, –9 %):

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

Так мы и закончили контест, медленно опустившись к началу «заморозки» лидерборда до 11 места (https://icfpcontest2019.github.io/rankings/), но надеясь, что сделанные в последние 6 часов улучшения вернут нас в группу лидеров.

А что мы делали после контеста? Всё как обычно:

1. Выложили код на GitHub (в этот раз 8 тысяч строк на C# вместо 11 тысяч в прошлом году). Написали подробный README с описанием стратегий и вклада разных участников команды: https://github.com/kontur-contests/icfpc2019-tech-kontur-ru/blob/master/README.md

2. Сложили все фоточки с контеста в один альбом (https://photos.app.goo.gl/qFYHWX6UvdBvsjVn6), обновили страничку ICFPC на сайте (https://tech.kontur.ru/contests/icfpc)

3. Почитали обещанный пост Вероники @Aminopyrodin про пользу от фронтендера на ICFPC, борьбу со ScalaJS и «лучшие цитаты контеста» (https://telegra.ph/Frontender-na-ICFP-Contest-2019-07-02)

4. Заглянули на Reddit, почитали отчёты других команд (https://www.reddit.com/r/icfpcontest/). Заглянули в твиттер, почитали отчёт Никиты Прокопова, участвовавшего в первый раз (https://tonsky.livejournal.com/322258.html)

5. В качестве обязательного ритуала почитали код в репозитории японской команды Unagi, неоднократного победителя ICFPC (https://github.com/imos/icfpc2019). Огорчились, что мы придумали, но не реализовали «обход лабиринта по левой стеночке» — у Unagi этот подход хорошо сработал

А ещё увидели у ребят из Unagi кучу кода на shell. В частности, инфраструктурного, с помощью которого они запускали свои алгоритмы на 96-ядерных spot-инстансах в Amazon Web Services: