Пока результат нам нравится. Умеем решать все задания, улучшаем алгоритмы, без большого энтузиазма рассчитываем на победу в 24-часовом раунде, готовим мощный задел на борьбу в полном контесте. Всё по плану: https://twitter.com/backendsecret/status/1142025169797619712

34 часа с начала контеста. Пора написать что-нибудь ещё. Надеюсь, никого не разбужу этим постом.

24-часовой раунд закончился 10 часов назад. Как положено, примерно за полтора часа до его окончания и перед самой заморозкой лидерборда синхронно произошли два события: команда «All your lambda are belong to us» отодвинула нас на второе место; мы поняли, как радикально улучшить наши алгоритмы и запустили массовый пересчёт всех решений.

Следующий час прошёл в напряжённом разглядывании дашборда с результатами пересчёта, мануально-голосовой координации пересчёта на ноутбуках, доступных по RDP и SSH рабочих станциях, а также прочих приятных виртуалках с 24-ядрами. Довольно быстро утомились от переговоров вида «Запусти жадного с палкой для задач от 150 до 200! У кого дип-волк считается? Стьюпиды досчитались или нет?». Однако вовремя одёрнули себя, когда начали всерьёз обсуждать, что пора завести Zookeeper для распределённой блокировки, ну или хотя бы Raft между «вычислительными нодами» поднять. Решили, что пока обойдёмся голосом, а припрёт — сделаем аренды с TTL поверх MongoDB.

Вот так боролись с нервами, сдавая наши лучшие решения под конец первых суток. Пройдут недели и узнаем, смогли вырваться обратно на ПЕРВОЕ МЕСТО или нет

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

Чуть лучший алгоритм мы назвали глупым (stupid). Ходит «по стеночке», стараясь заполнять области рядом с уже заполненными и не меняя направление без нужды. Получается не сильно хорошо:

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

Пока deep-walk разбивает подвалы на кластера динамически, на лету. Думаем о том, чтобы разбить подвалы на «оптимальные» кластеры и просчитать наилучший путь обхода заранее. Должна же быть польза от датасаенса:

Кажется, мы на правильном пути:

А вот главное достижение нашего роботостроения — это пока что жутко секретный алгоритм random-walk-2/100/True/zako с оценочной функцией EstimatorZakoulochki от Паши @xoposhiy. Новый эстиматор оптимизирует обход тёмных углов, экономя массу ходов. Сейчас запустили пересчёт всех решений с «закоулочками», результаты неплохие

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

Вероника @Aminopyrodin успевает не только наводить красоту на дашборде, но и делать крутые фоточки, и шутить шутки во внутреннем чатике. Попрошу её написать завтра гостевой пост в этот канал :)

Ладно, ещё услышимся. А пока закончу актуальной шуткой от Паши @xoposhiy, который глубоко в отладке EstimatorZakoulochki: