Konteks

Straw Poll adalah situs web yang dimaksudkan untuk menciptakan jajak pendapat sederhana / informal. Dilengkapi dengan daftar opsi, pengguna dapat memilih pilihan mereka, dan suara dihitung. Ada dua fitur yang sangat penting dari Poll Straw:

• Dimungkinkan untuk melihat hasil saat ini sebelum memilih
• Seringkali dimungkinkan untuk memilih beberapa opsi, yang diperlakukan dengan cara yang sama seperti jika Anda memilih beberapa kali, satu untuk setiap opsi.

Satu hal yang lebih menyenangkan daripada membuat Straw Polls adalah mengacaukan hasilnya. Ada dua jenis gangguan utama:

• Gangguan sederhana, di mana Anda memilih semua opsi
• Gangguan tingkat lanjut, di mana Anda secara strategis memilih opsi mana yang akan dipilih untuk memaksimalkan efeknya.

Dalam tantangan ini, Anda akan menulis sebuah program untuk gangguan lanjut .

Matematika

Untuk hal-hal sederhana secara matematis, kita dapat mengatakan bahwa semakin tinggi entropi suara, semakin terganggu jajak pendapat. Ini berarti bahwa jajak pendapat di mana satu opsi memiliki semua suara tidak terganggu sama sekali, sedangkan jajak pendapat di mana setiap opsi memiliki jumlah suara yang sama terganggu secara maksimal (ini menjadi tujuan akhir).

Entropi daftar angka [x1, x2, ..., xn]diberikan oleh persamaan berikut dari wikipedia. P(xi)adalah probabilitas xi, yaitu xi / total_num_of_votes. Jika opsi telah menerima nol suara sejauh ini, itu sama sekali tidak termasuk dalam penjumlahan (untuk menghindari log(0)). Untuk tujuan kami, logaritma dapat berada di basis pilihan Anda.

Sebagai contoh, entropi [3,2,1,1]kira-kira 1.277, menggunakan basis e .

Langkah selanjutnya adalah menentukan pola pemungutan suara apa yang mengarah pada peningkatan entropi terbesar. Saya dapat memberikan suara untuk setiap subset opsi, jadi misalnya suara saya bisa [1,0,1,0]. Jika ini suara saya, maka penghitungan akhir adalah [4,2,2,1]. Menghitung ulang entropi memberi 1.273, memberikan penurunan entropi, yang berarti ini adalah upaya yang mengerikan pada gangguan. Berikut beberapa opsi lain:

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

Dari sini, kita dapat menyimpulkan bahwa pola pemungutan suara yang optimal adalah [0,0,1,1]karena ia memberikan peningkatan terbesar dalam entropi.

Memasukkan

Input adalah daftar non-kosong bilangan bulat yang tidak bertambah, tidak negatif. Contohnya termasuk [3,3,2,1,0,0], [123,23,1]atau bahkan [4]. Setiap format yang masuk akal diijinkan.

Keluaran

Output adalah daftar (panjang yang sama dengan input) dari nilai-nilai kebenaran dan falsey, di mana kebenaran mewakili pilihan yang harus saya pilih jika saya ingin menyebabkan gangguan maksimal. Jika lebih dari satu pola pemungutan suara memberikan entropi yang sama, salah satunya bisa jadi keluaran.

Kriteria Kemenangan

Ini kode-golf, lebih sedikit byte lebih baik.

Uji Kasus

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

... (mengeluh keras)

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

Uji:

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

Pyth - 25 byte

hosm*FlBcdsGfT=G+VQN^U2lQ

Test Suite .

MATL , 24 byte

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

Ini bekerja dengan versi 13.0.0 dari bahasa / kompiler, yang lebih awal dari tantangan.

Cobalah online!

Penjelasan

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

Contoh

Berikut ini contoh cara kerjanya. Untuk input [3 2 2], susunan dari pola pemilihan yang mungkin (dihasilkan oleh Z^) adalah

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

di mana setiap baris adalah sebuah pola. Ini ditambahkan ke aslinya [3 2 0]dengan siaran ( G+). Itu berarti [3 2 0]direplikasi 8kali secara vertikal dan kemudian ditambahkan elemen bijaksana untuk diberikan

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

Ini ditransposisikan dan setiap kolom dibagi dengan jumlah masing-masing ( !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 ]

Mengalikan dengan logaritma dan menjumlahkan setiap kolom ( tYl*s) memberikan minus entropi:

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

Entropi dikurangi diminimalkan ( 4#X<) oleh 4pola suara th, yang sesuai ( Y)) dengan hasil akhir[0 1 1] .