ICFP Programming Contest — это ежегодное онлайн-соревнование, длящееся три дня и предлагающее весьма нестандартные, почти что жизненные задачи. Например, в прошлые годы мы управляли 3D-принтером и «дезинтегратором», писали эмулятор аркады и играли в Пакмана, даже участвовали в межгалатических «звёздных войнах»! В общем, скучно не бывает (почти).

В этом году контест проходил с 9-го по 13-е июля. Я традиционно играл в составе Codingteam, которую также представляли Akon32, ForNeVeR, pink-snow, portnov и sergevp. Последний с нами ещё не выступал, но он любит задачки и весь предыдущий год обсуждал со мной ката в CodeWars. Вообще приятно, что команда обрастает новыми людьми, которые затем превращаются в постоянных участников: больше идей, больше рук для их реализации, больше фана и выше места́ в рейтинге.

Код писали на Scala 2.13. Да, старье, но тройка только-только вышла и вряд ли готова, да и мы к ней не готовы тоже :) Моя шпаргалка для хаскелистов актуальна до сих пор. Репозиторий со всеми наработками можно найти на GitHub.

Дальше я буду рассказывать в основном про то, что делал сам. За обзором работы всей команды смотрите отчёт ForNeVeR-а.

Задание

Организаторы вдохновлялись японской передачей Brain Wall: игрок стоит на месте, за спиной у него бассейн, а спереди на него едет стена с отверстием причудливой формы. Чтобы не оказаться в воде, игрок должен как-нибудь извернуться и протиснуться в дыру. Проще показать:

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

Таблички «663» и «0», которые подымают судьи — это оценки решения. Они измеряются в «дизлайках», поэтому чем меньше, тем лучше; ноль — вообще идеально. Рассчитывается просто: от каждой вершины отверстия вычисляется квадрат расстояния до ближайшей вершины фигуры; сумма этих квадратов и есть оценка решения. (Внимательный читатель будет вознаграждён). Все подробности условия можно прочесть здесь.

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

Что я делал в пятницу и субботу (Z-72)

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

Я настолько увлёкся этой физической аналогией, что даже перечитал главу Ландсберга про статику и осознал, какие силы возникали бы в рёбрах треугольника, парящего в пространстве, если приложить силу к любой его вершине. Чуть позже Форневер и sergevp независимо реализуют более простой «force solver», который считает рёбра пружинами и учитывает только силу упругости, и мои открытия не пригодятся.

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

Закончив с арифметикой, я быстренько написал «оценщик» решений, использующий вышеописанную формулу, и занялся первым «решателем»: мой «rotation solver» методом градиентного спуска искал самый удачный поворот фигуры. Никаких серьёзных задач он решить не мог, но я надеялся, что его удастся использовать как базу для более крутых алгоритмов. Тем временем у меня наступила ночь, и я ушёл спать.

В субботу я появился в чате ровно в тот момент, когда обсуждение дошло до A*. Кто не понимает, в чём тут соль — марш читать все мои предыдущие отчёты :) Портнов обратил внимание, что треугольники можно только двигать и поворачивать — их нельзя ни сложить, ни скрутить, потому что от этого ломаются рёбра. Следовательно, если выделить из фигуры некий «остов», то искать его положение будет сильно проще. Вдохновившись этими идеями, я написал алгоритм поиска отдельных треугольников, а затем поправил написанный Портновым алгоритм Брезенхэма: он у нас работал только с целочисленными радиусами, а в задачах встречались величины вроде \(26 \sqrt{2}\).

Тут у меня начало шатать Интернет, а у sergevp и вовсе выключили свет, но мы продолжали бороться: sergevp решал задачи вручную, удерживая нас на 25-м месте, а я занялся поиском «остова». К Z-46 этот код был готов, и я занялся развитием «верификатора», чтобы можно было проверять, находится ли точка внутри отверстия (там уже был похожий код, просто не было метода, который можно было бы дёрнуть снаружи). Заодно написал ещё и генератор случайных точек, лежащих внутри отверстия — задел для будущих стохастических алгоритмов (которые так и не появились).

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

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

В Z-40, пока я учил наш визуализатор загружать решения из файла, в чат вернулся sergevp и рассказал, что он успел понапридумывать в оффлайне. Среди прочего упомянул и неудачные идеи, например:

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

Тут меня совсем стал рубить сон, и я ушёл спать.

Воскресенье (Z-28)

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

Реализация выглядела так: координаты, в которых находится вершина фигуры — это «ген», а «особь» — это набор «генов», то есть решение задачи. Чтобы сгенерировать случайную особь, берутся случайные вершины отверстия (с повторами). При мутациях 10% вершин заменяются на случайные, а при скрещивании создаётся новая особь, в которой 90% генов взяты из одного предка, а остальные из другого. Ну, а дальше всё стандартно: оцениваем каждую особь, складываем их в TreeSet и оставляем только 10 тысяч лучших. Потом проходимся по этому «поколению», случайным образом мутируя и скрещивая особей, и начинаем новый виток отбора.

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

Затем я додумался глянуть на промежуточные решения в визуализаторе и обнаружил, что алгоритм преспокойно создаёт рёбра за пределами отверстия. Чтобы это предотвратить, мне нужно было «наказывать» особей с такими рёбрами. К сожалению, наш «валидатор» не умел сообщать, какое именно ребро оказалось за границей, поэтому я позаимствовал соответствующий код у sergevp. На портирование ушло совсем немного времени, и к Z-22 я наконец-то смог заставить генетику не выходить за границы отверстия, пригрозив ей дикими штрафами — четвёртой степенью длины ребра-нарушителя. Это помогло, но сходимость не улучшилась.

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

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

«Ночью Minoru вообще расколбасило» (Z-19)

Наблюдая за промежуточными решениями генетики, я всё больше утверждался в мысли, что поиск можно было бы направлять, если учитывать длину рёбер. Я даже проанализировал имеющиеся задачи и выяснил, что у отверстия максимум 108 вершин, а у фигур — 224 вершины и 350 рёбер. Итого между вершинами отверстия можно сформировать чуть менее шести тысяч рёбер, из которых часть окажется за пределами отверстия и будет отбракована, а из остальных мы отберём те, длины которых соответствуют рёбрам фигуры. (Ага.) Пространство поиска можно сократить ещё сильнее, если учесть, что каждая вершина фигуры имеет рёбра строго определённой длины: например, если из неё выходят рёбра длиной 3 и 5 единиц, то её нельзя расположить в вершине отверстия, из которой выходят только рёбра длиной 1 и 3 единицы.

Я кратко обсудил эту идею с sergevp и, не получив убойных контр-аргументов, принялся за дело. Нужно понимать, что на часах у меня было уже полдесятого вечера, я кодил 11 часов кряду, а в голове вертелась фраза «constraint optimization» и воспоминания о нескольких постах майнтейнера Catch2. Изначально я думал, что поиском будет заниматься A*, но пока я занимался отсеиванием рёбер, идея про A* мутировала в совершенно шальную мысль: преобразовать всю задачу в boolean satisfiability problem! После этого её можно было бы скормить любому из существующих SAT-солверов (которые оптимизировались под эту задачу годами) и быстро получить решение.

Boolean satisfiability problem, или SAT, формулируется просто: есть булевы (двоичные) переменные и несколько выражений с их участием; нужно найти такое значение переменных, что все выражения истинны.

Представьте, что у фигуры \(F\) вершин, а у отверстия — \(H\). Пусть булева переменная \(f_ih_j\) будет истинной, если \(i\)-я вершина фигуры должна быть размещена в \(j\)-й вершине отверстия. Теперь можно сформулировать правила, описывающие «нулевое» решение задачи:

1. каждая вершина фигуры соответствует ровно одной вершине отверстия, то есть среди переменных \(f_ih_1, f_ih_2, f_ih_3, \ldots, f_ih_H\) истинной должна быть ровно одна. Звучит просто, а вот на языке булевой алгебры выглядит страшновато:

   \[\begin{array}{crrcrcrcccrl} & ( & f_ih_1 & \land & \lnot f_ih_2 & \land & \lnot f_ih_3 & \land & \ldots & \land & \lnot f_ih_H & ) \\ \lor & ( & \lnot f_ih_1 & \land & f_ih_2 & \land & \lnot f_ih_3 & \land & \ldots & \land & \lnot f_ih_H & ) \\ \lor & ( & \lnot f_ih_1 & \land & \lnot f_ih_2 & \land & f_ih_3 & \land & \ldots & \land & \lnot f_ih_H & ) \\ \vdots & & \vdots & & \vdots & & \vdots & & \ddots & & \vdots & \\ \lor & ( & \lnot f_ih_1 & \land & \lnot f_ih_2 & \land & \lnot f_ih_3 & \land & \ldots & \land & f_ih_H & ) \end{array}\]

   И так для каждой из \(F\) вершин фигуры. Хорошо, что эти штуки будет генерировать компьютер!

2. вершина фигуры может быть помещена только в ту вершину отверстия, из которой исходят рёбра нужной длины. Например, если вершина \(f_3\) может быть помещена только в вершины \(h_4\), \(h_7\) и \(h_9\) (потому что у других нет всех нужных рёбер), должно выполняться следующее условие:

   \[f_3 \land (h_4 \lor h_7 \lor h_9)\]

3. если между двумя вершинами фигуры существует ребро, то эти вершины нужно размещать в соседних вершинах отверстия. Например, если между вершинами \(f_1\) и \(f_3\) есть ребро, и при этом вершина \(f_1\) может быть размещена в вершинах \(h_2\) и \(h_4\), а \(f_3\) — в \(h_8\) и \(h_9\), и к тому же подходящие рёбра образуются только парами \((h_2, h_8)\) и \((h_4, h_9)\), то при размещении \(f_1\) в \(h_2\) нужно обязательно разместить \(f_3\) в \(h_8\), а при размещении \(f_1\) в \(h_4\) — обязательно разместить \(f_3\) в \(h_9\):

   \[(f_1h_2 \land f_3h_8) \lor (f_1h_4 \land f_3h_9)\]

4. если между двумя вершинами фигуры существует ребро, то эти вершины не могут быть помещены в одну и ту же вершину отверстия. Это совершенно очевидное правило пришло мне в голову гораздо позже, когда я начал смотреть на результаты первых трёх и увидел, что солвер ради решения готов сломать всю геометрию. Тут пришлось даже вывести формулку, похожую на импликацию, но как бы наоборот: \(\lnot a \lor \lnot b\) означает, что \(a\) и \(b\) не могут быть истинными одновременно. Теперь, если между \(f_1\) и \(f_4\) есть ребро, то для каждой из \(H\) вершин отверстия нужно сгенерировать условие:

   \[\lnot f_1h_j \lor \lnot f_4h_j\]

Выглядит несложно, правда? На часах Z-16, мы занимаем 26-е место рейтинга (из 158-и команд), меня клонит в сон — превосходные условия для кодинга. Погнали!

Moonshot (Z-16)

Между мной и идеальными решениями всех задач стояла всего одна преграда: я никогда раньше не пользовался SAT-солверами. К счастью, в тех же постах майнтейнера Catch2 был упомянут Minisat, чья документация быстро прояснила ситуацию:

1. солвер принимает на вход не произвольные выражения, а некую «конъюнктивную нормальную форму» — термин, который я не слышал со времён университета;
2. КНФ записывается не как формулы выше, а в неком формате DIMACS;
3. решение выдаётся в каком-то третьем формате, специфичном для Minisat.

КНФ — это такая запись булевого выражения, где отрицания стоят только рядом с переменными, переменные объединяются только с помощью логического ИЛИ, а между объединениями стоят только логические И. Например, \((f_1h_1 \lor \lnot f_2h_9) \land f_3h_5\). Чтобы из вышеприведённых формул получить КНФ, нужно в цикле применять два закона и одну теорему, найти которые можно в Википедии. Освежив память, я взялся писать «упрощалку» выражений.

Сперва у меня произошёл фальстарт: я был настолько занят размышлениями о КНФ, что заточил под него AST булевых выражений. Конечно, это замечательно, что результат получается по построению, но на входе у меня всё же не КНФ. Переделав как надо, к Z-13 я получил (пока что не реализованную) возможность закодировать вышеприведённые формулы и выдать их в требуемой форме.

Формат DIMACS оказался простым текстом, в котором сперва нужно указать количество переменных и «клоз» (clause), а потом перечислить клозы одну за другой. Клозы — это те части КНФ, которые объединяются через И. На это ушёл ещё часок, основная часть которого была потрачена на осознание того, что StringBuffer для задачи не подходит и вместо него нужен Array[String].

Где-то к Z-9, то есть середине ночи, я наконец-то закодировал первое правило, преобразовал его в КНФ, вывел DIMACS, руками скопировал его в Minisat и получил решение самой простой задачи: повернув треугольник на 90°, уместить его в такое же треугольное отверстие. На более крупных задачах моя «упрощалка» выражений просто загибалось. Прочитав Википедию чуть внимательнее, я узнал, что некоторые выражения при переходе к КНФ растут экспоненциально. Чтобы это побороть, я нагуглил алгоритм получше, но тут же отложил — сперва нужно было дописать остальные куски кода.

А оставалось не так уж много: ещё три правила и автоматический запуск Minisat с разбором результата. Впрочем, правила требовали вычисления длин рёбер и отсеивания вершин, так что вся эта работа была завершена только к Z-6, то есть утру понедельника.

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

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

Внимательный читатель, наверное, уже охрип орать на монитор; потерпи, осталось всего три десятка слов. В Z-3:11 я наконец догадался открыть в визуализаторе одно из «нулевых» решений, которые ребята сделали руками, и обнаружил, что некоторые вершины фигуры не совпадают с вершинами отверстия! Дальше просто цитирую чат:

<ForNeVeR>
Не все точки решения должны содержаться в узлах отверстия.

<Minoru>
для нуля дизлайков? Но почему?

<ForNeVeR>
Там обратное требование
В каждой точке дыры нужно иметь одну из точек фигуры
У фигуры больше точек, чем у дыры, поэтому остальные точки могут делать что им захочется (в пределах ограничений).
Рейтинг смотрит на ближайшую точку фигуры к каждой точке дыры.

<Minoru>
*схватился за голову*
то есть
я два дня занимаюсь полной ерундой
и вы это терпите?

<ForNeVeR>
Мы не поняли, чем ты занимаешься :(

А вернее, я не объяснил толком, чем я занимаюсь, поэтому меня не успели остановить и разубедить. Эх!

Забавно, что эта ошибка была допущена именно мной. Ведь это же я писал «оценщик», я должен был лучше всех знать, как считается оценка! И тем не менее: код я написал правильно, а принцип запомнил неправильно; построил на нём две заведомо нерабочие идеи и успешно спустил два дня в трубу.

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

Выводы

Личные:

• думать наперёд полезно, но у меня получается не очень хорошо. Вместо чтения Ландсберга нужно было закодить «очевидную» идею с рёбрами-пружинами и посмотреть, как она работает;

• первым делом надо писать визуализатор и «щупать» задачи руками. Писать «солвер», не решив ни единой задачи вручную — это хороший способ получить максимум фана и минимум результата;

• ну и ещё пара, которые я не буду писать в Интернете, но над которыми уже думаю.

А про команду написать нечего. Я в этом году слишком мало в команде участвовал, чтоб о ней выводы делать :)

Результат

В lightning division (первые 24 часа соревнования) мы 26-е из 137-и, в финале — 30-е из 160-и. Это лучший наш результат за всё время и я, вообще-то, удивлён. Портнов на протяжении всего контеста рассказывал про умных дядь из сильных команд, которые наверняка уже три дня молотят задачи с помощью чудо-алгоритмов на супер-мейнфреймах, а оказалось, что команда из 6-1 человек, решающая задачи почти что вручную, способна я этими «умными дядями» тягаться. Чудеса!

Если вы сюда дочитали, то, во-первых — спасибо! Во-вторых, ребята из команды TBD (вы могли видеть их вверху рейтинга на прошлых ICFPC) хотят организовать в первом квартале следующего года тренировку по ICFPC и дать задачку с какого-то из прошлых контестов. Приглашают всех в свой Discord. Увидимся ^_^