Contexto

O Straw Poll é um site destinado à criação de pesquisas simples / informais. Fornecido com uma lista de opções, o usuário pode selecionar suas opções e os votos são computados. Há duas características muito importantes de uma pesquisa de palha:

• É possível visualizar os resultados atuais antes da votação
• Geralmente, é possível selecionar várias opções, que são tratadas da mesma maneira como se você votasse várias vezes, uma para cada opção.

A única coisa mais divertida do que fazer pesquisas de palha é mexer nos resultados. Existem dois tipos principais de interrupção:

• Interrupção simples, na qual você vota em todas as opções
• Interrupção avançada, na qual você escolhe estrategicamente em quais opções votar para maximizar o efeito.

Neste desafio, você escreverá um programa para interrupções avançadas .

A matemática

Para simplificar as coisas matematicamente, podemos dizer que quanto maior a entropia dos votos, mais prejudicada é a votação. Isso significa que uma pesquisa em que uma única opção tem todos os votos não é interrompida, enquanto uma pesquisa em que cada opção tem um número igual de votos é interrompida ao máximo (sendo esse o objetivo final).

A entropia de uma lista de números [x1, x2, ..., xn]é dada pela seguinte equação da wikipedia. P(xi)é a probabilidade de xi, qual é xi / total_num_of_votes. Se uma opção recebeu zero voto até agora, ela simplesmente não está incluída no somatório (para evitar log(0)). Para nossos propósitos, o logaritmo pode estar em qualquer base de sua escolha.

Como exemplo, a entropia de [3,2,1,1]é aproximadamente 1.277, usando a base e .

O próximo passo é determinar qual padrão de votação leva ao maior aumento na entropia. Posso votar em qualquer subconjunto de opções, por exemplo, meu voto poderia ser [1,0,1,0]. Se esses foram meus votos, então a contagem final é [4,2,2,1]. Recalcular a entropia dá 1.273, dando uma diminuição na entropia, o que significa que esta é uma terrível tentativa de interrupção. Aqui estão algumas outras opções:

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

A partir disso, podemos concluir que o padrão ótimo de votação é [0,0,1,1]uma vez que proporciona o maior aumento na entropia.

Entrada

Entrada é uma lista não vazia de números inteiros não crescentes e não negativos. Exemplos incluem [3,3,2,1,0,0], [123,23,1], ou mesmo [4]. Qualquer formato razoável é permitido.

Resultado

A saída é uma lista (do mesmo tamanho que a entrada) de valores de verdade e falsey, em que as verdades representam as opções pelas quais devo votar se desejar causar a interrupção máxima. Se mais de um padrão de votação der a mesma entropia, qualquer um poderá ser emitido.

Critério vencedor

Isso é código-golfe, menos bytes são melhores.

Casos de teste

[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

... (alto reclamando)

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

Teste:

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

Pitão - 25 bytes

hosm*FlBcdsGfT=G+VQN^U2lQ

Conjunto de Teste .

MATL , 24 bytes

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

Isso funciona com a versão 13.0.0 do idioma / compilador, anterior ao desafio.

Experimente online!

Explicação

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

Exemplo

Aqui está um exemplo de como isso funciona. Para entrada [3 2 2], a matriz de possíveis padrões de votação (produzidos por 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 ]

onde cada linha é um padrão. Isso é adicionado ao original [3 2 0]com broadcast ( G+). Isso significa que [3 2 0]é replicado 8vezes verticalmente e depois adicionado elemento a elemento para fornecer

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

Isso é transposto e cada coluna é dividida por cada soma ( !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 ]

Multiplicar por seu logaritmo e somar cada coluna ( tYl*s) fornece menos a entropia:

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

A entropia negativa é minimizada ( 4#X<) pelo 4padrão do voto th, que corresponde ( Y)) ao resultado final[0 1 1] .