Только что закончился ICFP Contest 2021 года, и я «по горячим следам» пишу этот отчёт. Как и каждый год (начиная, кажется, с 2011?), я участвовал в составе команды Codingteam. Кроме меня, в нашей команде были следующие участники:

• Minoru
• Akon32
• portnov
• pink-snow
• sergevp

Наш код можно посмотреть в публичном GitHub-репозитории.

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

Подготовка

В качестве языка программирования мы загодя планировали использовать Scala (потому что Haskell был в прошлом году). Поэтому мы начали заранее готовиться к работе: Minoru завёл репозиторий на Гитхабе, залил туда Hello world-проект на Scala с тестами, и попросил всех, кто планировал участвовать, убедиться, что у них всё собирается и работает. Попутно мы решили несколько инфраструктурных проблем на машинах участников, и в целом к соревнованию были готовы.

Мы договорились использовать Scala 2.13, а не свежевышедшую 3.0, во избежание всякого.

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

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

Помимо прочего, я взял отпуск на всё время соревнования (то есть на пятницу 9 июля и понедельник 12 июля), потому что решил, что силы в эти дни мне пригодятся. И не зря!

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

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

2021-07-09, день 0

По моему часовому поясу соревнование началось в 19:00, а к тому же я себя не очень хорошо чувствовал, но всё-таки вовремя приступил к работе.

Ровно в назначенный час была опубликована спецификация, которая не будет значительно меняться по ходу соревнования. Нам предстоит решать задачи, стилизованные под популярное японское телешоу, Brain Wall. Предполагается, что на нас надвигается платформа с контурным отверстием, а нам нужно сложить некоторую заранее заданную фигуру таким образом, чтобы она пролезла в это отверстие. При этом решения иногда называют «позами» (что соответствует оригиналу), а сайт с автопроверкой решений метко называется poses.live.

Вот ссылка на визуализацию одного из наших решений для последней задачи (которая выглядит забавно). На случай, если оно не переживёт время, ниже добавлю гифку.

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

Minoru: по сути у нас две проблемы: 1) уместиться в дыру (это обязательно); 2) «растянуться» так, чтобы наши точки оказались поближе к точкам дыры (это опционально). Не факт, что две эти штуки решаются одинаково

Контуры отверстий и фигуры нам доставляются в более-менее удобном виде в JSON; есть возможность как загрузить результаты через веб-интерфейс, так и в автоматическом режиме через API.

Разумеется, я не сумел в первые минуты обойтись без своего юмора:

fvnever: Всё, мы проиграли

fvnever: Пеговка набрала более 9 тыщ очков

fvnever: Будем бороться за второе место или расходимся?

(стоит отметить, что Пеговка — это название населённого пункта из прошлогоднего соревнования, и на этот раз кто-то назвал свою команду так же)

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

fvnever: Цоднингтим взорвал танцпол

fvnever: С пятым местом

Minoru: не знаю, у меня первое место показывают

fvnever: Скринь скорее

Minoru: уже

fvnever: Как мы их всех уничтожили

fvnever: Всё, расходимся? Мы выиграли?

На этом этапе уже стало нужно, наконец, писать какой-то код. Я для себя выбрал задачу UI-визуализатора (по опыту понимая, что он обязательно пригодится и ещё не раз). Во-первых, это достаточно простая задача для столь ограниченного человека, а во-вторых, у меня опыта в написании UI на JVM побольше, чем у других товарищей, и поэтому я с ней мог бы более эффективно справиться.

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

portnov: приходит в голову какой-то итеративный алгоритм, что-то наподобие алгоритма Ллойда. Берём точки вне дырки, каждую двигаем к ближайшей точке внутри дырки. Расстояния соответственно поедут. Теперь берём рёбра и удлинняем / укорачиваем их до положенной длинны. Какие-то точки от этого выедут за пределы дырки. Опять их проецируем на контур дырки, итд в цикле.

Как оказалось, за прошедшие годы сообщество Scala так и не договорилось использовать какой-то один нормальный JSON-сериализатор, поэтому мне внезапно снова пришлось вспоминать, а что там сейчас в моде на эту тему. В итоге взял jackson и jackson-module-scala, который себя показал с лучшей стороны. Надо заметить, я всё-таки немножко опростоволосился с jackson из-за отсутствия nullable-типов в языке, но это было в этот раз не страшно, и проблема была вовремя исправлена.

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

Попутно мне в чате рассказали про очень полезный тип java.awt.Polygon, который несколько раз нам пригождался как для задач рисования, так и для задач валидации (поскольку он предлагает прекрасный метод определения принадлежности точки многоугольнику). Почему-то Minoru (а за ним и portnov) окрестили этот тип названием "JWT".

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

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

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

2021-07-10, день 1

Ну и ещё, пока я спал, у народа не работала IDE, и это было неприятно! (А к утру действительно починилась.)

Akon32: почему idea не видит пакет java...

Akon32: ужас какой-то

portnov: потому что форневер спит

portnov: это же так положено, баги проявляются пока девелопер спит

portnov: завтра он проснётся и у тебя идея починится

(для тех, кто не в курсе, напомню, что я косвенно являюсь одним из разработчиков IntelliJ IDEA, хотя Java- и Scala-модулей своими изменениями практически не касаюсь)

А ночью в чат подошёл и pink-snow, и помог с решением подручных задач в визуализаторе и везде подряд.

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

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

Minoru приступил к автоматизации решения для простых задач: сделал автовращатель.

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

Увидев первое решение задачи от sergevp, portnov высказал догадку, что правильно составленные треугольники рёбер будут играть важную роль при решении задач.

Конструктивную деятельность я начал с того, что поругался на Scala-реализацию списков:

portnov: я думал List это интерфейс, как в жаве

fvnever: Лист — это не интерфейс, это грех.

Видимо, с горя portnov начал решать какие-то хитрые уравнения в Wolfram Alpha (похоже, пытаясь найти минимумы функций, которые оценивают наши решения на стороне организаторов).

А вот он описывает детали реализации будушего оптимизатора решений:

portnov: кто умеет в какой-нибудь "метод ветвей и границ" или чото такое?

portnov: идея такая. Дано нам начальное состояние. Мы его можем менять парой способов в разных направлениях. Получаются дочерние состояния.

portnov: сначала надо из исходного состояния сделать любое валидное решение, а потом из него — решение получше.

portnov: варианты изменения: а) любую точку подвинуть на пару пикселей, в рамках эпсилона;

portnov: б) если точка связана ровно двумя рёбрами, то её можно отразить относительно прямой, соединяющей две соседние точки

В какой-то момент pink-snow решил добавить в проект scalafmt и переформатировать весь код. И даже приложил соответствующий PR на GitHub. Но делать мы этого, конечно, не стали, потому что заставлять людей разрешать конфликты форматирования в слабо знакомом языке — это уж как-то совсем не по-людски.

Minoru делает что-то с алгоритмом Брезенхема (я не понял, что именно).

Ближе к вечеру у Minoru отключили Интернет, а у sergevp отключили электричество! Но последний сумел каким-то непостижимым образом оставить нам своё наследие — питонокод — через сервер организаторов (загрузил питоновый файлик в качестве решения одной из задач). Это было забавно. (Но в итоге у обоих всё починилось.)

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

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

Также я нашёл и исправил баги в работе с BigInt и BigDecimal. Там совершенно дикий API, в котором метод round делает trunc, поэтому пришлось искать нормальное решение.

Вечернее обновление спецификации принесло с собой несколько проблем в обоих смыслах слова (то есть как новых задач, так и настоящих проблем). Теперь в каждой задаче мы можем выиграть бонусы, если разместим фигуру в определённой точке, и сможем эти бонусы использовать в определённых других фигурах! Сразу отмечу, что, как и всегда, до бонусных механизмов мы как следует не добрались, и залили всего лишь около двух задач с применением бонусов (благодаря тому же sergevp). До конца соревнования в спецификацию вносили ещё несколько видов бонусов, но, поскольку мы их не особо использовали, я не стану на этом далее заострять внимание.

2021-07-11, день 2

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

sergevp отчитался о достижениях в питоновой версии UI и вообще:

sergevp: В гуе я реализовал опции:

• автостретчинг - рёбра стремятся вернуться в норм.размер (выглядит как "резиновая фигура")
• автозапихивание - вершины стремятся сползти к ближайшей точке дырки
• авторастягивание - каждая вершина дырки тянет к себе ближайшую вершину

Всё кроме перетаскивания мышой — в дробных числах (надо для поворота и авто- стягивания - иначе фигура не стабилизируется) + кнопка Round to int, чтобы привести все точки к целым.

Этого мне хватило, чтобы вручную решить любую задачу, или найти какое-то валидное решение минут за 10-20.

sergevp: И вообще мне казалось, что если мы засабмитим хоть какое-то решение по каждой задаче - у нас было бы одно из первых мест. :) Я и собирался это сделать (начиная от тех, за которые давали больше очков), но тут отключили свет. :(

sergevp: Идеи, которые не сделал:

• после "Round to Int" часть рёбер оказывалась пере-/недо-растянутыми, их приходилось править мышой, а надо бы сделать стабилизацию растянутости в целых числах (есть пара идей на эту тему)
• многие задачи имеют точное решение с нулём дизлайков, вот бы находить их в автоматическом режиме...

sergevp: Забракованные идеи:

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

А ещё он сделал у себя поддержку бонусов! И реализация на Питоне так и осталась единственной у нас, которая их поддерживала: в коде на Scala до этого просто не дошли руки.

Minoru занялся генетическим алгоритмом, который должен был бы искать «нулевые» (т.е. идеальные) решения для задач.

pink-snow доделал несколько ручных инструментов для нашего UI (для поворота и перетаскивания точек). (Кстати, как работает drag tool — я во время соревнования так и не понял, и пришлось спрашивать уже после.) А под вечер у него обнаружилась очень странная проблема с SBT (отказывался принимать ввод в интерактивном режиме), которая вылечилась перезапуском терминала.

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

В момент особой задумчивости я начал решать задачи с помощью нашего UI, и местами вышло не очень плохо (и полезно для нашего рейтинга, а, следовательно, и боевого духа). Собственно, в процессе решения задач я набрёл на баг в нашей простой проверке корректности решения с помощью растеризатора. К счастью, Minoru как раз допортировал правильную геометрическую проверку из кода sergevp (ну, почти правильную, после пары моих правок), и мы её использовали везде, где это было важно.

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

fvnever: Возможно, какая-нибудь мелкая слабая команда, у которой очень мало очков, решила некоторую задачу за ноль баллов

fvnever: И поэтому она вычла баллы у более крутых команд, которые решили ту же задачу хуже

fvnever: В итоге по общему балансу те команды потеряли баллы

fvnever: А мы могли потерять меньше, или вообще не потерять, потому что мы ту задачу не решили

fvnever: Из-за этого мы можем внезапно расти в рейтинге, ничего не делая. Из-за разборок чужаков.

2021-07-12, день 3

Ночью Minoru вообще расколбасило, и он решил нашу задачу превратить в boolean satisfiability problem (SAT). И даже почти с этим справился, но, как он позже рассказал (и очень расстраивался!) он при составлении замысла забыл, как работает выставление оценок для наших решений. К сожалению, подробности я не очень понял, но, похоже, что алгоритм оценки был очень важной деталью для его реализации, и из-за этого алгоритм так и не заработал вообще, а время было потрачено. Не расстраивайся, Minoru, такое случается. Мне кажется, от тебя всё равно была очень большая польза.

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

Minoru чуть было не втянул меня в свои исследования SAT, но я вовремя напоролся на minisat, который ещё надо собирать под Windows, и это меня задержало достаточно, чтобы переключиться на другие задачи. Впрочем, Minoru честно предупредил, что его труды могут оказаться бесплодными.

Ну и в некоторые задачи пришлось прям вообще по хардкору втягиваться, и перекладывать узлы до просветления (т.е. пока не получу идеальное решение).

sergevp сегодня обещал отключиться (понедельник же! кажется…), но всё равно понемножку эпизодически принимал участие. Он решил несколько задач с бонусами, но залил их на сервер с ошибками (сначала пропустил указание бонусов, потом portnov залил обратно валидное решение, потом он опять залил решение но уже с неверно кодированными бонусами, и лишь в самом конце уже мы совместными усилиями разрешили все проблемы и залили работающие решения). Поскольку это происходило в последние минуты соревнования, а организаторы включили лимит на загрузку решений (не чаще одного решения на конкретную задачу за 5 минут) — это было достаточно опасным моментом! Но, к счастью, всё разрешилось очень хорошо, все проблемы залились в таком виде, в каком нам было нужно.

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

Результаты

На момент традиционной заморозки рейтинга (за один час до конца соревнования) мы занимали 30 место из 160 команд. В окончательном рейтинге (который стал известен чуть позже) наша позиция не поменялась.

Выводы

Мне понравилось соревнование в этом году. Задача достаточно сбалансирована, чтобы можно было и UI пописать, и алгоритмы посмаковать.

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

Во время соревнования всё время было, чем заняться. Не знаешь/устал от сложных алгоритмов — иди порисуй UI, или займись простыми геометрическими инструментами для работы с фигурами. Посетила светлая идея — срочно беги реализовывать, а UI за тебя допишут. Устал от всего — можешь вручную порешать головоломки.

Я, например, когда не понимал, чего делать, занимался инфраструктурой (всякие там скачивалки и автозагрузчики), а потом уже копался в UI.

Товарищи по команде, да и другие участники в Discord согласны, что такая организация задачи, когда её можно решать вручную/в полуавтоматическом режиме (пусть и с переменным успехом), довольно удачна.

Спасибо организаторам, спасибо оппонентам, спасибо товарищам по команде. Надеюсь, что и в следующем году нам удастся поучаствовать в ICFPC!