Programming Contest: Trade

    UPDATE: Announcements for members .
    UPDATE 2: Intermediate results and announcements . Hola

    company again announces a programming contest! Winners will receive prizes:

    1. First place: 3000 USD.
    2. Second place: 2000 USD.
    3. Third place: 1000 USD.
    4. The jury may award at its discretion a special prize of 400 USD.
    5. If you send someone a link to this contest, putting our address in the CC, and this person will take the prize, you will receive half the amount of the prize (of course, not to the detriment of the winner's award). For one winner, only one person can receive such an award - the one who sent the link first.

    Authors of interesting decisions will be invited for interviews.



    rules


    Competition terms in English are posted on GitHub . Below is a Russian translation.
    • Submit solutions using this form . No decision is made via email.
    • Decisions are made until July 20, 2018 , 23:59:59 UTC.
    • Preliminary results will be published on July 27, 2018 , and the final announcement of winners - August 3, 2018 .
    • You can send solutions repeatedly, but each participant will only consider the most recent decision sent before the deadline for accepting work.
    • For testing, we will use Node.js v10.4.1 (the current version at the time of publication). You can use any language features supported by the interpreter in the standard configuration.
    • All solution code should be in a single JS file .
    • The solution should be on JS. If you prefer CoffeeScript or similar languages, you need to broadcast the solution to JS before sending it.
    • If your JS file is a product of generation, minification and / or compilation from other languages ​​like CoffeeScript, please attach the archive with the sources, and also, preferably, with a description of the approach. The contents of this archive will be published, but we will not test it.
    • You cannot load any modules , even those included in the standard Node.js package.
    • One participant can use only one email address to send a solution. Sending a set of solutions that are in "collusion" from different addresses is prohibited; all decisions involved in such a scheme will be disqualified.
    • We need to know your full name, but if you want, we will publish a pseudonym instead. We will keep your email address confidential.
    • The current and former Hola employees and their closest relatives can take part only out of the competition, without claiming for prizes.
    • Ask questions about the problem statement in the comments to this publication or by e-mail .

    Trade


    Suppose we have a book, two hats and three balls. You and another member must decide how to divide this good between the two of you. For you, the book has a value of $ 4, each ball is $ 2, and hats have no value. For a partner, the same objects may have a different value, but you know that all the objects together are as valuable to him as they are to you - in this case it is $ 10.

    You and your partner in turn offer options for the section of items. In turn, one of you can either accept the previous offer (unless it is the very first turn), or make a counter offer. Negotiations are limited to 5 rounds, in total, both participants can put forward up to 10 proposals. If an agreement is reached during this time, then each of you will receive the total value of the items going to him (each in accordance with their own coefficients of value). If an agreement is not reached, that is, the last word in the last round - a counter offer, not an agreement - then no one gets anything. The same happens if one of the partners interrupts the negotiations.

    Here is an example of how negotiations can take place:

    1. You: I want a book and two balls; you get one ball and both hats.
    2. Partner: I do not agree. I want all the balls and one hat; you get a book and one hat.
    3. You: I do not agree. I want a book and one ball; You will get two balls and both hats.
    4. Partner: I agree.

    You did not know this, but for the partner the value of the items was as follows: $ 2 per ball, $ 2 per hat, the book has no value. The agreement brought you $ 6 to you and $ 8 to your partner.

    In general, there are two or more object types and a positive integer number of objects of each type. The value of each type of object for each of the partners is a nonnegative integer. The total value of all objects for both partners is the same, although the values ​​of individual objects differ. The proposal for the section should distribute among the partners all objects without a remainder; individual objects are not crushed.

    Your task is to write a script seeking to make a deal with the highest possible value (for yourself).

    Solutions


    The solution is a Node.js module without dependencies. The export module must be a class:

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

    A copy of this class will be created once and used during the negotiation session. The following arguments are passed to the constructor:

    • me - 0 if your turn is first, or 1 if second.
    • counts- an array of integers containing the number of objects of each type. It contains from 2 to 10 elements.
    • values- an array of integers of the same length as counts, describing the value of an object of each type for you.
    • max_rounds - the number of rounds of negotiations (each round consists of two replicas).
    • log- a function that can be called for debug output ( console.logwill not work).

    The method offeris invoked every time it is your turn. Its argument ois an array of integers of the same length as counts. The argument describes how many objects of each type are offered by the partner. If your first and foremost, and this is the first round, then othe same undefined.

    The method offershould return undefinedif you accept the offer (except when oequal to undefined). Otherwise, it must return an array of integers of the same length as counts, describing how many objects of each type you want to keep. Note that both the argument oand the return value offerdescribe the item section from your point of view.

    The time of the script is limited to 1 second per move. If time expires, or the script raises an exception or returns an invalid value, it is considered that the participant interrupted the negotiations, and none of the partners receive anything.

    The environment in which the script is run does not provide the possibility of accumulating information between sessions.

    The example.js file contains a simple example of a script that satisfies the rules. He accepts any offer for which he withdraws at least half of the total value of all objects; otherwise, it simply requires all objects of non-zero value. The script also demonstrates the use of the function log.

    Testing


    The haggle.js script allows you to organize negotiations between two human participants, between a person and a script, or between two scripts. Run it with a parameter --helpto learn about all its features. (To install all the necessary modules, run npm installin the directory src.)

    We will arrange pairwise negotiations between the scripts sent by the contest participants. We hope to be able to hold at least two sessions for each possible pair, however, if there are too many solutions, then we may have to choose another system for holding the championship. A specific system will be announced later. In any case, the value will not be "victory" and "defeat", and the amount of rewards received by each script in all sessions.

    For the final testing, we will use the default test system parameters: 3 types of objects, a total of up to 6 objects, the total value of all objects for each of the partners is $ 10, a limit of 5 rounds. We recommend writing solutions so that they support any combination of parameters that the test system supports.

    Testing will take place on the virtual server c3.large (see the hardware specifications by reference) on Amazon AWS running Ubuntu 14.04 (amd64). Solutions will be tested one pair after another with no other load on the machine.

    We will fix the bugs in the test system, which are reported to us by the participants; stay tuned ( history). When reporting bugs, please give us the protocol of the session (it can be recorded using the option --log).

    Negotiations online


    We provide a server that allows your script to negotiate with other participants. It is arranged like servers of online games: you can connect to the arena, and the server organizes a session between you and another participant.

    Initially, we created one arena with default settings (3 types of objects, up to 6 objects in total, the total value of all objects for each of the partners is $ 10, the limit is 5 rounds). This arena does not control the time limit of 1 second to allow people to participate manually. Here is the address of the arena:

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

    Use haggle.jsto connect to the server as a human participant or with your own script. In this mode, you also need to pass a command line parameter --id: this is a unique identifier by which the system will track the progress of your script. We recommend using your email address as an identifier plus a constant random string. We will not publish ids. Later we will launch a “live” table of best results, which will show the average outcomes of transactions and identifier hashes .

    Server and table best - for your information and for fun. Points in the table will not affect the results of the competition in any way, and using the server for participation is not necessary. However, online negotiations can not only allow you to informally compare your decision with others, but also provide you with valuable information about the strategies of other participants.

    If your script works, we recommend that it constantly participate in online sessions, for example, using the following UNIX shell command:

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


    Sending Solutions


    To send solutions, use the form on our website . No decision by email!

    Since the decision code is often generated, minimized or translated from another language, the form also contains a field for sending an archive with source tests. If the code is generated, turn on the generator; if it is minimized, include the original version; If the code is translated from CoffeeScript or another language, include the code in the language in which it is written. It is also advisable to include in the archive a README file with a brief description of the approach to the solution (in English). The archive must be in the format tar.gz, tar.bz2 or zip. The contents of the archive will be published, but will not be tested (we only test the JS file that you send outside the archive).

    The maximum size of the JS file is set to 64 MiB. This is an arbitrarily chosen number, which exists mainly so that someone’s “solution” does not simultaneously fill us with a disk. If your solution is true more than 64 MiB, write to us and we will increase the limit.

    If you have questions about the condition of the problem or problems with sending a solution, please write a comment or letter .

    Good luck to all participants!

    Also popular now: