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

Вопреки традиции, отпуск мне взять не удалось, поэтому к команде я присоединился только вечером пятницы, спустя четыре с половиной часа после начала соревнования. Задание (зеркало) вызывало лёгкое ощущение дежавю: создавая прямоугольные трафареты и закрашивая сквозь них полотно, мы должны были как можно быстрее и точнее воспроизвести заданную картинку. Самих картинок-задач под конец соревнования набралось аж 40 штук, причём они варьировались от обманчиво-тривиальных изображений Тетриса до вполне реальных картин вроде «Крика» Эдварда Мунка. В общем, классика ICFPC: задание, которое легко объяснить, но сложно выполнить.

Решение нужно было записать при помощи специального языка из пяти команд: разрезать полотно на кусочки («блоки») по горизонтали, вертикали или на четыре части, поменять два кусочка местами, склеить два кусочка или закрасить кусочек определённым цветом. За каждое действие мы платили цену, причём за действия над мелкими кусочками гораздо больше, чем за действия над крупными. Кроме того, учитывалась степень похожести результата на заданную картинку; она вычислялась как сумма отклонений цветов каждого пикселя.

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

Пятница

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

К сожалению, получившиеся решения нельзя было отправить, потому что они не влезали в установленный организаторами двухмегабайтный лимит. Поэтому первое, что я сделал — это залил для всех задач пустое решение, состоявшее из одного только комментария «# nothing». Так как турнирная таблица сортировалась сначала по убыванию количества решённых задач, а затем по возрастанию стоимости решений, то мы сразу попали на восьмое место. Чудно!

Дальше я занялся оценщиком решений — вернее, интерпретатором, потому что для вычисления оценки нужно знать площадь задействованных в команде блоков. Тут меня ждала засада.

Условие задачи было сформулировано так, будто бы у блоков (кусочков полотна) есть иерархия: они делятся на «простые», которые залиты одним цветом, и «сложные», состоящие из нескольких простых. Кроме того, у каждого блока есть идентификатор, например «0», и при разрезании блока из него образуются блоки с идентификаторами «0.0» и «0.1». Мы, естественно, смоделировали это деревом. Теперь же я сидел и думал, как реализовать команду склеивания блоков: если разрезать полотно по горизонтали, затем каждую половинку разрезать по вертикали, а потом попытаться склеить четвертинки, принадлежащие разным половинкам, то придётся обновлять всю иерархию, начиная с корня!

Вообще-то деревья — это моя любимая структура данных, но такие широкомасштабные манипуляции даже для меня были чересчур. Поэтому я решил попробовать другое представление: хранить отображение из идентификатора блока в его положение и размеры (Map BlockId Shape), а также отображение из идентификатора блока во множество идентификаторов блоков, которые он содержит (Map BlockId (Set BlockId)). Успешно реализовав поверх этого все виды разрезов, я принялся за команду объединения — и обнаружил, что она опять не получается! В этот раз мешало то, что у простых блоков, находящихся внутри сложного, нет идентификаторов — они теряются, когда блоки объединяются. Таким образом, второе отображение вообще не имело смысла, т.к. я ничего не мог положить во множества.

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

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

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

Суббота

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

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

Тем временем организаторы выкатили обновлённую спецификацию. Это, кстати, фишка ICFPC — задача в целом не меняется, но время от времени выходят обновления, привносящие усложнения и сюрпризы. В этом, первом, обновлении организаторы добавили задачи с заранее раскрашенными полотнами и уже нарезанными блоками. Теперь нужно было не просто нарисовать что-то с нуля, а дорисовать или перерисовать то, что уже есть. Ощущение дежавю немного усилилось — ровно такое же обновление было в 2018-м году. Первой идеей было свести задачу к предыдущей: объединить все блоки обратно в один большой, а затем решать задачу уже существующими солверами. Портнов занялся парсером нового формата задач, а Форневер трудился над алгоритмом вырезания заданного прямоугольника из полотна.

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

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

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

<portnov> отправил решения на 26-й, 28-й, 29-й задачи, которые получились лучше чем “# nothing”

<Minoru> надеюсь, с комментарием «# better than nothing»? :)

<portnov> Minoru: that’s why we call it beta.

<portnov> ’cause it’s betta than nothin

А потом мы застряли. Akon32 знал, какой алгоритм применить к вычислению среднего, но очень долго писал его на Haskell. Портнов пытался ускорить уже существующий алгоритм с помощью библиотеки repa, но безрезультатно. Форневер продолжал заниматься алгоритмом вырезания прямоугольника, и тоже без прогресса. Я же, как уже сказано выше, погряз в трясине монад. Чатик окутало уныние, и мы даже немного поспорили, на каком языке писать в следующий раз.

Чтобы ощутить хоть какой-то прогресс, я плюнул на мутабельные изображения и занялся скриптом, который запускал бы все солверы на всех задачах и записывал лучшие решения в наш репозиторий. Форневер наконец-то заставил свой код компилироваться, словил исключение и теперь ждал, пока проект пересоберётся более старым компилятором — оказалось, что в GHC 9.0.2 сломано профилирование, без которого не работают стектрейсы. А без стектрейсов, вобщем-то, Хаскель дебажится только внимательным чтением кода.

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

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

В итоге получилось что-то вроде биллборда, составляющего изображение из вертикальных полос. К двум часам ночи Alt.Solver.Billboard был готов, и даже улучшил наши решения по паре задач. Довольный первым существенным прогрессом, я ушёл спать.

Воскресенье

За ночь pink_snow написал на Python программу, генерирующую решение первой задачи (на картинке выше), а также ускорил вычисление среднего цвета. Это, как и ожидалось, существенно помогло cолверу, искавшему оптимальную точку разреза, и мы получили несколько улучшенных решений. Портнов, проснувшись, занялся новыми задачами, в которых изначально уже присутствовали какие-то блоки: объединив их обратно в один большой, можно было свести эти задачи к предыдущим и применить существующие солверы.

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

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

Алгоритм теперь выглядел так:

1. закрашиваем полотно средним цветом левого столбца;
2. для каждого столбца, начиная со второго:
   1. разрезаем полотно по линии перед этим столбцом — фактически, делим полотно на уже готовую и ещё не готовую части;
   2. закрашиваем правую часть полотна средним цветом текущего столбца;
   3. склеиваем половинки обратно.

Согласно моим расчётам, это должно было уменьшить стоимость программы в 1,75 раз.

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

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

Тут организаторы снова обновили задачу. Отныне предварительно созданные блоки могли быть заполнены не просто цветом, а какими-то картинками. У нас уже не было сил с этим разбираться, поэтому мы просто забили. Ещё организаторы добавили в турнирную таблицу информацию о лучшем решении каждой из задач. Форневер, отчаявшись написать свой алгоритм вырезания прямоугольника, проанализировал циферки и выяснил, какие из задач мы решили сильно хуже, чем соперники. Результаты явно указывали на более новые задачи, так что у моей работы были все шансы как-то улучшить наше положение. Форневер тем временем взялся писать ручную решалку на C# (потому что этот язык он знает хорошо, а GUI на Haskell мы уже когда-то делали и это была боль).

К десяти вечера я доделал мерж начальных блоков. Алгоритм был простейшим, но я сразу же получил улучшения по ряду задач. Затем я добавил сортировку, чтобы алгоритм мержил пару, включавшую наибольший возможный блок — и снова получил ряд улучшений! Учитывая, что воскресенье было для меня последним днём соревнований (из-за работы), я был очень рад получить такой ощутимый прогресс.

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

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

Понедельник

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

Выводы

К моменту заморозки турнирной таблицы мы были 69-е из 93-х команд, решивших все 40 задач, и 150-ти команд, участвовавших в соревновании. В общем, средненько во всех смыслах слова. Update 2022.09.17: в финале мы 71-е из 151-го.

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

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

А ещё в этом году мы поздно принялись за GUI и поэтому не знаем, помог бы он нам или нет.

В целом я доволен. Несмотря на то, что контест готовили в последний момент, он получился достаточно оригинальным и интересным. Так что, дорогие читатели, если уж вы добрались до этого абзаца — вам обязательно надо поучаствовать в ICFPC 2023! До него ещё год, так что можете скоротать время чтением моих прошлых отчётов ;) Если владеете английским, почитайте ещё и отчёт Форневера — у него своя перспектива.