Un amigo tiene una tarjeta adicional en su computadora que genera un número perfectamente aleatorio del 1 al 5 inclusive. Desafortunadamente, derramaron cola de alguna manera, y ahora genera solo 2 para todos los números del 1 al 4. Afortunadamente, la aleatoriedad se conserva, pero 2 tiene una probabilidad del 80% y 5 tiene una probabilidad del 20%, y no hay 1's, 3's o 4's generados. Usando esta fuente aleatoria (llámela BrokenRand()o algo similar), escriba un generador de números aleatorios que funcione que produzca números del 1 al 5 cada uno con una probabilidad igual del 20% con la misma aleatoriedad perfecta que la fuente original.

El programa más corto gana. Puntos de bonificación otorgados por la cantidad mínima de llamadas a BrokenRanduna consulta de enfoque de servicio al cliente seleccionada demográficamente, desglosada por edad y sexo, es decir, yo.

JavaScript: 69 caracteres

Esto usa el extractor von Neumann para generar bits insesgados; El algoritmo general también se describe en el sitio web de HotBits . Se utilizan tres bits para formar un número del 0 al 7. Todos los números 5 y superiores se descartan y se agrega 1 a cada uno de los demás antes de imprimirlos. Hice una simulación para mostrar que esto no está muy sesgado .

Debe proporcionar su propia función r()para acceder al RNG.

 for(;;v<5&&alert(v+1))for(v=i=0;i<3;a-b&&(v*=2,v+=a<b,i++))b=r(a=r())

Scala 79 caracteres:

// preparation: 
val r = util.Random 
def defektRNG = if (r.nextInt (5) == 0) 5 else 2 

(1 to 20).foreach (_ => print (" " + defektRNG))
// first impression:
// 2 2 2 2 2 2 2 5 2 2 5 2 2 2 5 2 2 2 2 2

def rnd : Int = { val k = (1 to 5).map (_ => defektRNG)
  if (k.sum == 13) k.findIndexOf (_ == 5) + 1 else rnd } 

// first impression:
(1 to 20).foreach (_ => print (" " + rnd))             
// 3 3 2 3 5 2 2 5 1 1 3 4 3 2 5 3 3 1 5 4
// control:
(1 to 50000).map (_ => rnd).groupBy (identity) .map (_._2.length) 
// scala.collection.immutable.Iterable[Int] = List(10151, 9997, 9971, 9955, 9926)

Ahora para el golf real, el alias defektRNG brokenRand se renombra a b.

def r:Int={val k=(1 to 5).map(_=>b)
if(k.sum==13)k.findIndexOf(_==5)+1 else r} 

Cómo funciona: la mayoría de las veces, b devuelve una secuencia de 2s. Pero si hace 5 llamadas a b, muy a menudo terminará con un resultado de 4x2 y 1x5, es el segundo evento más probable y puede ser 5-2-2-2-2, 2-5-2-2 -2, 2-2-5-2-2, 2-2-2-5-2 y 2-2-2-2-5.

Estos tienen en común, que la suma es 4 * 2 + 5 = 13. El índice de los primeros cinco se puede utilizar para definir un número aleatorio válido. Si hay más o menos de un 5, una suma mayor o menor de 13, repita.

Un contador en 'rnd' también conocido como 'r' puede mostrar cuántas llamadas son necesarias en promedio para producir los números. Hay 121 200 llamadas a r por 50 000 números aleatorios, lo cual no es impresionante. :)

> <> (Pescado) - 55 bytes

Actualizado para usar el mismo algoritmo que @user unknown en su respuesta scala

<v? = d + &: i & + &: i & + &: i & + &: i &: i
 0 0
 > 1 + $ 5 (? Vnao;
 ^ <

Espera que el generador roto esté conectado a stdin; Aquí está el script de Python que utilicé . El código coincide con la especificación actual de Fish, pero utilicé una versión modificada del antiguo intérprete.

bash:$ for i in $(seq 1000); do ./bad_rand.py | ./myfish.py rand.fish; done >res.txt
bash:$ for i in $(seq 5); do echo -n "$i : "; grep -c $i res.txt; done
1 : 193
2 : 204
3 : 198
4 : 206
5 : 199

Haría una muestra más grande pero es lenta.

GolfScript, 23 bytes

Respuesta tardía, pero dado que esto apareció en la primera página ...

0{;[{r}5*].5?)\5-,4-}do

Utiliza el mismo algoritmo que la solución Scala del usuario desconocido . Asume que el generador de números aleatorios sesgado se da como una subrutina de GolfScript llamada r; usted mismo puede definir un RNG sesgado adecuado, por ejemplo, como:

{5rand!3*2+}:r;

Aquí hay una prueba rápida que demuestra la falta de sesgo. Desafortunadamente, el servidor de GolfScript en línea es un poco lento, así que tuve que reducir la demostración a solo 100 muestras para completarla a tiempo. Si se ejecuta la prueba a nivel local con el intérprete GolfScript , intente aumentar el 100*a 1000*o incluso 10000*.

(El servidor GolfScript también a veces se congela aleatoriamente y se agota el tiempo de espera de todos modos. Si esto sucede para usted, intentarlo nuevamente generalmente lo resuelve. También sucede con otro código, y solo ocurre en el servidor, no en mi propia computadora, así que estoy seguro que es un problema con el servidor y no con mi código)

JavaScript, 160 caracteres sin reducir la legibilidad, también conocida como optimización

function giveRandom(){
    var result = Math.floor(5 * Math.random()) + 1;
    while(BrockenRand() != 5){
        result = Math.floor(5 * Math.random()) + 1;
    }
    return result;
}