11
\$\begingroup\$

Context

Straw Poll is a website that is meant for the creation of simple/informal polls. Provided with a list of options, the user can select their choice(s), and the votes are tallied up. There's two very important features of a Straw Poll:

  • It is possible to view the current results before voting
  • It is often possible to select multiple options, which is treated the same way as if you voted multiple times, one for each option.

The one thing that's more fun than making Straw Polls is messing with the results. There's two main types of disruption:

  • Simple disruption, in which you vote for all the options
  • Advanced disruption, in which you strategically pick which options to vote for in order to maximize the effect.

In this challenge, you will write a program for advanced disruption.

The Math

To simply things mathematically, we can say that the higher the entropy of the votes, the more disrupted a poll is. This means that a poll where a single option has all the votes isn't disrupted at all, while a poll where every option has an equal number of votes is maximally disrupted (this being the ultimate goal).

The entropy of a list of numbers \$[x_1, x_2, \dots x_n]\$ is given by the following equation from Wikipedia. \$P(x_i)\$ is the probability of \$x_i\$, which is \$\frac {x_i} {\sum^n_{i=1} x_i}\$. If an option has received zero votes so far, it is simply not included in the summation (to avoid \$\log(0)\$). For our purposes, the logarithm can be in any base of your choice.

$$H(X) = \sum^n_{i=1} P(x_i) I(x_i) = -\sum^n_{i=1} P(x_i) \log_b P(x_i)$$

As an example, the entropy of \$[3,2,1,1]\$ is approximately \$1.277\$, using base \$e\$.

The next step is to determine what voting pattern leads to the greatest increase in entropy. I can vote for any subset of options, so for example my vote could be \$[1,0,1,0]\$. If these were my votes, then the final tally is \$[4,2,2,1]\$. Recalculating the entropy gives \$1.273\$, giving a decrease in entropy, which means this is a terrible attempt at disruption. Here are some other 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

From this, we can conclude that the optimal voting pattern is \$[0,0,1,1]\$ since it gives the greatest increase in entropy.

Input

Input is a non-empty list of non-increasing, non-negative integers. Examples include \$[3,3,2,1,0,0]\$, \$[123,23,1]\$, or even \$[4]\$. Any reasonable format is allowable.

Output

Output is a list (the same length as input) of truthy and falsey values, where the truths represent the options for which I should vote if I desired to cause maximal disruption. If more than one voting pattern gives the same entropy, either one can be output.

Winning Criterion

This is code-golf, fewer bytes are better.

Test Cases

[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)
\$\endgroup\$
3
  • \$\begingroup\$ I wonder what would happen if we wanted to decrease entropy. \$\endgroup\$ Feb 24, 2016 at 3:47
  • 1
    \$\begingroup\$ The test cases seem to be consistent with the heuristic "Increase the below-average values." Could you include some trickier test cases? \$\endgroup\$
    – xnor
    Feb 24, 2016 at 10:57
  • \$\begingroup\$ @xnor given that entropy is maximised with a uniform distribution, that's going to be a good heuristic! In fact, it might even be always the optimal strategy.. Perhaps someone can think of a good edge case? \$\endgroup\$
    – A Simmons
    Feb 24, 2016 at 12:15

4 Answers 4

4
\$\begingroup\$

Mathematica, 19 44 bytes

...(loud complaining)

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

Test:

{Test, data, goes, here};
(x=Median@#[[;;Mod[Length@#,2]-3]];#≤x&/@#)&
%%+Boole/@%
\$\endgroup\$
6
  • \$\begingroup\$ This fails for {100,50,1,1} where it returns {False, False, True, True}, resulting in an entropy of 0.758. {False, True, True, True} yields an entropy of 0.761. \$\endgroup\$
    – IPoiler
    Feb 24, 2016 at 15:50
  • \$\begingroup\$ @IPoiler thanks for finding that testcase. \$\endgroup\$
    – PhiNotPi
    Feb 24, 2016 at 15:55
  • 1
    \$\begingroup\$ (cries and dies) \$\endgroup\$ Feb 24, 2016 at 15:56
  • 2
    \$\begingroup\$ Per here This should be deleted. \$\endgroup\$
    – Riker
    Feb 24, 2016 at 16:02
  • 1
    \$\begingroup\$ ..Fixed. (more loud complaining) \$\endgroup\$ Feb 24, 2016 at 16:17
3
\$\begingroup\$

Pyth - 25 bytes

hosm*FlBcdsGfT=G+VQN^U2lQ

Test Suite.

\$\endgroup\$
2
\$\begingroup\$

MATL, 24 bytes

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

This works with version 13.0.0 of the language/compiler, which is earlier than the challenge.

Try it online!

Explanation

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

Example

Here's an example of how it works. For input [3 2 2], the array of possible voting patterns (produced by Z^) is

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

where each row is a pattern. This is added to the original [3 2 0] with broadcast (G+). That means [3 2 0] is replicated 8 times vertically and then added element-wise to give

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

This is transposed and each column is divided by each 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 ]

Multiplying by its logarithm and summing each column (tYl*s) gives minus the entropy:

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

The minus entropy is minimized (4#X<) by the 4th vote pattern, which corresponds (Y)) to the final result [0 1 1].

\$\endgroup\$
2
\$\begingroup\$

Jelly, 17 bytes

LØ.ṗ+ḟ0÷SḋÆl$ƊɗÐṂ

Try it online!

How it works

LØ.ṗ+ḟ0÷SḋÆl$ƊɗÐṂ - Main link. Takes a list A on the left
L                 - Length of A
 Ø.ṗ              - Cartesian power of [0, 1] to the length of A
              ɗÐṂ - Output the bitlist B with the minimum value f(B, A):
    +             -   Add the elements of B to A
     ḟ0           -   Remove any zeros
             Ɗ    -   Last 3 links as a monad g(A+B \ {0}):
       ÷S         -     Divide each by the sum
            $     -     Last 2 links as a monad h([A+B \ {0}] ÷ sum):
          Æl      -       Natural log of each
         ḋ        -       Dot product
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.