По моему опыту и тикету github.com/angular/angular/issues/30497 метод 5 работать не будет в продакшн-билде — ngOnDestroy, объявленный в дектораторе, не вызывается при AoT компиляции, если исходный компонент не содержит данный метод.
Как упомянуто в статье (может стоит выделить более жирным начертанием?) методы take/takeWhile приводят к утечкам памяти, если необходимые условия для отмены подписки не соблюдены. Простейший пример — использование filter до, либо switchMap/mergeMap после.
Если нужно корректно отписаться и при этом избежать утечек памяти — то async, unsubscribe и takeUntil (при условии, что тот стоит после всех остальных условий прямо перед подпиской).
Типо того. Но, боюсь, что текущие ограничения сильно уменьшают шансы «на корпус вперёд». Мне больше понравилась площадка LARGE, там было интереснее торговаться. Хотя практически все решения сводятся к конечной логике, которую проще реализовать без использования нейронных сетей и супер алгоритмов.
1. Исключаем все предметы с нулевой ценностью для нас, т.к. смысла торговаться за них нет, будем отдавать их сразу.
2. Из оставшихся предметов генерируем все возможные комбинации, группируем по суммарной ценности (например, все комбинации, которые дают $10, $9, $8...), сортируем группы в порядке убывания
3. Начинаем торговаться, начиная с максимально выгодных комбинаций
Основной момент тут — ограничение количества ходов. Т.е. для того, чтобы уменьшить количество торгов, надо предлагать максимально выгодное предложение для меня и, в то же время, максимально выгодное для противника.
Для уменьшения количества торгов нужно примерно оценить стоимость товар для противника, и выкинуть из торгов комбинации, манипулирующие товарами, не имеющими стоимости для противника — т.е. для таких товаров мы всегда требуем всё.
После этого сортируем комбинации внутри ценовой группы и отдаём, начиная с самых выгодных для противника, и заканчивая самыми невыгодными (по нашей оценке).
Оценку производим по встречным предложениям.
Почти наверняка первым ходом противник предложит товары, не имеющие для него ценности, т.е. 0. Затем будет торговаться, предлагая товары, имеющие малую стоимость, затем большую и большую, вплоть до товара с максимальной стоимостью.
Возможны варианты, когда для противника все товары имеют стоимость, поэтому первым ходом противник не отдаст ничего (это ожидаемый жадный ход), либо противник отдаст только один товар с минимальной стоимостью. Если товаров с минимальной стоимостью несколько, то это можно определить. Если товар с минимальной стоимостью только один, то отличить его от товара с нулевой стоимостью не получится (но этот случай исключение).
Дальше мы назначаем примерную стоимость для всех товаров, которые предложил противник от 0.001 до 0.999 (0 — только для товаров из первого предложения, 1 и более назначать нельзя, чтобы уменьшить вероятность ошибок и неверных предложений от противника). Если были оценены не все товары, то оставшиеся товары оцениваются по следующему алгоритму — все оценки товаров от 0.001 до 0.999 приравниваем 1, умножаем на их количество и отнимаем от общей суммы. Остаток после вычислений делим нацело на каждый из типов товаров.
Например, у нас 4 позциции товаров [A, B, C, D] с количеством [2, 3, 1, 2] и общая сумма $12.
Предложения, поступившие от оппонента [0, 0, 0, 1], [0, 0, 0, 2], [0, 0, 1, 0].
По логике, описанной выше, если бы первым предложением было [0, 0, 0, 2], то товар D получил бы нулевую стоимость. Но т.к. первым предложением была часть товара, поэтому стоит предположить, что товар имеет не нулевую ценность (но нельзя сказать, что он стоит 1). Поэтому товару D присваиваем 0.001, а товару C — 0.002. Теперь надо вычислить примерную стоимость товаров A и B. Увеличиваем минимальную стоимость товаров C, D до 1, умножаем на количество, получаем $3.
$12 — $3 = $9. Именно столько приходится на оставшиеся два товара по нашим предположениям. У нас осталось 2 товара A и 3 товара B. У товара A предполагаемая стоимость будет 9 / 2 = $4, у товара B ~ 9 / 3 = $3.
Итого примерная оценка товаров противника для сортировки будет [4, 3, 0.002, 0.001]
Переоценка товаров происходит после каждого предложения от оппонента, как и пересчёт порядка комбинаций внутри ценовых групп.
Было бы интересно посмотреть на статистику торговли с собой — насколько скрипт способен торговаться против себя же. В таких случаях скрипты «хочу всё, отдам только ненужное» будут по нулям (за редкими значениями, когда «ненужное» окажется тем самым, на что сам же бот в таком случае согласится).
А то как-то грустно смотреть на одностороннюю торговлю, когда свой бот торгуется, а противник всегда выставляет одно и то же предложение.
Теоретический минимум — 5 забегов, даже если бы был таймер, чтобы протестировать всех лошадей. Максимум при последовательном переборе — 11, если из каждого забега оставлять тройку лидеров и заменять последних двух лошадей свежими: 5-2-2-2-2-2-2-2-2-2-2. У меня получилось минимум 9 забегов.
Конкурс был интересным и увлекательным. Победителям — заслуженные поздравления, организаторам — большое спасибо.
Д/З — работа над ошибками и изучение решений в ожидании следующего конкурса :)
Идеальное решение — это хранить весь словарь, что довольно проблематично, учитывая ограничение в размере данных. Поэтому все решения заточены под текущий генератор, чьи-то больше, чьи-то меньше. Если бы генератор был другим, и решения были бы другими.
Сложно предусмотреть все ситуации, поэтому организаторы оставили для себя возможность определять победителя наиболее объективным способом. Альтернатива этому — добавить пункт в правила, что условия конкурса могут меняться при нахождении изъянов в оригинальных правилах. Имхо, первый вариант лучше, чем второй.
Имхо, организаторы конкурса в курсе этого изъяна в тестировании. Для того, чтобы подобное решение не сработало, достаточно ограничить количество блоков со словами, или можно запустить несколько тестов используя фиксированное количество блоков, затем вычислить среднее (что немного не совпадает с условиями запуска функции init только один раз).
Выглядит как читерство, но идея классная, жаль сам не додумался :)
В голову приходит только ограничение максимального количества блоков, чтобы не дать собрать статистику, либо действительно перезапускать init через какой-то интервал.
Первым делом нужно отсечь бессмысленное 's на конце слов и получим сокращение словаря до 490822. Затем можно отсечь все слова, содержащие апостроф — их всего несколько сотен (~350, false-negative 0,07%) против 100 тыс на 1 млн неверных слов (~10%), итого получаем словарь вообще без апострофов. Две простейшие регулярки дают офигенный профит.
Я думал, что 82% достижимо, но так и не смог добраться — остановился на 81%. А миллион тестовых слов — это 10.000 блоков? Или всё же 1 миллион уникальных слов?
Как упомянуто в статье (может стоит выделить более жирным начертанием?) методы take/takeWhile приводят к утечкам памяти, если необходимые условия для отмены подписки не соблюдены. Простейший пример — использование filter до, либо switchMap/mergeMap после.
Если нужно корректно отписаться и при этом избежать утечек памяти — то async, unsubscribe и takeUntil (при условии, что тот стоит после всех остальных условий прямо перед подпиской).
1. Исключаем все предметы с нулевой ценностью для нас, т.к. смысла торговаться за них нет, будем отдавать их сразу.
2. Из оставшихся предметов генерируем все возможные комбинации, группируем по суммарной ценности (например, все комбинации, которые дают $10, $9, $8...), сортируем группы в порядке убывания
3. Начинаем торговаться, начиная с максимально выгодных комбинаций
Основной момент тут — ограничение количества ходов. Т.е. для того, чтобы уменьшить количество торгов, надо предлагать максимально выгодное предложение для меня и, в то же время, максимально выгодное для противника.
Для уменьшения количества торгов нужно примерно оценить стоимость товар для противника, и выкинуть из торгов комбинации, манипулирующие товарами, не имеющими стоимости для противника — т.е. для таких товаров мы всегда требуем всё.
После этого сортируем комбинации внутри ценовой группы и отдаём, начиная с самых выгодных для противника, и заканчивая самыми невыгодными (по нашей оценке).
Оценку производим по встречным предложениям.
Почти наверняка первым ходом противник предложит товары, не имеющие для него ценности, т.е. 0. Затем будет торговаться, предлагая товары, имеющие малую стоимость, затем большую и большую, вплоть до товара с максимальной стоимостью.
Возможны варианты, когда для противника все товары имеют стоимость, поэтому первым ходом противник не отдаст ничего (это ожидаемый жадный ход), либо противник отдаст только один товар с минимальной стоимостью. Если товаров с минимальной стоимостью несколько, то это можно определить. Если товар с минимальной стоимостью только один, то отличить его от товара с нулевой стоимостью не получится (но этот случай исключение).
Дальше мы назначаем примерную стоимость для всех товаров, которые предложил противник от 0.001 до 0.999 (0 — только для товаров из первого предложения, 1 и более назначать нельзя, чтобы уменьшить вероятность ошибок и неверных предложений от противника). Если были оценены не все товары, то оставшиеся товары оцениваются по следующему алгоритму — все оценки товаров от 0.001 до 0.999 приравниваем 1, умножаем на их количество и отнимаем от общей суммы. Остаток после вычислений делим нацело на каждый из типов товаров.
Например, у нас 4 позциции товаров [A, B, C, D] с количеством [2, 3, 1, 2] и общая сумма $12.
Предложения, поступившие от оппонента [0, 0, 0, 1], [0, 0, 0, 2], [0, 0, 1, 0].
По логике, описанной выше, если бы первым предложением было [0, 0, 0, 2], то товар D получил бы нулевую стоимость. Но т.к. первым предложением была часть товара, поэтому стоит предположить, что товар имеет не нулевую ценность (но нельзя сказать, что он стоит 1). Поэтому товару D присваиваем 0.001, а товару C — 0.002. Теперь надо вычислить примерную стоимость товаров A и B. Увеличиваем минимальную стоимость товаров C, D до 1, умножаем на количество, получаем $3.
$12 — $3 = $9. Именно столько приходится на оставшиеся два товара по нашим предположениям. У нас осталось 2 товара A и 3 товара B. У товара A предполагаемая стоимость будет 9 / 2 = $4, у товара B ~ 9 / 3 = $3.
Итого примерная оценка товаров противника для сортировки будет [4, 3, 0.002, 0.001]
Переоценка товаров происходит после каждого предложения от оппонента, как и пересчёт порядка комбинаций внутри ценовых групп.
Всё просто
А то как-то грустно смотреть на одностороннюю торговлю, когда свой бот торгуется, а противник всегда выставляет одно и то же предложение.
Д/З — работа над ошибками и изучение решений в ожидании следующего конкурса :)
В голову приходит только ограничение максимального количества блоков, чтобы не дать собрать статистику, либо действительно перезапускать init через какой-то интервал.
Я думал, что 82% достижимо, но так и не смог добраться — остановился на 81%. А миллион тестовых слов — это 10.000 блоков? Или всё же 1 миллион уникальных слов?