Contexto

Straw Poll es un sitio web destinado a la creación de encuestas simples / informales. Con una lista de opciones, el usuario puede seleccionar sus opciones y los votos se contabilizan. Hay dos características muy importantes de una encuesta de paja:

• Es posible ver los resultados actuales antes de votar
• A menudo es posible seleccionar múltiples opciones, que se tratan de la misma manera que si votara varias veces, una para cada opción.

Lo único que es más divertido que hacer encuestas de paja es jugar con los resultados. Hay dos tipos principales de interrupción:

• Interrupción simple, en la que vota por todas las opciones
• Interrupción avanzada, en la que eliges estratégicamente qué opciones votar para maximizar el efecto.

En este desafío, escribirás un programa para la interrupción avanzada .

Las matemáticas

Para simplificar las cosas matemáticamente, podemos decir que cuanto mayor es la entropía de los votos, más perturbada es una encuesta. Esto significa que una encuesta donde una sola opción tiene todos los votos no se interrumpe en absoluto, mientras que una encuesta donde cada opción tiene un número igual de votos se interrumpe al máximo (este es el objetivo final).

La entropía de una lista de números [x1, x2, ..., xn]viene dada por la siguiente ecuación de wikipedia. P(xi)es la probabilidad de xi, que es xi / total_num_of_votes. Si una opción ha recibido cero votos hasta el momento, simplemente no se incluye en la suma (para evitar log(0)). Para nuestros propósitos, el logaritmo puede estar en cualquier base de su elección.

Como ejemplo, la entropía de [3,2,1,1]es aproximadamente 1.277, usando la base e .

El siguiente paso es determinar qué patrón de votación conduce al mayor aumento de la entropía. Puedo votar por cualquier subconjunto de opciones, por ejemplo, mi voto podría ser [1,0,1,0]. Si estos fueron mis votos, entonces la cuenta final es [4,2,2,1]. Recalcular la entropía da 1.273, dando una disminución en la entropía, lo que significa que este es un terrible intento de interrupción. Estas son algunas otras opciones:

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 de esto, podemos concluir que el patrón de votación óptimo se debe a [0,0,1,1]que proporciona el mayor aumento de entropía.

Entrada

La entrada es una lista no vacía de enteros no negativos y no crecientes. Los ejemplos incluyen [3,3,2,1,0,0], [123,23,1]o incluso [4]. Se permite cualquier formato razonable.

Salida

La salida es una lista (la misma longitud que la entrada) de los valores de verdad y falsey, donde las verdades representan las opciones por las que debería votar si quisiera causar una interrupción máxima. Si más de un patrón de votación da la misma entropía, cualquiera de los dos puede salir.

Criterio ganador

Este es el código de golf, menos bytes son mejores.

Casos de prueba

[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

... (fuerte quejándose)

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

Prueba:

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

Pyth - 25 bytes

hosm*FlBcdsGfT=G+VQN^U2lQ

Test Suite .

MATL , 24 bytes

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

Esto funciona con la versión 13.0.0 del lenguaje / compilador, que es anterior al desafío.

Pruébalo en línea!

Explicación

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

Ejemplo

Aquí hay un ejemplo de cómo funciona. Para la entrada [3 2 2], la matriz de posibles patrones de votación (producidos por Z^) es

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

donde cada fila es un patrón. Esto se agrega al original [3 2 0]con broadcast ( G+). Eso significa que [3 2 0]se replica 8verticalmente y luego se agrega en forma de elementos para dar

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

Esto se transpone y cada columna se divide por cada suma ( !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 su logaritmo y sumar cada columna ( tYl*s) da menos la entropía:

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

La entropía negativa se minimiza ( 4#X<) mediante el 4patrón de votos, que corresponde ( Y)) al resultado final[0 1 1] .