Конкурс по программированию: Торговля

Компания Hola вновь объявляет конкурс по программированию! Победителей ожидают призы:

1. Первое место: 3000 USD.
2. Второе место: 2000 USD.
3. Третье место: 1000 USD.
4. Жюри может присудить по своему усмотрению специальный приз в 400 USD.
5. Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите половину суммы приза (разумеется, не в ущерб награде победителя). За одного победителя такую награду может получить только один человек — тот, кто отправил ссылку первым.

Авторы интересных решений будут приглашены на собеседования.

Правила

Условия конкурса на английском языке размещены на GitHub. Ниже — перевод на русский язык.

• Отправляйте решения с помощью этой формы. По электронной почте решения не принимаются.
• Решения принимаются до 20 июля 2018, 23:59:59 UTC.
• Предварительные результаты будут опубликованы 27 июля 2018, а окончательное объявление победителей — 3 августа 2018.
• Можно отправлять решения многократно, но от каждого участника будет рассмотрено только самое последнее решение, отправленное до окончания срока приёма работ.
• Для тестирования мы будем использовать Node.js v10.4.1 (текущая версия на момент публикации). Можно использовать любые возможности языка, поддерживаемые интерпретатором в стандартной конфигурации.
• Весь код решения должен находиться в единственном файле на JS.
• Решение должно быть на JS. Если Вы предпочитаете CoffeeScript или подобные языки, необходимо оттранслировать решение в JS перед отправкой.
• Если Ваш JS-файл — продукт генерации, минификации и/или компиляции с других языков вроде CoffeeScript, пожалуйста, приложите архив с исходниками, а также, желательно, описанием подхода. Содержимое этого архива будет опубликовано, но мы не будем его тестировать.
• Нельзя загружать никаких модулей, даже тех, что входят в стандартный комплект Node.js.
• Нам нужно знать Ваше полное имя, но если Вы хотите, мы опубликуем вместо него псевдоним. Мы сохраним Ваш адрес электронной почты в тайне.
• Нынешние и бывшие сотрудники Hola и их ближайшие родственники могут принимать участие лишь вне конкурса, не претендуя на призы.
• Задавайте вопросы по условию задачи в комментариях к этой публикации или по электронной почте.

Торговля

Допустим, у нас есть книга, две шляпы и три мяча. Вы и ещё один участник должны решить, как разделить это добро между вами двоими. Для вас книга имеет ценность $4, каждый мяч — $2, а шляпы ценности не имеют. Для партнёра эти же объекты могут иметь другую ценность, но вам известно, что все объекты вместе для него ценны настолько же, насколько и для вас — в данном случае это $10.

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

Вот пример того, как могут пройти переговоры:

1. Вы: Я хочу книгу и два мяча; ты получишь один мяч и обе шляпы.
2. Партнёр: Не согласен. Я хочу все мячи и одну шляпу; ты получишь книгу и одну шляпу.
3. Вы:Не согласен. Я хочу книгу и один мяч; ты получишь два мяча и обе шляпы.
4. Партнёр: Согласен.

Вам это не было известно, но для партнёра ценность предметов была такой: по $2 за мяч, по $2 за шляпу, книга не имеет ценности. Соглашение принесло $6 вам и $8 партнёру.

В общем случае есть два или более типов объектов и целое положительное число объектов каждого типа. Ценность каждого типа объектов для каждого из партнёров — целое неотрицательное число. Суммарная ценность всех объектов для обоих партнёров одинакова, хотя ценности отдельных предметов разнятся. Предложение о разделе должно распределять между партнёрами все объекты без остатка; отдельные объекты не дробятся.

Ваша задача — написать скрипт, стремящийся заключить сделку с максимально возможной ценностью (для себя).

Решения

Решение представляет собой модуль Node.js без зависимостей. Экспорт модуля должен представлять собой класс:

module.exports = class {
    constructor(me, counts, values, max_rounds, log){
        ..
    }
    offer(o){
        ...
    }
}

Экземпляр этого класса будет создан один раз и использован в течение сеанса переговоров. Конструктору передаются следующие аргументы:

• me — 0, если ваша очередь первая, или 1, если вторая.
• counts — массив целых чисел, содержащий количество объектов каждого типа. Он содержит от 2 до 10 элементов.
• values — массив целых чисел такой же длины, что и counts, описывающий ценность объекта каждого из типов для вас.
• max_rounds — число раундов переговоров (каждый раунд состоит из двух реплик).
• log — функция, которую можно вызывать для отладочного вывода (console.log работать не будет).

Метод offer вызывается каждый раз, когда наступает ваша очередь. Его аргумент o — это массив целых чисел такой же длины, как counts. Аргумент описывает, сколько объектов каждого из типов вам предлагает партнёр. Если ваша очередь первая, и это самый первый раунд, то o равно undefined.

Метод offer должен вернуть undefined, если вы принимаете предложение (кроме случая, когда o равно undefined). В противном случае он должен вернуть массив целых чисел такой же длины, как counts, описывающий, сколько объектов каждого типа вы хотите оставить себе. Обратите внимание, что и аргумент o, и возвращаемое значение offer описывают раздел предметов с вашей точки зрения.

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

Окружение, в котором запускается скрипт, не предоставляет возможности накопления информации между сеансами.

В файле example.js приведён простой пример скрипта, удовлетворяющего правилам. Он принимает любое предложение, по которому ему отходит не менее половины суммарной ценности всех объектов; в противном случае он просто требует для себя все объекты, имеющие ненулевую ценность. Скрипт также демонстрирует применение функции log.

Тестирование

Скрипт haggle.js позволяет организовать переговоры между двумя участниками-людьми, между человеком и скриптом или между двумя скриптами. Запустите его с параметром --help, чтобы узнать обо всех его возможностях.

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

Для окончательного тестирования мы будем использовать параметры тестовой системы по умолчанию: 3 типа объектов, от 1 до 5 объектов каждого типа, суммарная ценность всех объектов для каждого из партнёров $10, лимит в 5 раундов. Мы рекомендуем писать решения так, чтобы они поддерживали любую комбинацию параметров, которую поддерживает тестовая система.

Тестирование будет происходить на виртуальном сервере c3.large (см. аппаратные характеристики по ссылке) на Amazon AWS под управлением Ubuntu 14.04 (amd64). Решения будут тестироваться одна пара за другой при отсутствии прочей нагрузки на машине.

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

Переговоры онлайн

Мы предоставляем сервер, который позволяет вашему скрипту вести переговоры с другими участниками. Он устроен наподобие серверов онлайн-игр: можно подключиться к «арене», и сервер организует сеанс между вами и другим участником.

Изначально мы создали одну арену с настройками по умолчанию (3 типа объектов, от 1 до 5 объектов каждого типа, суммарная ценность всех объектов для каждого из партнёров $10, лимит в 5 раундов). Эта арена не контролирует предел времени в 1 секунду, чтобы дать возможность и людям участвовать вручную. Вот адрес арены:

wss://hola.org/challenges/haggling/arena/standard

Используйте haggle.js, чтобы подключаться к серверу как участник-человек или же со своим скриптом. В этом режиме нужно также передавать параметр командной строки --id: это уникальный идентификатор, по которому система будет отслеживать успехи вашего скрипта. Мы рекомендуем использовать в качестве идентификатора ваш адрес электронной почты плюс случайную строку. Мы не будем публиковать идентификаторы. Позже мы запустим «живую» таблицу лучших результатов, где будут приведены средние исходы сделок и хэши идентификаторов.

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

Если ваш скрипт работает, мы рекомендуем, чтобы он постоянно участвовал в онлайн-сеансах, например, с помощью такой команды UNIX shell:

while true; do node haggle.js --id me@example.com:1234abcd myscript.js wss://hola.org/challenges/haggling/arena/standard; done

Отправка решений

Для отправки решений пользуйтесь формой на нашем сайте. По электронной почте решения не принимаются!

Поскольку код решений часто бывает сгенерированным, минимизированным или оттранслированным с другого языка, форма содержит также поле для отправки архива с исходными тестами. Если код сгенерирован, включите туда генератор; если он минимизирован, включите исходную версию; если код переведён с CoffeeScript или другого языка, включите код на том языке, на котором он написан. Желательно также включить в архив файл README с кратким описанием подхода к решению (по-английски). Архив должен быть в формате tar.gz, tar.bz2 или zip. Содержимое архива будет опубликовано, но не будет протестировано (мы тестируем только JS-файл, который вы отправляете вне архива).

Максимальный размер JS-файла установлен в 64 МиБ. Это произвольно выбранная цифра, которая существует в основном для того, чтобы чьё-нибудь «решение» одномоментно не заполнило нам диск. Если ваше решение правда больше 64 МиБ, напишите нам, и мы увеличим ограничение.

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

Желаем удачи всем участникам!

Автор: feldgendler

Источник