Kontekst

Straw Poll to strona internetowa przeznaczona do tworzenia prostych / nieformalnych ankiet. Dostarczony z listą opcji, użytkownik może wybrać swoje opcje, a głosy są podwyższane. Sonda ankietowa ma dwie bardzo ważne cechy:

• Możliwe jest przeglądanie bieżących wyników przed głosowaniem
• Często można wybrać wiele opcji, które są traktowane tak samo, jakbyś głosował wiele razy, po jednej dla każdej opcji.

Jedyną rzeczą, która sprawia więcej radości niż tworzenie ankiet słomkowych, jest bałagan z wynikami. Istnieją dwa główne rodzaje zakłóceń:

• Proste zakłócenie, w którym głosujesz na wszystkie opcje
• Zaawansowane zakłócenie, w którym strategicznie wybierasz opcje, na które chcesz głosować, aby zmaksymalizować efekt.

W tym wyzwaniu napiszesz program dla zaawansowanych zakłóceń.

Matematyka

Mówiąc po prostu matematycznie, możemy powiedzieć, że im wyższa entropia głosów, tym bardziej zakłócona jest ankieta. Oznacza to, że ankieta, w której jedna opcja ma wszystkie głosy, nie jest w ogóle przerywana, natomiast ankieta, w której każda opcja ma taką samą liczbę głosów, jest maksymalnie przerywana (jest to ostateczny cel).

Entropię listy liczb [x1, x2, ..., xn]podaje poniższe równanie z wikipedii. P(xi)to prawdopodobieństwo xi, które wynosi xi / total_num_of_votes. Jeśli jak dotąd opcja otrzymała zero głosów, po prostu nie jest uwzględniana w podsumowaniu (aby tego uniknąć log(0)). Dla naszych celów logarytm może znajdować się w dowolnej wybranej przez ciebie bazie.

Na przykład, entropia [3,2,1,1]jest w przybliżeniu 1.277, przy użyciu podstawy e .

Następnym krokiem jest ustalenie, jaki wzór głosowania prowadzi do największego wzrostu entropii. Mogę głosować na dowolny podzbiór opcji, więc na przykład mój głos może być [1,0,1,0]. Gdyby to były moje głosy, to końcowy wynik jest [4,2,2,1]. Ponowne obliczenie entropii daje 1.273, zmniejszając entropię, co oznacza, że ​​jest to straszna próba zakłócenia. Oto kilka innych opcji:

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

Z tego możemy wywnioskować, że optymalny schemat głosowania jest taki, [0,0,1,1]ponieważ daje największy wzrost entropii.

Wejście

Dane wejściowe to niepusta lista nie rosnących, nieujemnych liczb całkowitych. Przykłady obejmują [3,3,2,1,0,0], [123,23,1]albo nawet [4]. Dozwolony jest każdy rozsądny format.

Wynik

Dane wyjściowe to lista (o tej samej długości co dane wejściowe) wartości prawdy i falseya, gdzie prawdy reprezentują opcje, na które powinienem głosować, jeśli chcę spowodować maksymalne zakłócenia. Jeśli więcej niż jeden wzorzec głosowania daje tę samą entropię, można wyprowadzić jeden z nich.

Zwycięskie kryterium

To jest golf golfowy, im mniej bajtów, tym lepiej.

Przypadki testowe

[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 bajtów

... (głośno narzeka)

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

Test:

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

Pyth - 25 bajtów

hosm*FlBcdsGfT=G+VQN^U2lQ

Pakiet testowy .

MATL , 24 bajty

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

Działa to z wersją 13.0.0 języka / kompilatora, która jest wcześniejsza niż wyzwanie.

Wypróbuj online!

Wyjaśnienie

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

Przykład

Oto przykład, jak to działa. Dla danych wejściowych [3 2 2]tablica możliwych wzorców głosowania (wyprodukowanych przez Z^) to

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

gdzie każdy rząd jest wzorem. Jest to dodawane do oryginału za [3 2 0]pomocą broadcast ( G+). Oznacza to, że czasy [3 2 0]są replikowane w 8pionie, a następnie dodawane w zależności od elementu, aby dać

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

Jest to transponowane i każda kolumna jest dzielona przez każdą sumę ( !ts/):

[ 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 ]

Pomnożenie przez jego logarytm i zsumowanie każdej kolumny ( tYl*s) daje minus entropię:

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

Entropia minus jest minimalizowana ( 4#X<) przez 4wzorzec th głosowania, który odpowiada ( Y)) końcowemu wynikowi[0 1 1] .