9
\$\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 [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.

enter image description here

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\$
  • \$\begingroup\$ I wonder what would happen if we wanted to decrease entropy. \$\endgroup\$ – CalculatorFeline Feb 24 '16 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 '16 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 '16 at 12:15
3
\$\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\$
  • \$\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 '16 at 15:50
  • \$\begingroup\$ @IPoiler thanks for finding that testcase. \$\endgroup\$ – PhiNotPi Feb 24 '16 at 15:55
  • 1
    \$\begingroup\$ (cries and dies) \$\endgroup\$ – CalculatorFeline Feb 24 '16 at 15:56
  • 2
    \$\begingroup\$ Per here This should be deleted. \$\endgroup\$ – Rɪᴋᴇʀ Feb 24 '16 at 16:02
  • 1
    \$\begingroup\$ ..Fixed. (more loud complaining) \$\endgroup\$ – CalculatorFeline Feb 24 '16 at 16:17
2
\$\begingroup\$

Pyth - 25 bytes

hosm*FlBcdsGfT=G+VQN^U2lQ

Test Suite.

\$\endgroup\$
1
\$\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\$

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.