Reverse Engineer Polling Statistics

Question

Introduction

Given a set of percentages of choices in a poll, calculate the minimum number of voters there must be in the poll to generate those statistics.

Example: What is your favorite pet?

• Dog: 44.4%
• Cat: 44.4%
• Mouse: 11.1%

Output: 9 (minimum possible # of voters)

Specs

Here are the requirements for your program/function:

• You are given an array of percentage values as input (on stdin, as function argument, etc.)
• Each percentage value is a number rounded to one decimal place (e.g., 44.4 44.4 11.1).
• Calculate the minimum possible number of voters in the poll whose results would yield those exact percentages when rounded to one decimal place (on stdout, or function return value).
• Bonus: -15 characters if you can solve in a "non-trivial" way (i.e., doesn't involve iterating through every possible # of voters until you find the first one that works)

Example

>./pollreverse 44.4 44.4 11.1
9
>./pollreverse 26.7 53.3 20.0
15
>./pollreverse 48.4 13.7 21.6 6.5 9.8
153
>./pollreverse 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 99.6
2000
>./pollreverse 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 98.7
667
>./pollreverse 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 98.7
2000
>./pollreverse 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 97.8
401

Scoring

This is code-golf, so shortest possible characters wins. Any bonuses are further subtracted from the total character count.

Answer 1

APL (Dyalog Classic), 48 43 bytes

-5 bytes by Adám

+/0(⊢+{(⌈/⍷⊢)⍺-⍵÷+/⍵})⍣{z≡⍎3⍕⍺÷+/⍺}⍨z←.01×⎕

Full program taking input from stdin.

Try it online! Link is to dfn version.

Ungolfed

normalize ← ⊢ ÷ +/
find_max ← {⍵⍷⍨⌈/⍵}
round ← {⍎3⍕⍵}
increase ← {find_max ⍺ - normalize ⍵}
vote_totals ← {z←⍺ ⋄ ⍺ (⊢+increase)⍣{z ≡ round normalize ⍺} ⍵}
h ← {+/ (.01×⍵) vote_totals 0}

Try it online!

• normalize divides (÷) all elements of its right argument (⊢) by its sum (+/).
• round(y) rounds y to 3 decimal places by formatting (⍕) and then evaluating (⍎) each element of y.
• find_max(y) returns an array with 1 where max(y) is found and 0 elsewhere.
• increase(x,y) takes x (the goal percentages) and y (the array of current vote totals) and calculates where to add 1 in y to bring the percentages closer to x.
• vote_totals(x,y) takes x (the goal percentages) and y (the starting vote totals) and executes f repeatedly, adding votes until the percentages round to x.
  • The syntax f ⍣ g means to execute f repeatedly until g(y,f(y)) is true. In this case we ignore f(y).
• h(x) sets y to 0 (equivalent to an array of 0s due to vectorization), executes g, and sums the final vote totals.

Answer 2

Python, 154

def p(x):
 n=[1]*len(x);d=2;r=lambda z:round(1000.*z/d)/10
 while 1:
    if(map(r,n),sum(n))==(x,d):return d
    d+=1
    for i in range(len(x)):n[i]+=r(n[i])<x[i]

It works for the last example now.

Example runs:

>>> p([44.4, 44.4, 11.1])
9
>>> p([26.7, 53.3, 20.0])
15
>>> p([48.4, 13.7, 21.6, 6.5, 9.8])
153
>>> p([0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 99.6])
2000
>>> p([0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 98.7])
667
>>> p([0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 98.7])
2000
>>> p([0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 97.8])
401

Answer 3

Python, 154

def r(l):
 v=0
 while 1:
  v+=1;o=[round(y*v/100)for y in l];s=sum(o)
  if s: 
    if all(a==b for a,b in zip(l,[round(y*1000/s)/10for y in o])):return s

Answer 4

J, 57 characters

t=:".>'1'8!:0|:100*%/~i.1001
{.I.*/"1(t{~i.#t)e."1~1!:1[1

Used the trivial method. It takes input from the keyboard. t creates a lookup table and the second line looks for the input within the table. I can provide an expanded explanation of the code if anyone's interested.

I had looked into using the percentage to create a fraction then get the lowest form of the fraction to figure out the number, but I couldn't figure out a way to make it work with the rounding of the results.

Answer 5

VBA - 541

This has got some glaring errors, but it was my attempt to find a non-trivial/looping-until-I-get-the-right-number solution. I have not fully golfed it, though I don't think there's much to add in that regard. However, I've spent too much time on this, and it hurts my head now. Not to mention, the rules are probably very broken and apply more or less to these examples only.

This does very well for a lot of simple tests I ran, (i.e. even totals, 2 or 3 inputs) but it fails for some of the tests presented by the challenge. However, I found that if you increase the decimal precision of the input (outside the scope of the challenge), the accuracy improves.

Much of the work involves finding the gcd for the set of numbers provided, and I sort of got that through Function g(), though it is for sure incomplete and likely a source of at least some of the errors in my outputs.

Input is a space-delimited string of values.

Const q=10^10
Sub a(s)
e=Split(s)
m=1
f=UBound(e)
For i=0 To f
t=1/(e(i)/100)
m=m*t
n=IIf(n>t Or i=0,t,n)
x=IIf(x<t Or i=0,t,x)
Next
h=g(n,x)
i=(n*x)/(h)
If Int(i)=Round(Int(i*q)/q) Then
r=i
ElseIf (n+x)=(n*x) Then
r=(1/(n*x))/h/m
ElseIf x=Int(x) Then
r=x*(f+1)
Else
z=((n+x)+(n*x)+m)*h
y=m/(((m*h)/(f+1))+n)
r=IIf(y>z,z,y)
End If
Debug.Print Round(r)
End Sub
Function g(a,b)
x=Round(Int(a*q)/q,3)
y=Round(Int(b*q)/q,3)
If a Then
If b Then
If x>y Then
g=g(a-b,b)
ElseIf y>x Then
g=g(a,b-a)
Else
g=a
End If
End If
Else
g=b
End If
End Function

Testcases (input ==> expected/returned):

Passed:  

"95 5" ==> 20/20
"90 10" ==> 10/10
"46.7 53.3" ==> 15/15
"4.7 30.9 40.4 23.8" ==> 42/42
"44.4 44.4 11.1" ==> 9/9
"26.7 53.3 20.0" ==> 15/15
"48.4 13.7 21.6 6.5 9.8" ==> 153/153
"0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 99.55" ==> 2000/2000
"0.15 0.15 0.15 0.15 0.15 0.15 0.15 0.15 0.15 98.65" ==> 2000/2000
"0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 98.65067" ==> 667/667


Failed:  

"0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 99.6" ==> 2000/1000
"0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 98.7" ==> 2000/5000
"0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 98.7" ==> 667/1000
"0.14 0.14 0.14 0.14 0.14 0.14 0.14 0.14 0.14 98.65" ==> 667/10000
"0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 97.8" ==> 401/500
"0.24 0.24 0.24 0.24 0.24 0.24 0.24 0.24 0.24 97.75" ==> 401/235
"0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 97.75561" ==> 401/14010

Answer 6

C# (.NET Core), 286 bytes

double M(string[]a){var p=a.Select(double.Parse).ToList();var n=p.Select(x=>1d).ToList();var c=2;for(;;){Func<double,double>f=x=>Math.Round(x*1000/c,(MidpointRounding)1)/10;if(n.Select(f).Zip(p,(x,y)=>x==y).All(z=>z)&&c==n.Sum())return c;c++;n=n.Zip(p,(x,y)=>x+(f(x)<y?1:0)).ToList();}}

Try it online!

Saved lots of bytes thanks to Peter Taylor and Embodiment of Ignorance

Answer 7

Python 3, 140 139 137 bytes

f=lambda l,m=1,i=0,c=0,x=0:round(x*100,1)-l[i]and(x<1and f(l,m,i,c,x+1/m)or f(l,m+1))or l[i+1:]and f(l,m,i+1,c+x)or c+x-1and f(l,m+1)or m

Try it online!

Gives the right answer for the first two test cases, and runs into Python's recursion limits for the others. This is not very surprising, since every check is made on a new recursion level. It's short, though...

(An explanation of the used variables can be found in the TIO link)

f=lambda l,m=1,i=0,c=0,x=1:round(x*100,1)-l[i]and(x and f(l,m,i,c,x-1/m)or f(l,m+1))or l[i+1:]and f(l,m,i+1,c+x)or c+x-1and f(l,m+1)or m

should work for 136 bytes, but doesn't due to float precision.