Reverse Engineer Polling Statistics

22

Einführung

Berechnen Sie bei einer Reihe von Prozentsätzen für die Auswahlmöglichkeiten in einer Umfrage die Mindestanzahl der Wähler, die in der Umfrage enthalten sein müssen, um diese Statistiken zu erstellen.

Beispiel: Welches ist Ihr Lieblingshaustier?

  • Hund: 44.4%
  • Katze: 44.4%
  • Maus: 11.1%

Output: 9(minimal mögliche Anzahl von Wählern)

Technische Daten

Hier sind die Anforderungen für Ihr Programm / Ihre Funktion:

  • Sie erhalten ein Array mit Prozentwerten als Eingabe (für stdin, als Funktionsargument usw.).
  • Jeder Prozentwert ist eine auf eine Dezimalstelle gerundete Zahl (z 44.4 44.4 11.1. B. ).
  • Berechnen Sie die kleinstmögliche Anzahl von Wählern in der Umfrage, deren Ergebnisse genau diese Prozentsätze ergeben würden, wenn sie auf eine Dezimalstelle gerundet würden (auf Standard- oder Funktionsrückgabewert).
  • Bonus : -15 Zeichen, wenn Sie auf "nicht triviale" Weise lösen können (dh Sie müssen nicht jede mögliche Anzahl von Wählern durchlaufen, bis Sie die erste finden, die funktioniert)

Beispiel

>./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

Wertung

Das ist Code-Golf, also gewinnt der kürzestmögliche Charakter. Etwaige Boni werden von der Gesamtzahl der Zeichen weiter abgezogen.

mellamokb
quelle
2
Ich denke, das könnte mit ein paar umständlicheren Fällen zum Testen einhergehen. 26.7 53.3 20.0(4 8 3 von 15), 48.4 13.7 21.6 6.5 9.8(74 21 33 10 15 von 153) usw.
Gareth
@ Gareth: Gute Gedanken. Aktualisiert mit Ihren Testfällen.
Mellamokb
Sollte die Summe aller Stimmen nicht 100% sein? Es ist nicht in den letzten vier Testfällen
Ali1S232
@Gajet: Nein, es ist nicht immer gleich 100%. Bei jeder Abrundung verlieren Sie bis zur 0.5%Gesamtsumme und bei jeder Aufrundung addieren Sie 0.5%zur Gesamtsumme. Die letzten vier Testfälle wurden gezielt konstruiert, um dieses Phänomen optimal auszunutzen. In dem ersten Testfall, der zu führt 2000, repräsentiert jeder der ersten 9 Einträge eine 1Abstimmung (und sind alle aufgerundet 0.5%), während der letzte eine 1991Abstimmung repräsentiert (und abgerundet ist ~ 0.5%). Wenn Sie diese Prozentsätze manuell berechnen und auf 1 Dezimalstelle runden, werden Sie sehen, dass alle korrekt sind.
Mellamokb
Ich habe Probleme mit der nicht-trivialen Antwort in VBA (seitdem gibt es keine), aber ich arbeite daran!
Gaffi

Antworten:

2

APL (Dyalog Classic) , 48 43 Bytes

-5 Bytes von Adám

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

Vollständiges Programm unter Eingabe von stdin.

Probieren Sie es online! Link ist zur dfn version.

Ungolfed

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

Probieren Sie es online!

  • normalizedividiert ( ÷) alle Elemente seines rechten Arguments ( ) durch seine Summe ( +/).
  • round(y)Rundet y auf 3 Dezimalstellen, indem Sie jedes Element von y formatieren ( ) und dann auswerten ( ).
  • find_max(y) gibt ein Array mit 1 zurück, wobei max (y) gefunden wird und 0 an anderer Stelle.
  • increase(x,y) Nimmt x (die Zielprozentsätze) und y (das Array der aktuellen Stimmensummen) und berechnet, wo 1 in y hinzugefügt werden muss, um die Prozentsätze näher an x ​​heranzuführen.
  • vote_totals(x,y) Nimmt x (die Zielprozentsätze) und y (die Gesamtzahl der Startstimmen) und führt f wiederholt aus, wobei Stimmen addiert werden, bis die Prozentsätze auf x gerundet sind.
    • Die Syntax f ⍣ gbedeutet, fwiederholt auszuführen, bis g(y,f(y))wahr ist. In diesem Fall ignorieren wir f(y).
  • h(x) Setzt y auf 0 (entspricht einem Array von 0s aufgrund der Vektorisierung), führt g aus und summiert die Gesamtzahl der abgegebenen Stimmen.
Lirtosiast
quelle
7

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]

Es funktioniert jetzt für das letzte Beispiel.

Beispiel läuft:

>>> 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
grc
quelle
Ich denke, dass in Ihrem letzten Beispiel etwas nicht stimmt. vielleicht 99.1
meintest
2
Ich denke es ist richtig, aber es ist ziemlich verwirrend. 1/2000 = 0.05%( 0.1%gerundet) und 1991/2000 = 99.55%( 99.6%gerundet). Wenn es also zehn Optionen in einer Umfrage gibt und neun davon einmal gewählt werden, während die letzten 1991 Stimmen erhalten, dann würden diese Prozentsätze angegeben.
Grc
Du hast recht. Tolle Lösung, übrigens.
Cristian Lupascu
Ich denke, Sie können 3 weitere Zeichen sparen, indem Sie diesen Tipp befolgen
Cristian Lupascu
Danke, w0lf. Ich habe es jetzt aktualisiert, um Registerkarten einzuschließen. Tabulatoren werden als vier Leerzeichen angezeigt, wenn sich jemand wundert.
Grc
4

J, 57 Zeichen

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

Verwendete die triviale Methode. Es nimmt Eingaben von der Tastatur entgegen. tErstellt eine Nachschlagetabelle und die zweite Zeile sucht nach der Eingabe in der Tabelle. Bei Interesse kann ich den Code ausführlich erläutern.

Ich hatte versucht, den Prozentsatz zu verwenden, um einen Bruch zu erstellen, und dann die niedrigste Form des Bruches zu erhalten, um die Zahl zu ermitteln, aber ich konnte keine Möglichkeit finden, mit der Rundung der Ergebnisse zu funktionieren.

Gareth
quelle
Hmm, dies schlägt für den neuen Testfall fehl. Ich muss nach einer Lösung suchen.
Gareth
4

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
Blazer
quelle
+1 Sieht gut aus! ideone.com/k2Mgb . Ich habe versucht, einen pathologischen Fall zu finden, um ihn zu lösen, aber ich konnte nicht.
Mellamokb
Ich kann auf ideone nicht generieren, da das Zeitlimit überschritten wurde. Aber für welches Ergebnis erhalten Sie [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,99.6]?
Mellamokb
hmm ... eine halbe stunde und das programm läuft noch. Ich denke, es ist wahrscheinlich sicher zu sagen, dass das ein Breaker ist. Ich verstehe jedoch nicht, wie das eine gültige Antwort sein kann, da es 100,5% und nicht 100% beträgt
Blazer
2
1/2000 = 0.05%( 0.1%gerundet) und 1991/2000 = 99.55%( 99.6%gerundet). Es ist also tatsächlich 100%, aber die Rundung macht es wirklich verwirrend.
Grc
3

VBA - 541

Dies hat einige krasse Fehler, aber es war mein Versuch, eine nicht-triviale / Loop-bis-ich-die-richtige-Nummer-Lösung zu finden. Ich habe es nicht voll ausprobiert, obwohl ich glaube, dass es in dieser Hinsicht nicht viel hinzuzufügen gibt. Ich habe jedoch zu viel Zeit damit verbracht, und es tut mir jetzt am Kopf weh. Ganz zu schweigen davon, dass die Regeln wahrscheinlich sehr gebrochen sind und mehr oder weniger nur für diese Beispiele gelten.

Dies funktioniert bei vielen einfachen Tests, die ich durchgeführt habe, sehr gut (dh sogar bei Summen, 2 oder 3 Eingaben), schlägt jedoch bei einigen der Tests, die von der Challenge präsentiert werden, fehl. Ich habe jedoch festgestellt, dass sich die Genauigkeit verbessert, wenn Sie die Dezimalgenauigkeit der Eingabe erhöhen (außerhalb des Bereichs der Abfrage).

Ein Großteil der Arbeit besteht darin, die gcd für die bereitgestellten Zahlen zu finden, und ich habe das irgendwie geschafft Function g(), obwohl es mit Sicherheit unvollständig ist und wahrscheinlich zumindest einige der Fehler in meinen Ausgaben verursacht.

Die Eingabe ist eine durch Leerzeichen getrennte Zeichenfolge von Werten.

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

Testfälle (Eingabe ==> erwartet / zurückgegeben):

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
Gaffi
quelle
Sie können 6 Bytes verlieren, indem Sie Debug.Print zuDebug.?
Taylor Scott
2

C # (.NET Core) , 286 Byte

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();}}

Probieren Sie es online!

Dank Peter Taylor und Inbegriff der Ignoranz konnten viele Bytes gespart werden

Cristian Lupascu
quelle
Wie kann ich das ändern, um es auf ideone.com zu testen?
Gareth
Ich denke, Sie vermissen eine }am Ende.
Grc
@Gareth Ich habe versucht, es auf ideone.com auszuführen, aber ich denke, es wird eine .NET Framework-Version vor 4.0 verwendet, da die Linq- ZipMethode nicht erkannt wird.
Cristian Lupascu
@grc Danke für den Hinweis. Aktualisiert.
Cristian Lupascu
1
@Gaffi: Nein, C # hat eine strikte Typisierung (wie Java), es muss also ein Boolescher Wert sein. Da 1>0ist kürzer als true, ist es bevorzugt.
Mellamokb
0

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

Probieren Sie es online!

Gibt die richtige Antwort für die ersten beiden Testfälle und stößt bei den anderen an Pythons Rekursionsgrenzen. Dies ist nicht sehr überraschend, da jede Prüfung auf einer neuen Rekursionsebene durchgeführt wird. Es ist aber kurz ...

(Eine Erklärung der verwendeten Variablen finden Sie im 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

sollte für 136 Bytes funktionieren, aber aufgrund der Float-Genauigkeit nicht.

ArBo
quelle