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

After a successful stint as painters, the denizens of Lambda land are now turning to different artistic endeavors, and starting a new career in music.

Только не Lambda land! Это был сеттинг унылейшей задачи 2017-го года, и даже весьма удачный сиквел 2019-го не смог реабилитировать сеттинг в моих глазах.

Тем не менее, я продолжил читать. Нам предстояло расположить музыкантов на сцене так, чтобы стоящие вокруг неё слушатели получили от концерта максимальное удовольствие. Оно зависело от ряда факторов:

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

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

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

Выяснилось, что у нас есть инфраструктура для скачивания задач и заливки решений, а также тупейший «солвер», который просто ставит всех музыкантов в угол сцены. Такое решение невалидно, т.к. между музыкантами должно быть не менее десяти единиц расстояния. Так что я первым делом написал чуть более умный вариант, расставлявший исполнителей на прямоугольной сетке. И сильно удивился, когда он не смог решить некоторые задачи! Оказалось, что там много музыкантов и маленькая сцена, и в прямоугольной сетке не хватает узлов. Я написал ещё один солвер, расставлявший музыкантов более плотно, и мы наконец получили свои первые очки.

Также я допилил нашу инфру, чтобы рядом с каждым нашим решением хранился JSON со скором (так как функция его расчёта заметно тормозила). Это позволяло быстрее перерешивать задачи новыми солверами. Чуть позже Гсомикс добавит в JSON поле с названием солвера, сгенерировавшего решение — а потом, с появлением улучшающих солверов, будет сокрушаться, что мы не храним там полную историю ☺ Урок на будущее: запилить такую инфраструктуру сразу, и хранить в ней как можно больше информации о том, как было получено каждое решение. Кто-то из соперников так и поступает:

[…] in the end our winning solvers looked like the following when invoked from the CLI: greedy+shake{cap=10}+vol10+genetic+genetic, which would translate into a chain of solver passes with greedy, shake (local optimization in real space) with cycle cap of 10 full cycles, setting volume to 10 and two genetic passes on top. We also implemented load_best solver, so you could test end-of-chain stuff directly on the best solution in our repo […].

Суббота

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

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

Я исправил проблему, но многие скоры все равно не сходились с сайтом организаторов. Да что же такое?! К счастью, в этот момент подвезли обновлённую спецификацию. Это традиция ICFPC — каждые сутки или чаще задача из нерешаемой превращается сначала в вообще нерешаемую, а потом в «они там совсем уже, что ли?». В нынешнем обновлении появились колонны и возможность «улучшать» игру музыканта, ставя его рядом с другими исполнителями на том же инструменте. Быстренько запилив поддержку этих фич в скоринг и выпустив таким образом пар, я вернулся к отладке.

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

1. мы считаем границу стадиона его частью, хотя по условию она должна быть исключена;
2. чтобы определить, принадлежит ли точка отрезку, мы используем правило треугольника и проверяем, что сумма двух коротких сторон примерно равна длинной. Но по алгоритму мы и так знаем, что точка лежит на прямой, поэтому достаточно проверить, что расстояния от точки до концов отрезка не превышают длины самого отрезка.

С фиксами этих проблем некоторые наши скоры наконец совпали с сайтом организаторов. Но не все. ☹

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

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

Остаток вечера ушёл на то, чтобы разбить формулу скора на составляющие и написать скелет итеративного расчёта. Можно было бы чуток быстрее, но в этом году мы с подачи Форневера писали на F#, поэтому заметная часть времени ушла на гугление синтаксиса. Глубоко в ночи я закоммитил скелет алгоритма и ушёл спать.

Воскресенье

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

Ладно (•̀⤙•́ ) Закатал рукава, пофиксил ошибку копи-пасты, пофиксил индексирование в массивах, пофиксил проверки валидности решения, добавил юнит-тест с задачей из спеки, исправил ещё одну ошибку в «стадионе» (он игнорировал препятствия, если линия музыкант–слушатель была вертикальной). Юнит-тест прошёл, но по сравнению с имевшимся скорингом мой алгоритм работал ужасно медленно.

Тем временем в командном чате пишут, что у нас закончились бесплатные минуты GitHub Actions.

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

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

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

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

На часах было 11 вечера, а из-за работы это был последний день, когда я могу играть. Пока я занимался итеративным скорингом, мысль о локальном поиске трансформировалась сначала в эволюционный алгоритм, а затем в имитацию отжига. Времени его реализовать не оставалось, поэтому я попытался объяснить смысл итеративного скоринга Форневеру в надежде, что в понедельник он сам сможет что-то запилить. Фокстран тоже заинтересовался, но так ничего и не реализовал.

Заодно кратко обсудили последнее обновление задачи, в котором музыкантам добавили громкость. Она варьировалась от 0 до 10, на неё умножался скор каждого музыканта. Гсомикс не видел в громкости никакого толку, и все наши решения задавали десятку всем музыкантам. Мне с трудом верилось в бесполезность этого обновления, поэтому я взял какой-то из наших «улучшающих» солверов, использующий метод Нелдера — Мида, и поправил его, чтобы оптимизировалась громкость. К сожалению, это не дало улучшений ни по одной из опробованных задач, поэтому я в расстроенных чувствах почапал спать.

Уже стоя под душем, я вдруг допёр, что на самом деле у громкости есть польза: с её помощью можно заглушить музыкантов с негативным скором! И, конечно же, это легче всего сделать с помощью итеративного скоринга, потому что:

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

Поэтому я вернулся за клавиатуру и быстренько запилил новый «улучшающий» солвер под названием suosi — «shape up or ship out». Он брал готовое решение, выставлял всем музыкантам единичную громкость, считал скор, а затем менял громкости в зависимости от скора каждого музыканта — кто-то получал 0, а остальные 10. Этот солвер смог-таки улучшить некоторые решения, но на смешные сотни тысяч единиц; общий скор решения к тому моменту мог превышать миллиард.

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

Итоги

На момент заморозки скорборда мы были 51-ми из 155-и (или 161, если считать тех, кто не решил ни единой задачи). Не самый блестящий наш результат, но и не худший; так, средненький. Окончательные результаты будут объявлены в сентябре во время конференции ICFP.

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

F# мне понравился маржинально больше, чем Scala. Да, с ним тоже приходится разбираться по ходу дела; да, я не знаю дотнетовских апишек; да, моя производительность далека от той, которую я достиг бы на «своём» языке. Тем не менее, язык вполне юзабельный, можно применять (раз в два года :)

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

В этом году Фокстран, Гсомикс и Форневер хорошо скооперировались, Портнов отвалился после первого дня, а мы с Аконом работали в основном в одиночку. Сложно сказать, хорошо это или плохо. Я, например, получил море фана за те два дня, что пилил итеративный солвер. Мне греет душу, что написанные мной солверы держали нас в лидерборде весь первый день. В общем, нам удалось поймать какой-то локальный оптимум, где нашлось место и кооперации, и индивидуализму.

За сим откланиваюсь. Если есть желание — поглядите на наш код на GitHub, а если желания нет — почитайте отчёт Форневера с более подробной хроникой работы всей команды. И до встречи в лидерборде ICFPC 2024!