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

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

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

UPDATE: Канал в Telegram для обсуждения конкурса: @hola_challenge_haggling

Правила

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

Торговля

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

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

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

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

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

Решения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

while true; do node haggle.js --id [email protected]:1234abcd myscript.js wss://hola.org/challenges/haggling/arena/standard; done

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

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

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

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

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