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!

Вопреки традиции, отпуск мне взять не удалось, поэтому к команде я присоединился только вечером пятницы, спустя четыре с половиной часа после начала соревнования. Задание (зеркало) вызывало лёгкое ощущение дежавю: создавая прямоугольные трафареты и закрашивая сквозь них полотно, мы должны были как можно быстрее и точнее воспроизвести заданную картинку. Самих картинок-задач под конец соревнования набралось аж 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! До него ещё год, так что можете скоротать время чтением моих прошлых отчётов ;) Если владеете английским, почитайте ещё и отчёт Форневера — у него своя перспектива.

В этом году контест проходил с 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. Увидимся ^_^

Вот такая вот LEGO-модель теперь выглядывает из-за моего монитора и соблазняет плюнуть на всё и уехать в закат.

«Сердце» всей конструкции — двигатель с настоящими поршнями и цилиндрами. Под шестерёнкой с красной осью есть даже заводской номер!

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

Номерной знак, похоже, «с потолка»; примечательно лишь то, что Harley-Davidson основан в штате Висконсин.

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

Всё, заднее крыло уже не впечатляет — поглядите на бензобак! А выхлопная труба, вы видели?

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

Собрал! Ноутбук с пятнадцатидюймовым экраном для масштаба ☺

Руль просто шикарен. Там есть даже маленькие рычажки!

Впервые в жизни обратил внимание, что у каждого цилиндра своя собственная выхлопная труба.

Не знаю, почему на тахометре именно «1974», но спидометр и отделка бензобака повторяют реальность.

Играюсь с глубиной резкости. И нет, это не пятно на линзе, это курсор.

Целиком всю длину модели в ГРИП уместить так и не удалось.

В фаре можно разглядеть отражение горе-фотографа, заваливающего горизонт этой фотографии ☺

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

Изначально этот пост был галереей на Imgur.com, но теперь будет здесь — чтоб не потерялся.

1. предисловие;
2. день первый;
3. день второй;
4. день третий;
5. день четвёртый;
6. итоги и выводы (это то, что вы сейчас читаете).

Мы заняли 38-е место из 95-и, при этом 30 команд не заработали ни единого балла. Я удивлён, что мы не оказались среди их числа.

О задании

Делать тизеры частью задания нельзя. ICFPC длится 72 часа, а не две недели. Те, кто вникал в тизеры, в час T просто нажали F5 на ReadTheDocs и продолжили то, что делали предыдущие 14 дней. Формально это давало некоторым командам преимущество.

Дальше. Правила соревнования¹, пункт 2, гласят (выделение моё):

[…] Teams may not divide, merge, or collaborate after the start of the contest.

Вопреки этому соревнование началось именно с призыва собраться в Discord и сообща разгадывать сообщения. Первые сутки мы не могли делать ничего другого, кроме как коллаборироваться. Соревнование как таковое началось только спустя 24 часа 45 минут.

«Космолисп» и galaxy.txt оказались просто большим сайд-квестом. Да, там были туториалы, способные помочь с основной задачей, но с тем же успехом мы, наверное, могли проспать первые 46 часов, а после публикации описания команд зависнуть в Discord и таким образом выяснить всё, чего не знали.

За «космолисп» обидно вдвойне: вещь красивая, но программировать на нём довелось только при написании тестов.

Задание было, фактически, «матрёшкой» из загадок, а ядром её оказалось довольно скучная задача по управлению космофлотом. Да, там была неожиданная метрика расстояний и странная гравитация, но интереса задаче придавали исключительно загадки, в которые она была спрятана.

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

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

«Контур», не знаю, читает ли кто-то из вас этот отчёт, но: вы провели действительно выдающийся ICFPC, и я снимаю перед вами шляпу. ❤️

Об организации соревнования

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

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

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

О командной работе

Чтобы решить много загадок и проверить много идей, нужно много светлых голов и вдвое больше рук. Пожалуй, моим основным вкладом в нынешний результат было приглашение IngvarJackal-а и pink-snow к нам в команду: именно они написали львиную долю того кода, что завоевал нам 38-е место.

Даже самым светлым головам нужна организация труда, будь то менеджер, вики знаний, или же расписание статус-митингов. Для команды из восьми человек чат уже не может использоваться для хранения знаний — слишком большой объём и слишком мало структуры. Без должной координации часть потенциала участников останется неиспользованной; так, мне кажется, случилось в этом году с mr146, unclechu и Akon32 — любые поставленные задачи они решали быстро, да вот списка задач у нас не было, и часть времени была потеряна впустую.

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

Самоуверенность убивает. Я пресёк две попытки превратить функцию reduce в полноценную «вычислялку» «космолиспа» и, таким образом, задержал прогресс команды на целые сутки.

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

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

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

О Python

Что произошло: IngvarJackal написал прототип на Python; к началу оценивания у нас не было работающего бота на Haskell; прототип на Python ушёл в продакшен; система оценивания заставила меня допиливать то, что уже работает, а не то, что я хочу. Отсюда ирония и картинки с Гарольдом.

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

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

Если бы мы решали какую-то оффлайновую задачу (например, про оригами), расклад был бы совершенно другим: опечатки можно было бы поймать за считанные секунды, и Python (по этому критерию) оказался бы наравне с компилируемыми языками. Но в этом году расклад был неудачным, и мы потеряли много времени и нервов. Да что там: оба кандидата на финальный сабмишен были забракованы именно из-за банальной ошибки с именами.

Урок (как мне кажется) в том, что Python нужно либо плотненько обкладывать тестами, либо же ограничивать его применение вещами, которые можно полностью проверить локально. Вместо тестов могут сгодиться type hints, mypy и ещё какие-нибудь чекеры и линтеры, но в этом я уверен чуть меньше.

На этом всё. Наш код можно найти на GitHub. Команда в этом году была настолько большой, что за всеми не уследишь, так что в дополнение к моему отчёту поглядите ещё и на мысли Форневера. Надеюсь, позже в README репозитория появятся ссылки и на другие отчёты.

Надеюсь увидеть тебя, дорогой читатель, и твою команду в лидерборде ICFPC 2021 ;)

1. предисловие;
2. день первый;
3. день второй;
4. день третий;
5. день четвёртый (это то, что вы сейчас читаете);
6. итоги и выводы.

20-е июля, понедельник, Z-15:30. Гоняемся за багами в модуляторе

Итак, большинство команды разошлось спать, и на боевом посту остались только мы с IngvarJackal. Он всё ещё возился с орбитами, а я принялся выяснять, почему мы неправильно модулируем команду выстрела.

Весь этот код был покрыт какими-никакими, но тестами: закодировали всё, что упоминалось в сообщениях инопланетян, дополнив проверками \(mod(dem(x)) \equiv x\) и \(dem(mod(x)) \equiv x\) для нескольких известных нам \(x\). На самом деле, модуляция списков — дело несложное. Там всего два правила:

ap cons x y  ==  11 (mod x) (mod y)
nil          ==  00

К примеру (числа не модулированы для читабельности):

[]  ==  00
[42]  ==  11 42 00
[42, 13]  ==  11 42 11 13 00
(42, 13)  ==  11 42 13

Именно с последними двумя примерами у нас и возникли проблемы. Дело в том, что Python-код вместо честного cons использовал встроенные списки. Следовательно, он не делал различий между списком двух элементов и парой двух элементов — а ведь они должны модулироваться по-разному! Этот баг частично маскировался демодулятором, который «срезал углы», игнорируя nil-ы.

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

Теперь у Codingteam есть пушки!

Стратегия пока что простая: на каждом ходу наш корабль стреляет в первого попавшегося противника. Всё. Этот подход будет держать нас в районе 25-го места лидерборда в течение всего следующего раунда.

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

Z-13:00. Только бы нам ночь простоять да день продержаться

Пока я возился, IngvarJackal успел выставить «стреляющего» бота против соперников, дать ему сыграть пару десятков игр, и откатиться обратно к не-стреляющему боту: похоже, из-за выстрелов корабль сильно перегревался, что увеличивало расход топлива и приводило к падениям на планету. Закончив с рефакторингом, я принялся смотреть чужие игры, чтобы понять, что происходит с температурой и топливом. А тем временем…

<xxx> конец стейджа
<xxx> мы на нулевом месте
<xxx> выше первого!

Мы ничего не знали про начальные параметры кораблей, были только догадки: первый параметр — количество топлива, второй — количество пушек, третий неизвестно, четвёртый — тоже неизвестно, но обязательно больше нуля. Я принялся выяснять, сколько пушек можно взять при 150-и единицах топлива. Для этого я делал сабмишен, в котором просил, например, 64 пушки. Ждал 5 минут, пока это сбилдится и пройдёт тесты. Когда тесты падали, я уменьшал количество пушек вдвое и снова отправлял сабмишен. Спустя пять минут опять корректировал количество, и так далее… Понадобилось полчаса, чтобы выяснить: при 150-и единицах топлива можно взять 44 пушки.

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

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

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

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

А эти самые противники тем временем научились создавать целый флот и подрывать корабли, нанося нам дополнительный урон. Я тоже так хочу!

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

Z-09:00. Конец очередного этапа оценивания

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

Оставив мне коротенький список TODO, IngvarJackal уходит вздремнуть, а я добавляю простенькую защиту от перегрева и берусь выяснять, как создавать больше кораблей. pink-snow тем временем научился загонять корабль в угол карты и удерживать его там; IngvarJackal надеялся использовать эту стратегию для корабля-защитника, чтобы соперникам сложнее было нас доставать.

Тут просыпаются ForNeVeR и portnov, и я быстренько пересказываю им всё то, что успел узнать про игровые механики. ForNeVeR решительно отказывается лезть в Python. Вместо этого он берётся доводить наш Haskell-код до состояния, пригодного к сабмиту; в этом ему помогают unclechu и portnov. Настроение подавленное: суббота была потрачена впустую, прогресс за воскресенье неутешительный, и теперь, похоже, придётся делать финальный сабмишен на Python.

Тем временем моя работа над дополнительными кораблями даёт первые плоды: мне удаётся «отпочковать» четыре новых, но они тут же падают, т.к. у них нет ни топлива, ни времени на коррекцию орбиты. Следующая задача: «отпочковывать» корабли только после выхода на стабильную орбиту. Модуль IngvarJackal-а содержит все необходимые вычисления, нужно только немного порефакторить (famous last words).

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

Просыпается Akon32 и берётся выяснять, как с помощью самоподрыва наносить противникам максимальный урон. Кажется, он даже успеет что-то написать, но мы это так и не смержим ☹

Незаметно подкрадывается Z-4:00, то есть начало предпоследнего раунда оценивания.

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

К Z-2:00 у нас не готово ничего нового, и мы сабмитим тот же код, что и в Z-9:00. Вся команда в мыле, все пытаются заставить «отпочковавшиеся» корабли хотя бы разок пальнуть по противнику. Лидерборд замерзает, мы на 37-м месте. Возможности сравнить своего бота с чужими больше нет; дальше придётся нащупывать прогресс вслепую.

В Z-00:26 выясняется, что в моей ветке баг: в перечне кораблей нет «отпочковавшихся». Не удивительно, что они не стреляют! В срочном порядке делаю cherry-pick исправления от IngvarJackal и пушу. Секунду спустя IngvarJackal пишет, что переименовал одну из переменных класса с состоянием игры. Аргх! Снова git cherry-pick, опять git push, скрещиваю пальцы.

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

Наступает час Z, мы делаем F5, и сайт организаторов генерирует уже знакомый нам мемасик (выделение моё):

ICFP Programming Contest 2020 has started 3 days ago, will end a few seconds ago

А дальше я просто цитирую чат:

[Z+00:02] <xxx> капец
[Z+00:02] <xxx> я в одном месте distance не поменял
[Z+00:02] <xxx> то есть все последующие сабмиты тоже багованные

Из-за банальной опечатки последние 9 часов работы улетают коту под хвост.

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

1. предисловие;
2. день первый;
3. день второй;
4. день третий (это то, что вы сейчас читаете);
5. день четвёртый;
6. итоги и выводы.

19-е июля, воскресенье, Z-30:17. Обратно в бой!

Перечитывая с утра командный чатик, обнаруживаю, что pink-snow написал ещё одну «вычислялку», в этот раз на Haskell. Она полностью следует псевдокоду организаторов и, что самое важное, работает. Теперь portnov и pink-snow выделяют её в отдельное приложение, а ForNeVeR модифицирует свой проект на C#, чтобы GUI при каждом клике вызывал Haskell и рисовал результат.

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

В Z-30:17 ForNeVeR наконец получает первую картинку:

Пообедав, он выкатывает новую версию GUI с масштабированием, и я отправляюсь исследовать Галактику — в смысле, galaxy.txt. После нескольких кликов по иконке галактики идёт десяток экранов, где нужно кликать в пересечение горизонтальной и вертикальной линий — некая калибровка. А потом отображается та самая картинка, которую недавно показали нам организаторы:

У некоторых рас есть «игры», и я погружаюсь в угадывание правил одной из них; portnov и Akon32, похоже, увлечены тем же самым. Один из только что проснувшихся сокомандников недоумевает:

<xxx> теперь у нас приложение на шарпе, а не на х-ле или питоне?
<yyy> Шарповый фронтенд с хаскельным бэкендом
<zzz> Да, планируем каждые восемь часов переписывать.

ForNeVeR и mr146 заняты улучшением GUI, а pink-snow помогает им, впиливая в «вычислялку» поддерживающие фичи.

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

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

<xxx> первые четыре уровня прошли, осталось ещё 8 или 9
<yyy> из туториала в игре? <_<
<zzz> нет :(
<zzz> В игру мы пока не залогинились
<xxx> да, тут капча
<xxx> инопланетная
<yyy> её нужно прокликать
<xxx> yyy: я так и делаю!

Из-за каких-то изменений в GUI и «вычислялке» появляется забавный баг: если дважды быстро кликнуть в GUI, то второй клик не будет проигнорирован. Вместо этого он будет применён после первого и, возможно, как-то повлияет на состояние игры. Мне флегматично советуют не кликать так быстро. Люблю нашу команду, такие отзывчивые люди, ух! ^_^

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

Z-24:00. Мы снова вспоминаем про IngvarJackal-а

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

Лидерборд в этом году формировался необычно: сутки, оставшиеся до конца соревнования, были разделены на несколько этапов. Очки за каждый этап суммировались и формировали итоговый рейтинг команды. Таким образом, нам нужно было уже сейчас зарабатывать баллы; выкатить решение в последний момент и попасть в середину рейтинга было бы практически невозможно. Поэтому я бросаю решать загадки galaxy.txt и присоединяюсь к IngvarJackal-у.

Игра на орбите происходит следующим образом: два корабля оказываются рядом с планетой. Один из них нападает, второй защищается. Игра длится 256 ходов (позже лимит подняли до 384-х). Задача атакующего — сбить защитника. Защитник, в свою очередь, просто пытается пережить нападение.

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

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

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

Я принялся за эксперименты, и чего только не попробовал:

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

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

• не стрелять на первом ходу, потому что это постоянно заканчивалось ошибкой;

• передавать в последнем параметре не одно число, а список из трёх (потому что именно столько показывал визуализатор от организаторов);

• вместо последнего параметра передавать три числа, которые я видел в визуализаторе организаторов.

Всё эти эксперименты закончились одинаково — ошибкой.

У остальных членов команды дела тоже шли с переменным успехом:

• pink-snow добавил какую-то обвязку для HTTP API;
• ForNeVeR, замучившись отлаживать (де)модулятор, посоветовал портировать тесты из Python на Haskell и отправился спать;
• portnov добавил в «вычислялку» send и даже добрался до какого-то из туториалов;
• unclechu, добавив каркас для сабмишенов на Haskell, тоже уснул;
• у mr146 возник какой-то форс-мажор, и он отвалился до конца соревнования.

Спустя почти шесть часов возни с командой выстрела мы с IngvarJackal наконец решили проверить алгоритм модуляции — и обнаружили, что команды кодируются неправильно! Мы должны передавать список команд, где каждая команда кодируется отдельным списком, но получается какая-то ерунда:

-- так должно быть
[4, 14, [[0, 1, [-1, 0]], [2, 1, [-16, -48], 4]]]
-- так кодируем
[4, 14, [[0, 1, [-1, 0]],  2, 1, [-16, -48], 4] ]

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

Какой баг я найду? Успеем ли мы хоть чего-то достичь за последние 16 с лишним часов? Читайте в отчёте о последнем дне соревнования ;)

1. предисловие;
2. день первый;
3. день второй (это то, что вы сейчас читаете);
4. день третий;
5. день четвёртый;
6. итоги и выводы.

18-е июля, суббота, T+19:00. Я возвращаюсь в строй

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

• pink-snow написал на Python «вычислялку» для galaxy.txt: программу, берующую на вход целый исходник на «космолиспе» и «выполняющий» её, аж пока не получит результат. В «вычислялке» нет мемоизации, так что работает она весьма неспешно. Никто не может понять код, и у всех чешутся руки переписать это на Haskell;
• собственно, ForNeVeR занят первым шагом по переписыванию: парсером из текста во входной тип reduce;
• mr146 экспериментирует на C# с модуляцией-демодуляцией, то есть преобразованием «космолиспа» в последовательность ноликов-единичек и обратно. Это нужно для того, чтобы реализовать send и пообщаться, наконец, с инопланетянами;
• portnov сделал два неудачных подхода к написанию «вычислялки» по аналогии с кодом на Python и теперь пребывает в некой прострации;
• unclechu дописал биндинги для HTTP и спит;
• остальные тоже спят.

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

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

Как любит повторять Максим Дорофеев, между срочным и важным человек всегда выбирает… понятное. Так что я решил заняться починкой сабмишенов. Как я уже упоминал во флешбеке про сбор команды, я никого не ввёл в курс дела касательно отправки результатов — а именно, о том, что весь наш код собирается в Docker-контейнере без доступа к Интернету. unclechu, не знавший об этом, добавил к нам в проект Servant и, таким образом, сломал сабмишены. Не знал он и о том, что сабмишены должны при запуске проделывать определённые действия. На устранение всех этих оплошностей у меня ушло два часа. Организаторы всё не мержили мой пулл-реквест с обновлённым Dockerfile, так что я перешёл к следующей задаче: помогать ForNeVeR-у с «вычислялкой».

Тут я снова проделал то же самое, что и вчера с pink-snow: убедил ForNeVeR-а, что «вычислялка» должна быть циклом, опирающимся на reduce для упрощения выражений. Я по-прежнему сопротивлялся всяким попыткам добавить подстановку тел функций в саму reduce. Саботировав таким образом написание рабочей «вычислялки» (во второй раз!), я ушёл обедать, а ForNeVeR продолжил бороться с зависаниями на каком-то тривиальнейшем кусочке «космолиспа».

IngvarJackal тем временем занимался демодулятором на Python. Это была, кажется, уже вторая реализация этого алгоритма. Впрочем, мы не видели в этом проблемы: нам казалось, что в условиях повышенной неопределённости будет даже лучше, если несколько под-команд будут одновременно исследовать задачу на удобных им языках. Я даже предположить не мог, насколько хорошо отобьётся эта наша ставка.

Всё это время я каждые полчаса делал тестовый сабмишен, чтобы знать, когда организаторы деплойнут новый образ с Servant. Сабмишены фейлились. Прошло три часа, а они всё фейлятся. И тут…

T+24:00, Z-48:00. Lightning division заканчивается

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

Как раз в это время проснулся unclechu, и мы с ним принялись выяснять, что же не так с сабмишенами. Оказалось, что деплой уже давно выполнен, и я, по всей видимости, не добавил в образ какие-то библиотеки: Servant-то там есть, а вот десятка невесть откуда взявшихся вспомогательных пакетов — нет. Провозившись с этим ещё полчаса и так и не поняв, как stack смог поставить Servant, но не поставить его зависимостей, я предложил вернуться на http-conduit; благо, нам нужны были только два эндпоинта. unclechu, честь ему и хвала, воспринял это предложение стоически и взялся переделывать.

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

И тут, в Z-47:30, организаторы наконец объясняют, как выиграть контест. Инопланетяне летят устраивать у нас на орбите звёздные войны. Мы обязаны выиграть. Для этого командам нужно писать ботов, управляющих космическими кораблями. Лучший бот сразится с пришельцами, прибытие которых ожидается к концу контеста, в час Z: 20-го июля в 13:00 UTC. Ну наконец-то хоть какая-то определённость!

Судя по новому документу организаторов, нам всё же нужно вычислить galaxy, и там будут нетривиальные картинки:

В связи с этим ForNeVeR передаёт работу над «вычислялкой» мне, а сам отправляется писать на C# GUI, в котором мы могли бы исследовать рисунки galaxy. Ко мне тут же присоединяется Портнов, и мы снова начинаем возиться. Высказываются идеи добавить мемоизацию, чтобы не пересчитывать одинаковые поддеревья. Проскакивает идея добавить в AST частично применённые функции. Мы ходим кругами, пробуя то да сё.

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

Z-44:00. Мы вспоминаем про IngvarJackal-а

Дела с «вычислялкой» на Haskell заходят в тупик, и я решаю глянуть на Python-код, который, вроде, работает. В процессе расспросов о том, как его вообще запустить, обнаруживается, что на Python есть рабочие модулятор и кусочек демодулятора, а IngvarJackal сидит без дела. У меня появляется первая правильная идея за весь день, и я быстренько организую ветку, из которой можно слать сабмишены на Python. IngvarJackal уходит мучить сервер организаторов тестами в надежде выяснить что-нибудь про HTTP API, пока мы доводим до ума «вычислялки» и GUI.

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

:1 = ap ap vec 2 5
:0 = ap ap cons :1 nil

ForNeVeR, сделав часть GUI, удаляется спать, а portnov пытается добиться какой-то ясности касательно наших дальнейших действий. Прошло уже 29 часов с начала контеста, а у нас до сих пор один балл и нет понимания того, как заработать ещё. Что это за туториалы, пройденные остальными командами? Как до них добраться и как их проходить? Как это связано с HTTP API и galaxy?

Проводим статус-митинг и выясняем, что:

• unclechu уже выпилил Servant и добавил новые функции для двух нужных нам эндпоинтов, а теперь планирует реализовать модулятор/демодулятор на Хаскеле;
• IngvarJackal чинит (де)модулятор на питоне, обкладывая его тестами, и готовится делать сабмишены для выяснения API;
• mr146 пишет «вычислялку» на C#, но готов бросить, как только мы доведём до ума код на Haskell;
• portnov пытается привести в чувство хаскелевскую «вычислялку»;
• остальные спят.

Таким образом получается, что у нас, якобы-Haskell-команды, действительно рабочий код есть только на Python, да и писали его вовсе не «старожилы», а «новички». Иронично!

Z-41:30. Codingteam на первом месте

Akon32 обращает наше внимание на лидерборд, и мы наблюдаем невероятное:

Один из тестовых сабмишенов IngvarJackal-а оказался настолько удачным, что «обыгрывал» соперников несмотря на то, что никакой игровой логики в нём не было: сабмишен выполнял все необходимые инициализации и бездействовал. Практически пустой скрипт на Python выводит Haskell-команду на первое место лидерборда.

Марш смерти

Тем временем мы с portnov пришли к выводу, что пора объединять «вычислялку» с reduce, потому что ни один из нас не может понять, как эти две функции между собой меняют дерево. Промежуточные результаты показали небольшое улучшение: «вычислялка» перестала виснуть на наших простых примерах, но по-прежнему отказывалась что-либо вычислять в galaxy.txt.

Я стал подозревать, что дело в рекурсии, и попытался закодировать простенький цикл вроде этого кода на Haskell:

fn0 = fn1 13
fn1 = \x -> if x == 0 then 42 else fn1 (x - 1)

Тут со мной случилось то, что Тонский назвал «принудительным ликбезом по лябмда-исчислению»: чтобы в fn1 использовать x дважды (в условии и в else-ветке), пришлось напрячь мозг и сообразить, как с помощью двойного применения S-комбинатора «вывернуть» выражение, чтобы оно принимало x как аргумент. Получился вот такой вот код на «космолиспе»:

:0 = ap :1 13
:1 = ap ap s ap ap s if0 ap t 42 ap ap b :1 dec

Он, естественно, не работал, и я потратил ещё чуток времени, добавляя в «вычислялку» на Python поддержку if0 и dec. Код же на Haskell успешно редуцировал выражение к «42», только если в :1 передавался ноль, единица или двойка. Если тройка и больше — вычисление шло вразнос, S-комбинатор в левой ветке не заменялся, и всё заканчивалось каким-то покорёженным выражением.

Мне понадобилось всего полчаса, чтобы сообразить, что, кодируя if0, я бездумно переписал правила из сообщений инопланетян, и эта функция не была определена для значений помимо нуля и единицы. Вот так вот всегда: тестируя руками, мечтаешь о юнит-тестах; написав юнит-тесты, мечтаешь о свойствах на QuickCheck…

Тем временем организаторы смилостивились над нами и выложили псевдокод интерпретатора «космолиспа». mr146 успешно реализовал его на С#, и мне следовало бы уже остановиться, но сонный мозг уже не способен был принимать решения. Пообщавшись с проснувшимся unclechu, я пришёл к выводу, что пора впиливать мемоизацию, а для этого нужно взять монаду State и держать в ней Map, где ключом будет Data.Unique.Unique, соответствующий выражению, а значение (само выражение) мы будем постепенно редуцировать. К счастью, тут меня начал рубить сон, и я принял второе и последнее верное решение за день — лечь спать.

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

1. предисловие;
2. день первый (это то, что вы сейчас читаете);
3. день второй;
4. день третий;
5. день четвёртый;
6. итоги и выводы.

Флешбэк: сбор команды

Я традиционно играю с ребятами из сообщества Codingteam, поэтому для начала пингонул парочку «старожилов». Но хотелось большего. Из года в год наша команда сталкивается с одной и той же проблемой: идей больше, чем рук. Забыв, что в дополнение к рукам идут ещё и головы, генерирующие идеи, я задался целью собрать для ICFPC 2020 как можно больше цодингтимовцев.

Мне удалось. В этом году Цодингтим представляли аж восемь человек — четыре «старожила» и четыре «новичка»:

1. Akon32, для которого это был уже четвёртый контест;
2. ForNeVeR, тоже выступавший далеко не впервые;
3. IngvarJackal, который не знает Haskell и собирался помогать советами;
4. mr146, коллега ForNeVeR-а, имеющий богатый опыт в куче других соревнований, но ещё не игравший в ICFPC;
5. pink-snow, тоже никогда не игравший в ICFPC, но уже здорово вложившийся в разгадку тизеров;
6. portnov, известный вам по моим предыдущим отчётам;
7. unclechu, единственный из всей команды пишущий на Haskell за деньги, но никогда не игравший в ICFPC;
8. я.

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

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

17-е июля, пятница, T+00:00. Старт

Нажимаем F5, и сайт организаторов генерирует мемасик (выделение моё):

Starts a few seconds ago on July 17, 2020 @ 13:00 UTC

А задания нет. Ну, ладно, нам не впервой — в былые годы сайт организаторов вообще ложился под наплывом интересующихся. Просто жмём F5.

T+00:05. Радиоастроном Иван Зайцев публикует очередной пост, мол, пришла целая пачка сообщений, помогайте расшифровывать. Оказалось, что организаторы ещё 25 минут назад твитнули, что отказываются от своей задачи в пользу Пеговки. А Пеговка призывает скооперироваться в Дискорде и понять, чего от нас хотят инопланетяне.

Настроение в командном чате обескураженное и подавленное:

<xxx> Сорян, а где код-то писать нужно?
<xxx> Кажется, тут просто какая-то угадайка? Или не?
<yyy> xxx: код можно писать для того, чтобы упростить декодирование. Но, похоже, пока что контест состоит в том, чтобы апдейтить сайт на readthedocs
<xxx> И кто выиграет в таком соцсоревновании?
<zzz> Иван Зайцев!

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

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

Просто сидел и злился. Если бы я играл один, на этом месте я бы сдался.

Но со мной была команда, и никто другой не ушёл. Спустя 45 минут мне немного полегчало, товарищи тоже сбросили с себя оковы первого впечатления, и мы взялись за дело. mr146 погрузился в декодирование новых сообщений, записывая мысли в гуглодок. Я взялся помогать, но нелюбовь к загадкам взяла своё, и я переключился на другую задачку.

pink-snow обнаружил, что за тестовый сабмишен выдают один балл. Надо заметить, что система сабмишенов пока что никак не вязалась с заданием: она ожидала POST-запроса по адресу и с параметром, указанными в командной строке. В ответ нам возвращали тот же параметр. Отказываясь верить в то, что задание ограничено разгадыванием сообщений, я трачу время на эксперименты с API: шлю туда 42, потом случайные числа, потом большие случайные числа. В ответ всегда приходит то, что было отправлено.

<я> xxx: рандомное чиселко уже 6 минут тестируется
<xxx> минору сломал пришельцев случайным числом
<xxx> межпланетарный дипломатический конфликт получился

Спустя полтора часа организаторы публикуют очередной пост, где сообщают, что Зайцев принимает некое огромное сообщение. Тем временем Портнов с N-ой попытки таки доносит мысль, что пора писать код. Из дешифрованных сообщений понятно, что перед нами некий «космолисп» — как бы Лисп, но вместо скобочек польская запись и оператор частичного применения. К примеру, вот так записывается список двух элементов [1, 2]:

ap ap cons 1 cons 2 nil

Также в «космолиспе» есть арифметика, комбинаторы SKI и целый ряд функций ввода-вывода: некоторые рисуют картинки, другие что-то отправляют инопланетянам и возвращают ответ. После короткого обсуждения становится понятно, что выражения легко разбираются в бинарное дерево, где ap являются узлами, а все остальные токены — листьями. Я сажусь писать функцию reduce, «редуцирующую» любое выражение в как можно меньшее.

Тем временем прошло уже четыре часа с начала контеста. ForNeVeR, начитавшись расшифровок сообщений, отправляется спать, а организаторы наконец-то публикуют соломинку, связывающую «загадки» с HTTP API: Swagger-документ описывает, как можно отправить инопланетянам сообщение и получить ответ. Становится очевидно, что пятнадцатое сообщение, описывающее команду send, напрямую мапится в это API. unclechu отправляется писать биндинги.

Спустя ещё сорок минут Зайцев наконец публикует то самое «огромное сообщение», galaxy.txt. На поверку оно оказывается тремястами килобайтами кода на «космолиспе», где главная функция называется galaxy. Несколько предыдущих сообщений описывают некий «протокол запуска», согласно которому в galaxy нужно передавать некие параметры, получать результат, который снова передавать в galaxy, и так далее.

Очевидно, что нам нужно как можно скорее запустить galaxy и понять, чего от нас хотят инопланетяне. Рождается несколько идей:

1. навалиться всем вместе и довести функцию reduce до рабочего состояния, реализовав всё необходимое для вычисления galaxy;

2. оттранслировать galaxy.txt в какой-нибудь «настоящий» Лисп, например, Scheme, и выполнить;

3. оттранслировать galaxy.txt в Haskell и выполнить.

Тут наконец-то «выстреливает» тот факт, что у нас большая команда: мы выбираем все опции сразу. mr146 и я занимаемся reduce, pink-snow берётся за трансляцию в Haskell, а portnov — в Racket. Спустя пару часов последние две идеи отпадают: GHC не осиливает вывести типы рекурсивных функций, а Racket считает, что все функции в galaxy.txt не принимают аргументов, и отказывается что-либо вычислять. Высказав напоследок идею о том, как это исправить, Портнов отправляется спать.

pink-snow берётся думать, как поверх ещё не дописанной reduce сделать функцию, которая вычисляла бы galaxy. Дело в том, что сама galaxy ничего толком не делает, она просто вызывает вспомогательную функцию, которая вызывает другие, и так для графа из 1338-и функций. reduce умеет упрощать только отдельные выражения, но не умеет подставлять в них тела других функций. Почему-то никому не приходит в голову просто расширить reduce, чтобы она покрывала и вызовы функций тоже. Вместо этого я убеждаю pink-snow написать цикл, в котором дерево будет сначала упрощаться с помощью reduce, а затем в него будут подставляться все константы — и так до тех пор, пока дерево меняется. Эта моя глупость нам ещё аукнется…

Пока pink-snow думает, мы с mr146 реализуем в reduce все используемые в galaxy функции, кроме рисования картинок и отправки HTTP запроса. Биндинги к HTTP ещё не готовы, поэтому я ухожу спать, оставив соратникам моё видение задач на следующий день:

1. объединив HTTP-биндинги от unclechu с функцией от pink-snow, получить полноценную «вычислялку» выражений;
2. протестировать её на нескольких сообщениях, результат которых нам известен заранее;
3. запустить наконец galaxy.txt.

Послушают ли меня коллеги? Удастся ли нам реализовать задуманное? Успеем ли мы — впервые в нашей истории! — что-то отправить на lightning round? Читайте в следующем посте :)

1. предисловие (это то, что вы сейчас читаете);
2. день первый;
3. день второй;
4. день третий;
5. день четвёртый;
6. итоги и выводы.

Погодите, а что такое ICFPC?

Это соревнование по программированию, приуроченное к ежегодной Международной конференции по функциональному программированию (International Conference on Functional Programming, ICFP). Вопреки названию, программировать можно на любом языке, не обязательно функциональном. Соревнование длится 72 часа, но также есть отдельный приз для тех, кто за первые сутки преуспеет больше остальных.

Основная «фишка» ICFP Programming Contest — это задачи. Они, мягко говоря, нетривиальные. Как правило, задачу придумывают академики, и корни её зачастую уходят в какую-нибудь зубодробительную область вроде оптимизационных проблем, теории алгоритмов, робототехники, орбитальной механики или чего-нибудь такого. Впрочем, за пару часов можно успеть нахвататься достаточно основ, чтобы хоть как-то поучаствовать в соревновании.

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

За две недели до контеста

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

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

Итак, за две недели до соревнования организаторы ретвитнули обращение своего знакомого учёного Ивана Зайцева, работающего на радиотелескопе в Пеговке (смотреть сто́ит ради одних только антуража и атмосферы):

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

Учёный создал страничку на ReadTheDocs (берегитесь — спойлеры!) и чат в Discord, поощряя будущих участников ICFPC работать вместе и помочь ему расшифровать послание. Народ быстро пришёл к выводу, что квадраты слева — это кодировка для чисел, показанных справа. На картинке мы видим ноль, единицу и так далее до восьми. Каждая точка внутри «квадрата» обозначает бит, и квадраты 3×3 кодируют четыре бита (диапазон чисел [3; 15]). Сразу же появилась гипотеза о том, как кодируются числа больше пятнадцати.

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

Таким образом, инопланетяне две недели описывали нам некий язык выражений, и напоследок предлагают пообщаться. Зачем всё это? Какое отношение это имеет к контесту? Согласитесь, сделать задачу продолжением тизеров было бы весьма убого и даже несколько нечестно: некоторые уже потратили две недели на «въезжание» в контекст и, таким образом, имели преимущество над вновь прибывшими.

О том, что произошло в первый день соревнования, читайте в следующем посте.