June 27th, 2019

ICFPC 2019

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

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

Очень любопытно посмотреть, чего ты стоишь. В голове-то ты мог много себе про себя нафантазировать, а тут вот объективная реальность, ладдер, и ты либо можешь компьютер заставить делать что ты хочешь, либо не можешь. Никаких «если бы», никаких «возможно, наверное, мне кажется». Мы довольно посредственно выступили (на момент закрытия 29 место из 142 участвовавших, в лучший свой момент были на пятом).

Исторический скриншот. Дальше мы сильно сдали
Исторический скриншот. Дальше мы сильно сдали

Участвовали втроем, я в первый раз. Как я понял, средний размер команды ~5 человек, не редкость и восемь встретить. Втроем у нас довольно хорошо делились области ответственности, было бы больше появился бы организационный оверхед (как мне кажется). Восемь человек я бы вообще офигел менеджить и вообще ничего бы не написал, наверное. С другой стороны, больше рук – можно попробовать больше подходов. Можно вложиться в инфрастуктуру. Наверное.

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

Собери бонусы, закрась лабиринт
Собери бонусы, закрась лабиринт

Clojure, несмотря на все плюсы языка высокого уровня и быстрого iteration time, по ощущениям подошла довольно плохо. Потому что все упирается в перформанс. Можно сколько угодно рассуждать про «глобальные оптимизации против локальных», ненавидеть байтоебство, мыслить как стратег с высоты птичьего полета и гордиться тем, что не знаешь, как устроен компьютер, но это все и в императивных языках можно делать. Они же не отнимают способности мыслить и планировать. Да, механика записи мысли чуть более многословна, ну зато оно того стоит. Плюс за три дня вы разницы может и не заметите даже. А вот по перформансу заметите, еще как. Как ни крути, а команда, которая обсчитает за условное время X в два раза больше вариантов, чем ее конкурент, будет в топе выше. КАК НИ КРУТИ. Больше здесь строго лучше. Либо больше итераций, больше вариантов попробовать, либо решения будут более глубокими, а значит и очков принесут больше.

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

Выглядит красиво, жаль вся эта мощь обслуживает всякое говно вроде lazy sequences, primitive boxing, high-order functions вместо того, чтобы решать задачу
Выглядит красиво, жаль вся эта мощь обслуживает всякое говно вроде lazy sequences, primitive boxing, high-order functions вместо того, чтобы решать задачу

Сейчас я думаю, что даже если бы мы выбрали просто Java с unboxed примитивами и примитивными массивами, было бы качественно лучше. C++/OCaml/Rust может быть дали бы еще 1,5-2 раза прирост, но это уже не изменило бы ситуацию качественно. Но может и нет, цифры так, с потолка.

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

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

Кстати, многие ошибки, которые все-таки у нас были, были связаны с подстановкой переменной того же типа, где никакая система типов бы никого не спасла. Ну оно и не удивительно, когда у тебя большая часть программы, процентов 90, гоняет инты направо и налево. Это же алгоритмы.

не с этого хакатона, но смысл такой же
не с этого хакатона, но смысл такой же

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

лабиринты, генерируемые нашим алгоритмом, имели хорошо узнаваемый вид
лабиринты, генерируемые нашим алгоритмом, имели хорошо узнаваемый вид

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

Пилу нужно точить. Как бы ни казалось, что три дня уж без удобств можно прожить, удобства все-таки решают. Мы очень страдали от отсутствия визуализатора. Организаторы предлагали готовый, но в браузере (на ScalaJS кстати), и это не оч удобно было (для каждого запуска нужно было накликать мышкой и выбрать два раза через диалог выбора файла два файла).

Визуализатор организаторов
Визуализатор организаторов
ух как же меня бесило выбирать эти файлы каждый раз!
ух как же меня бесило выбирать эти файлы каждый раз!

Самое большое, чего там не хватало — пошагового реплея, перемотки назад и вперед, ну и доп информацию тоже иногда хочется какую-то вывести. Как разбился лабиринт, что думает бот, такое. Я написал в какой-то момент простой визуализатор через println и clear screen, он даже мультики показывал типа, но хотелось бы чего-то более удобного и универсального.

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

Приходить надо было подготовленным. У ребят, например, из контура, была инфраструктура заготовлена: сервера, гоняющие задачи, сбор ответов, дашборд, сравнение. Мы этого, конечно, не знали, у нас в лучшем случае запустил программу на ноуте — в терминал вывалился результат. Пик инфраструктуры.

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

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

Как правильно распределять силы я пока не понял. Я выложился по максимуму в первый день (до 6 утра, на следующий встал в 11) чтобы как можно больше впихнуть в Lightning Round (первые 24 часа). В результате весь второй день был как в тумане и работалось как на автопилоте. В третий зашли нормально, я переписал алгоритм даже, но тоже было очень тяжело. Возможно, здоровый сон каждый день (ну ок, кроме последнего) суммарно дал бы больше эффективности за три дня, чем такое.

Перерыв на обед
Перерыв на обед

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