Kontext

Straw Poll ist eine Website, die für die Erstellung einfacher / informeller Umfragen gedacht ist. Mit einer Liste von Optionen kann der Benutzer seine Auswahl (en) auswählen und die Stimmen werden gezählt. Es gibt zwei sehr wichtige Merkmale einer Strohumfrage:

• Es ist möglich, die aktuellen Ergebnisse vor der Abstimmung anzuzeigen
• Es ist oft möglich, mehrere Optionen auszuwählen, was genauso behandelt wird, als ob Sie mehrfach abgestimmt hätten, eine für jede Option.

Das einzige, was mehr Spaß macht als Strohumfragen durchzuführen, ist, mit den Ergebnissen herumzuspielen. Es gibt zwei Hauptarten von Störungen:

• Einfache Störung, bei der Sie für alle Optionen stimmen
• Erweiterte Unterbrechung, bei der Sie strategisch auswählen, für welche Optionen Sie stimmen möchten, um den Effekt zu maximieren.

In dieser Herausforderung schreiben Sie ein Programm für fortgeschrittene Störungen.

Die Mathematik

Einfach ausgedrückt können wir sagen, dass eine Umfrage umso störender ist , je höher die Entropie der Stimmen ist. Dies bedeutet, dass eine Umfrage, bei der eine einzelne Option alle Stimmen hat, überhaupt nicht gestört wird, während eine Umfrage, bei der jede Option die gleiche Anzahl von Stimmen hat, maximal gestört wird (dies ist das ultimative Ziel).

Die Entropie einer Zahlenliste [x1, x2, ..., xn]ergibt sich aus der folgenden Gleichung aus Wikipedia. P(xi)ist die Wahrscheinlichkeit von xi, was ist xi / total_num_of_votes. Wenn eine Option bisher keine Stimmen erhalten hat, wird sie einfach nicht in die Summierung einbezogen (um dies zu vermeiden log(0)). Für unsere Zwecke kann sich der Logarithmus in einer beliebigen Basis Ihrer Wahl befinden.

Als Beispiel ist die Entropie von [3,2,1,1]ungefähr 1.277unter Verwendung der Basis e .

Der nächste Schritt besteht darin, zu bestimmen, welches Abstimmungsmuster zu der größten Zunahme der Entropie führt. Ich kann für jede Untergruppe von Optionen stimmen, also könnte zum Beispiel meine Stimme sein [1,0,1,0]. Wenn dies meine Stimmen waren, dann ist die endgültige Bilanz [4,2,2,1]. Eine Neuberechnung der Entropie ergibt 1.273eine Verringerung der Entropie, was bedeutet, dass dies ein schrecklicher Versuch einer Störung ist. Hier sind einige andere Optionen:

don't vote
[3,2,1,1] -> 1.277

vote for everything
[4,3,2,2] -> 1.342

vote for the 1s
[3,2,2,2] -> 1.369

vote for the 2 and 1s
[3,3,2,2] -> 1.366

Daraus können wir schließen, dass das optimale Abstimmungsmuster darin besteht, dass [0,0,1,1]es die größte Zunahme der Entropie ergibt.

Eingang

Die Eingabe ist eine nicht leere Liste nicht ansteigender, nicht negativer Ganzzahlen. Beispiele hierfür sind [3,3,2,1,0,0], [123,23,1]oder sogar [4]. Jedes vernünftige Format ist zulässig.

Ausgabe

Die Ausgabe ist eine Liste (dieselbe Länge wie die Eingabe) von Wahrheits- und False-Werten, wobei die Wahrheiten die Optionen darstellen, für die ich stimmen sollte, wenn ich maximale Störungen verursachen möchte. Wenn mehr als ein Abstimmungsmuster dieselbe Entropie ergibt, kann eines ausgegeben werden.

Gewinnkriterium

Das ist Code-Golf, weniger Bytes sind besser.

Testfälle

[3,2,1,1] -> [0,0,1,1]  (from 1.227 to 1.369)

[3,3,2,1,0,0] -> [0,0,0,1,1,1] (from 1.311 to 1.705)

[123,23,1] -> [0,1,1] (from 0.473 to 0.510)

[4] -> [0] OR [1] (from 0 to 0)

[7,7,6,6,5] -> [0,0,1,1,1] (from 1.602 to 1.608)

[100,50,1,1] -> [0,1,1,1] (from 0.707 to 0.761)

Mathematica, 19 44 Bytes

... (laut klagen)

(x=Median@#[[;;Mod[Length@#,2]-3]];#≤x&/@#)&

Prüfung:

{Test, data, goes, here};
(x=Median@#[[;;Mod[Length@#,2]-3]];#≤x&/@#)&
%%+Boole/@%

Pyth - 25 Bytes

hosm*FlBcdsGfT=G+VQN^U2lQ

Testsuite .

MATL , 24 Bytes

FTinZ^tG+!ts/tYl*s4#X<Y)

Dies funktioniert mit Version 13.0.0 der Sprache / des Compilers, die früher als die Herausforderung ist.

Probieren Sie es online aus!

Erläuterung

FT        % array [0 1]
in        % take input and push its length
Z^        % Cartesian power. This gives all possible vote patterns, each on a row
t         % duplicate (will be indexed into at the end to produce the result)
G         % push input again
+         % element-wise addition with broadcast
!         % transpose
ts/       % duplicate. Divide each column by its sum
tYl       % duplicatte. Take natural logarithm
*         % element-wise multiplication
s         % sum of each column. Gives minus entropy produce by each vote pattern
4#X<      % arg max
Y)        % index into original array of voting patterns. Implicitly display

Beispiel

Hier ist ein Beispiel, wie es funktioniert. Für die Eingabe [3 2 2]ist das Array möglicher Abstimmungsmuster (erzeugt von Z^)

[ 0 0 0
  0 0 1
  0 1 0
  0 1 1
  1 0 0
  1 0 1
  1 1 0
  1 1 1 ]

wobei jede Zeile ein Muster ist. Dies wird dem Original [3 2 0]mit Broadcast ( G+) hinzugefügt . Das heißt, es [3 2 0]wird 8mal vertikal repliziert und dann elementweise hinzugefügt, um zu geben

[ 3 2 2
  3 2 3
  3 3 2
  3 3 3
  4 2 2
  4 2 3
  4 3 2
  4 3 3 ]

Dies wird transponiert und jede Spalte wird durch jede Summe ( !ts/) geteilt:

[ 0.4286    0.3750    0.3750    0.3333    0.5000    0.4444    0.4444    0.4000
  0.2857    0.2500    0.3750    0.3333    0.2500    0.2222    0.3333    0.3000
  0.2857    0.3750    0.2500    0.3333    0.2500    0.3333    0.2222    0.3000 ]

Das Multiplizieren mit dem Logarithmus und das Summieren jeder Spalte ( tYl*s) ergibt minus der Entropie:

[ -1.0790   -1.0822   -1.0822   -1.0986   -1.0397   -1.0609   -1.0609   -1.0889 ]

Die Minusentropie wird 4#X<durch das 4th-Abstimmungsmuster minimiert ( ) , das ( Y)) dem Endergebnis entspricht[0 1 1] .