Технологии в Контуре

2021-07-11 16:54:36 - У нас какой-то ужасный Time to Market — мы фичу написали пять часов назад, а очки она начала приносить только сейчас
- Да ладно! Прикинь у продуктов в Контуре был бы такой Time to Market?

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

А еще мы собираем бонусы. И сами бонусы, и решения с бонусами. Но сабмиттить их пока рано.

С бонусами выходит вот какая история. Допустим, мы решили задачу 1, получили там бонус, с помощью этого бонуса идеально решили задачку 4 и залили это решение. Что произойдет, если мы зальем новое решение задачи 1, которое не берет бонус?

А ничего хорошего не будет, отменится наше идеальное решение задачи 4. А если задача 4 брала бонус, на котором завязано решение задачи 5…

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

А что будет завтра — интрига даже для нас. Открыть/Комментировать

2021-07-11 16:35:40 Смогли, двенадцатое место взято! Технические детали будут чуть позже. Открыть/Комментировать

2021-07-11 15:24:07 Открыть/Комментировать

2021-07-11 15:23:33 За 24 часа до конца контеста организаторы добавили флекс

Даже SUPERFLEX — последний новый бонус, позволяющий выбрать одно ребро (организаторы использовали формулировку up to one) и деформировать его на какую угодно величину. Ну то есть его растяжимость становится бесконечной. А еще добавили новых задач и по одному дополнительному бонусу в каждую существующую.

Мы же как раз заканчиваем адаптировать наш алгоритм под старые бонусы. GLOBALIST и WALLHACK уже почти побеждены, BREAK_A_LEG на очереди. Интересных алгоритмических деталей пока немного, основная работа была в обновлении нашего кода под новые условия.

Например, для получения бонуса нужно было научиться «закреплять» некоторую вершину на точке с бонусом и не рассматривать другие решения. А еще сохранять в базу всякую дополнительную информацию, чтобы отдельно хранить решения с разными условиями (с использованием бонусов, со взятием бонусов, с разными вариантами использования бонусов и так далее). Ну и, разумеется, использование бонусов влияет на работу функцию оценки — GLOBALIST изменяет оценку растяжимости, WALLHACK добавляет дополнительное условие в оценку «влезаем ли мы в дыру?» и так далее.

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

2021-07-11 12:12:29 - «Ваня второй раз переписывает стейт, очень удобно (будет)»
- «Как переписывает? Мы же написали идеальный!»

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

А еще в задачах начало появляться по несколько доступных бонусов. И по несколько бонусов, которые можно взять, и по несколько бонусов, которые можно использовать. Хотя на последнее наложено ограничение, больше одного бонуса в задаче использовать нельзя. В любом случае, вариативность решений еще немножко подросла. Теперь мы можем решить, взяв первый бонус, взяв второй, взяв оба, ни взяв ни одного, взяв первый бонус с использованием Глобалиста, взяв оба бонуса с использованием BREAK_A_LEG, не беря бонусы с использованием WALLHACK…

Можно еще не решить в принципе. У нас есть несколько нерешенных задачек, так что одновременно с дотачиванием модели и алгоритма мы решаем кое-какие старые задачки. И придумываем новые мутаторы.

До конца контеста 27 часов — посмотрим, что еще интересного мы успеем накодить. Открыть/Комментировать

2021-07-10 23:47:10 В чате команды новые условия и поступающие идеи проиллюстрировали следующим образом Открыть/Комментировать

2021-07-10 23:35:07 Открыть/Комментировать

2021-07-10 23:34:53 Бонусы — это сложно.

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

Вот только пользоваться этими бонусами мы пока не умеем.

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

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

Что делать? Долго и сложно переписывать это все. Тем и заняты, параллельно ковыряя отдельные задачки и внося мелкие улучшения в другие куски системы. Открыть/Комментировать

2021-07-10 16:47:53 А вот так выглядит совместная работа всех перечисленных мутаторов на примере решения первой задачи Открыть/Комментировать

2021-07-10 16:47:14 Шестой делает подобное в больших масштабах. Он ищет некоторые участки фигуры, которые можно отразить не влияя на растяжение, и также пытается использовать это для решения задачи.

Простейший вариант такого участка — точка, соединенная только с двумя другими точками Открыть/Комментировать