Programmierwettbewerb: Handel

UPDATE: Ankündigungen für Teilnehmer .
UPDATE 2: Zwischenergebnisse und Ankündigungen .

Hola kündigt erneut Programmierwettbewerb an! Gewinner werden Preise erwartet:

1. Erster Platz: 3000 USD.
2. Zweiter Platz: 2000 USD.
3. Dritter Platz: 1000 USD.
4. Die Jury kann nach eigenem Ermessen einen Sonderpreis von 400 USD vergeben.
5. Wenn Sie jemandem einen Link zu diesem Wettbewerb senden, indem Sie unsere Adresse in CC eingeben, und diese Person den Preis entgegennimmt, erhalten Sie die Hälfte des Preisbetrags (natürlich nicht zum Nachteil des Gewinnerpreises). Für einen Gewinner kann nur eine Person eine solche Auszeichnung erhalten - diejenige, die den Link zuerst gesendet hat.

Autoren interessanter Entscheidungen werden zu Interviews eingeladen.

Die Regeln

Die Wettbewerbsbedingungen in englischer Sprache sind auf GitHub verfügbar. Unten ist eine Übersetzung ins Russische.

• Senden Sie Lösungen mit diesem Formular . Entscheidungen werden nicht per E-Mail getroffen.
• Entscheidungen werden bis zum 20. Juli 2018 , 23:59:59 UTC getroffen.
• Die vorläufigen Ergebnisse werden am 27. Juli 2018 und die endgültige Bekanntgabe der Gewinner am 3. August 2018 veröffentlicht .
• Sie können Entscheidungen mehrmals senden, aber von jedem Teilnehmer wird nur die aktuellste Entscheidung berücksichtigt, die vor Ablauf der Frist für die Annahme von Arbeiten gesendet wird.
• Zum Testen verwenden wir Node.js v10.4.1 (die aktuelle Version zum Zeitpunkt der Veröffentlichung). Sie können alle vom Interpreter unterstützten Sprachfunktionen in der Standardkonfiguration verwenden.
• Der gesamte Lösungscode muss sich in einer einzigen JS-Datei befinden .
• Die Lösung sollte auf JS sein. Wenn Sie CoffeeScript oder ähnliche Sprachen bevorzugen, müssen Sie die Lösung vor dem Absenden in JS übersetzen.
• Wenn Ihre JS-Datei ein Produkt der Generierung, Minimierung und / oder Kompilierung aus anderen Sprachen wie CoffeeScript ist, fügen Sie bitte ein Archiv mit Quellcodes sowie vorzugsweise eine Beschreibung des Ansatzes bei. Der Inhalt dieses Archivs wird veröffentlicht, aber wir werden ihn nicht testen.
• Sie können keine Module laden , auch nicht die in der Standard-Node.js enthaltenen.
• Ein Teilnehmer darf nur eine E-Mail-Adresse verwenden, um eine Entscheidung zu treffen. Das Senden mehrerer Entscheidungen in Absprache von verschiedenen Adressen ist verboten. Alle an einem solchen Programm teilnehmenden Entscheidungen werden disqualifiziert.
• Wir müssen Ihren vollständigen Namen kennen, aber wenn Sie möchten, veröffentlichen wir stattdessen einen Alias. Wir werden Ihre E-Mail-Adresse vertraulich behandeln.
• Aktuelle und ehemalige Hola-Mitarbeiter und ihre unmittelbaren Familienangehörigen können nur außerhalb des Wettbewerbs teilnehmen und keine Preise beanspruchen.
• Stellen Sie in den Kommentaren zu dieser Veröffentlichung oder per E-Mail Fragen zum Zustand der Aufgabe.

Handel

Nehmen wir an, wir haben ein Buch, zwei Hüte und drei Bälle. Sie und ein anderer Teilnehmer müssen entscheiden, wie Sie dieses Gut zwischen Ihnen beiden teilen möchten. Für Sie hat das Buch einen Wert von 4 $, jeder Ball ist 2 $ und Hüte haben keinen Wert. Für einen Partner haben dieselben Objekte möglicherweise einen unterschiedlichen Wert, aber Sie wissen, dass alle Objekte für ihn zusammen genauso wertvoll sind wie für Sie - in diesem Fall 10 US-Dollar.

Sie und der Partner schlagen abwechselnd einen Abschnitt für Artikel vor. Im Gegenzug kann einer von Ihnen entweder das vorherige Angebot annehmen (es sei denn, es ist die allererste Stufe) oder ein Gegenangebot machen. Die Verhandlungen sind auf 5 Runden begrenzt. Insgesamt können beide Teilnehmer bis zu 10 Vorschläge einreichen. Wenn in dieser Zeit eine Einigung erzielt wird, erhält jeder von Ihnen den Gesamtwert der Artikel, die ihn verlassen (jeweils gemäß seinen eigenen Wertfaktoren). Wenn keine Einigung erzielt wird, das heißt, das letzte Wort in der letzten Runde ist ein Gegenangebot und keine Zustimmung, dann bekommt niemand etwas. Das gleiche passiert, wenn einer der Partner die Verhandlungen unterbricht.

Hier ist ein Beispiel dafür, wie Verhandlungen verlaufen können:

1. Sie: Ich möchte ein Buch und zwei Bälle; Sie erhalten einen Ball und beide Hüte.
2. Partner: Ich stimme nicht zu. Ich will alle Bälle und einen Hut; Sie erhalten ein Buch und einen Hut.
3. Sie: Ich stimme nicht zu. Ich möchte ein Buch und einen Ball. Sie erhalten zwei Bälle und beide Hüte.
4. Partner: Ich stimme zu.

Sie wussten das nicht, aber für den Partner war der Wert der Gegenstände wie folgt: Bei 2 USD pro Ball, bei 2 USD pro Hut hat das Buch keinen Wert. Die Vereinbarung brachte Ihnen 6 USD und dem Partner 8 USD.

Im Allgemeinen gibt es zwei oder mehr Objekttypen und eine positive ganzzahlige Anzahl von Objekten jedes Typs. Der Wert jedes Objekttyps für jeden der Partner ist eine nicht negative Ganzzahl. Der Gesamtwert aller Objekte ist für beide Partner gleich, obwohl die Werte der einzelnen Objekte variieren. Der Vorschlag für die Aufteilung sollte alle Objekte spurlos unter den Partnern verteilen; einzelne Objekte werden nicht fragmentiert.

Ihre Aufgabe ist es, ein Skript zu schreiben, das versucht, einen Deal mit dem höchstmöglichen Wert (für sich selbst) abzuschließen.

Lösungen

Die Lösung ist ein Node.js-Modul ohne Abhängigkeiten. Der Modulexport sollte eine Klasse sein:

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, . ( , npm install src.)

, . , , , , , , . . , «» «», , .

: 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

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 , , .

, , , .

!