Estadísticas de sondeo de ingeniero inverso

22

Introducción

Dado un conjunto de porcentajes de opciones en una encuesta, calcule el número mínimo de votantes que debe haber en la encuesta para generar esas estadísticas.

Ejemplo: ¿Cuál es tu mascota favorita?

  • Perro: 44.4%
  • Gato: 44.4%
  • Ratón: 11.1%

Salida: 9(número mínimo posible de votantes)

Especificaciones

Estos son los requisitos para su programa / función:

  • Se le proporciona una matriz de valores porcentuales como entrada (en stdin, como argumento de función, etc.)
  • Cada valor de porcentaje es un número redondeado a un decimal (por ejemplo, 44.4 44.4 11.1).
  • Calcule el número mínimo posible de votantes en la encuesta cuyos resultados arrojarían esos porcentajes exactos cuando se redondea a un decimal (en stdout o valor de retorno de función).
  • Bonificación : -15 caracteres si puede resolver de una manera "no trivial" (es decir, no implica iterar a través de cada número posible de votantes hasta que encuentre el primero que funcione)

Ejemplo

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

Tanteo

Este es el código de golf, por lo que gana los personajes más cortos posibles. Cualquier bonificación se resta aún más del recuento total de caracteres.

mellamokb
fuente
2
Creo que esto podría funcionar con algunos casos más incómodos para la prueba. 26.7 53.3 20.0(4 8 3 de 15), 48.4 13.7 21.6 6.5 9.8(74 21 33 10 15 de 153) etc.
Gareth
@Gareth: Buen pensamiento. Actualizado con sus casos de prueba.
mellamokb
¿No debería la suma de todos los votos ser 100%? no está en los últimos cuatro casos de prueba
Ali1S232
@Gajet: No, no siempre es igual al 100%. Cada vez que hay un redondeo hacia abajo, pierde hasta 0.5%del total, y cada vez que hay un redondeo hacia arriba, suma 0.5%al total. Los últimos cuatro casos de prueba se construyeron a propósito para explotar de manera óptima este fenómeno. En el primer caso de prueba que resulta 2000, cada una de las primeras 9 entradas representa el 1voto (y se redondean todas 0.5%), mientras que la última representa los 1991votos (y se redondea hacia abajo ~ 0.5%). Si calcula esos porcentajes manualmente y redondea a 1 decimal, verá que todos son correctos.
mellamokb
Estoy luchando con la respuesta no trivial en VBA (intentándolo desde ahora, no ha habido ninguna), ¡pero estoy trabajando en ello!
Gaffi

Respuestas:

2

APL (Dyalog Classic) , 48 43 bytes

-5 bytes por Adám

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

Programa completo tomando información de stdin.

Pruébalo en línea! El enlace es a la versión dfn.

Sin golf

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

Pruébalo en línea!

  • normalizedivide ( ÷) todos los elementos de su argumento correcto ( ) por su suma ( +/).
  • round(y)redondea y a 3 decimales formateando ( ) y luego evaluando ( ) cada elemento de y.
  • find_max(y) devuelve una matriz con 1 donde se encuentra max (y) y 0 en otro lugar.
  • increase(x,y) toma x (los porcentajes de las metas) e y (la matriz de los totales de votos actuales) y calcula dónde sumar 1 en y para acercar los porcentajes a x.
  • vote_totals(x,y) toma x (los porcentajes de goles) ey (los totales de votos iniciales) y ejecuta f repetidamente, agregando votos hasta que los porcentajes redondeen a x.
    • La sintaxis f ⍣ gsignifica ejecutar frepetidamente hasta que g(y,f(y))sea ​​verdadera. En este caso lo ignoramos f(y).
  • h(x) establece y en 0 (equivalente a una matriz de 0 debido a la vectorización), ejecuta gy suma el total de votos finales.
lirtosiast
fuente
7

Pitón, 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]

Funciona para el último ejemplo ahora.

Ejecuciones de ejemplo:

>>> 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
fuente
Creo que algo puede estar mal en tu último ejemplo; quizás quiso decir 99.1como el último valor
Cristian Lupascu
2
Creo que es correcto pero es bastante confuso. 1/2000 = 0.05%( 0.1%redondeado) y 1991/2000 = 99.55%( 99.6%redondeado). Entonces, si hay diez opciones en una encuesta y nueve de ellas se votan una vez, mientras que la última obtiene 1991 votos, entonces daría esos porcentajes.
GRC
Tienes razón. Gran solución, por cierto.
Cristian Lupascu
Creo que puede guardar 3 caracteres más siguiendo este consejo: codegolf.stackexchange.com/a/58/3527
Cristian Lupascu el
Gracias w0lf. Lo actualicé ahora para incluir pestañas. Las pestañas aparecen como cuatro espacios si alguien se pregunta.
grc
4

J, 57 caracteres

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

Usó el método trivial. Toma entrada del teclado. tcrea una tabla de búsqueda y la segunda línea busca la entrada dentro de la tabla. Puedo proporcionar una explicación ampliada del código si alguien está interesado.

Había buscado usar el porcentaje para crear una fracción y luego obtener la forma más baja de la fracción para calcular el número, pero no pude encontrar una manera de hacerlo funcionar con el redondeo de los resultados.

Gareth
fuente
Hmm, esto falla para el nuevo caso de prueba. Tendré que buscar una solución.
Gareth
4

Pitón, 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
Chaqueta de sport
fuente
+1 ¡Se ve bien! ideone.com/k2Mgb . Traté de encontrar un caso patológico para romperlo y no pude.
mellamokb
No puedo generar ideone debido a que el límite de tiempo excede, pero ¿qué resultado obtienes [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,99.6]?
mellamokb
hmm ... media hora y el programa aún se está ejecutando. Creo que probablemente sea seguro decir que es un factor decisivo. sin embargo, no veo cómo eso puede ser una respuesta válida porque totaliza 100.5% y no 100%
Blazer
2
1/2000 = 0.05%( 0.1%redondeado) y 1991/2000 = 99.55%( 99.6%redondeado). Por lo tanto, en realidad totaliza el 100%, pero el redondeo lo hace realmente confuso.
grc
3

VBA - 541

Esto tiene algunos errores evidentes, pero fue mi intento de encontrar una solución no trivial / en bucle hasta obtener el número correcto. No lo he jugado completamente, aunque no creo que haya mucho que agregar al respecto. Sin embargo, he pasado demasiado tiempo en esto, y ahora me duele la cabeza. Sin mencionar que las reglas están probablemente muy rotas y se aplican más o menos a estos ejemplos solamente.

Esto funciona muy bien para muchas pruebas simples que ejecuté (es decir, totales, 2 o 3 entradas), pero falla en algunas de las pruebas presentadas por el desafío. Sin embargo, descubrí que si aumenta la precisión decimal de la entrada (fuera del alcance del desafío), la precisión mejora.

Gran parte del trabajo implica encontrar el mcd para el conjunto de números proporcionados, y de alguna manera lo logré Function g(), aunque sin duda es incompleto y probablemente sea una fuente de al menos algunos de los errores en mis resultados.

La entrada es una cadena de valores delimitada por espacios.

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

Casos de prueba (input ==> esperado / devuelto):

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
fuente
puede perder 6 bytes mediante la conversión Debug.Print aDebug.?
Taylor Scott
2

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

Pruébalo en línea!

Ahorré muchos bytes gracias a Peter Taylor y Encarnación de la ignorancia

Cristian Lupascu
fuente
¿Cómo podría modificar esto para probarlo en ideone.com?
Gareth
Creo que te estás perdiendo un }al final.
grc
@Gareth Intenté ejecutarlo en ideone.com, pero creo que está usando una versión de .NET Framework anterior a la 4.0, porque no reconoce el Zipmétodo Linq .
Cristian Lupascu
@grc Gracias por señalar eso. Actualizado.
Cristian Lupascu
1
@Gaffi: No, C # tiene una escritura estricta (como Java), por lo que debe ser un booleano. Como 1>0es más corto que true, se prefiere.
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

Pruébalo en línea!

Da la respuesta correcta para los dos primeros casos de prueba y se encuentra con los límites de recursión de Python para los demás. Esto no es muy sorprendente, ya que cada verificación se realiza en un nuevo nivel de recursión. Es corto, sin embargo ...

(Puede encontrar una explicación de las variables utilizadas en el enlace TIO)

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

debería funcionar para 136 bytes, pero no debido a la precisión flotante.

ArBo
fuente