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.
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
[x1, x2, ..., xn] is given by the following equation from wikipedia.
P(xi) is the probability of
xi, which is
xi / total_num_of_votes. 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.
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 is a non-empty list of non-increasing, non-negative integers. Examples include
[123,23,1], or even
. Any reasonable format is allowable.
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.
This is code-golf, fewer bytes are better.
[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)  ->  OR  (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)