Le contexte

Straw Poll est un site Web destiné à la création de sondages simples / informels. Muni d'une liste d'options, l'utilisateur peut sélectionner son ou ses choix et les votes sont comptabilisés. Il y a deux caractéristiques très importantes d'un sondage de paille:

• Il est possible de visualiser les résultats actuels avant de voter
• Il est souvent possible de sélectionner plusieurs options, ce qui est traité de la même manière que si vous avez voté plusieurs fois, une pour chaque option.

La seule chose qui est plus amusant que de faire des sondages de paille est de jouer avec les résultats. Il existe deux principaux types de perturbation:

• Interruption simple, dans laquelle vous votez pour toutes les options
• Interruption avancée, dans laquelle vous choisissez stratégiquement les options pour lesquelles voter afin de maximiser l'effet.

Dans ce défi, vous écrirez un programme de perturbation avancée .

Les maths

Pour simplifier les choses mathématiquement, nous pouvons dire que plus l'entropie des votes est élevée, plus un sondage est perturbé. Cela signifie qu'un sondage où une seule option a tous les votes n'est pas du tout perturbé, tandis qu'un sondage où chaque option a un nombre égal de votes est perturbé au maximum (c'est l'objectif ultime).

L'entropie d'une liste de nombres [x1, x2, ..., xn]est donnée par l'équation suivante de wikipedia. P(xi)est la probabilité de xi, qui est xi / total_num_of_votes. Si une option n'a jusqu'à présent reçu aucun vote, elle n'est tout simplement pas incluse dans le résumé (à éviter log(0)). Pour nos besoins, le logarithme peut être dans n'importe quelle base de votre choix.

Par exemple, l'entropie de [3,2,1,1]est approximativement 1.277, en utilisant la base e .

L'étape suivante consiste à déterminer quel modèle de vote conduit à la plus grande augmentation d'entropie. Je peux voter pour n'importe quel sous-ensemble d'options, par exemple mon vote pourrait l'être [1,0,1,0]. S'il s'agissait de mes votes, alors le décompte final est [4,2,2,1]. Recalculer l'entropie donne 1.273, donnant une diminution de l'entropie, ce qui signifie que c'est une terrible tentative de perturbation. Voici quelques autres options:

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

De cela, nous pouvons conclure que le modèle de vote optimal est [0,0,1,1]car il donne la plus grande augmentation de l'entropie.

Contribution

L'entrée est une liste non vide d'entiers non croissants et non négatifs. Les exemples incluent [3,3,2,1,0,0], [123,23,1]ou même [4]. Tout format raisonnable est autorisé.

Production

La sortie est une liste (de la même longueur que l'entrée) des valeurs véridiques et falsey, où les vérités représentent les options pour lesquelles je devrais voter si je voulais provoquer une perturbation maximale. Si plusieurs schémas de vote donnent la même entropie, l'un ou l'autre peut être émis.

Critère gagnant

C'est du code-golf, moins d'octets, c'est mieux.

Cas de test

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

... (se plaignant fort)

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

Tester:

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

Pyth - 25 octets

hosm*FlBcdsGfT=G+VQN^U2lQ

Suite de tests .

MATL , 24 octets

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

Cela fonctionne avec la version 13.0.0 du langage / compilateur, qui est antérieure au défi.

Essayez-le en ligne!

Explication

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

Exemple

Voici un exemple de son fonctionnement. Pour la saisie [3 2 2], le tableau des modes de vote possibles (produit par Z^) est

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

où chaque ligne est un motif. Ceci est ajouté à l'original [3 2 0]avec broadcast ( G+). Cela signifie qu'il [3 2 0]est répliqué 8fois verticalement puis ajouté élément par élément pour donner

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

Ceci est transposé et chaque colonne est divisée par chaque somme ( !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 ]

La multiplication par son logarithme et la somme de chaque colonne ( tYl*s) donne moins l'entropie:

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

L'entropie moins est minimisée ( 4#X<) par le 4modèle de vote e, qui correspond ( Y)) au résultat final[0 1 1] .