Correction d'une fonction aléatoire cassée

18

Un ami a une carte d'extension dans son ordinateur qui génère un nombre parfaitement aléatoire de 1 à 5 inclus. Malheureusement, ils ont renversé du cola d'une manière ou d'une autre, et il ne génère désormais que 2 pour tous les nombres de 1 à 4. Heureusement, le caractère aléatoire est préservé, mais 2 a une probabilité de 80% et 5 a une probabilité de 20%, et il n'y a pas 1, 3 ou 4 générés. À l'aide de cette source aléatoire (appelez-la BrokenRand()ou quelque chose de similaire), écrivez un générateur de nombres aléatoires qui produit des nombres de 1 à 5 chacun avec une probabilité égale de 20% avec le même caractère aléatoire parfait que la source d'origine.

Le programme le plus court gagne. Points bonus attribués pour le nombre minimal d'appels à BrokenRandun conseiller en matière de service client sélectionné démographiquement, répartis en fonction de l'âge et du sexe - c'est-à-dire moi.

Thomas O
la source

Réponses:

10

JavaScript - 69 caractères

Celui-ci utilise l' extracteur von Neumann pour générer des bits non biaisés; l'algorithme général est également décrit sur le site Web HotBits . Trois bits sont utilisés pour former un nombre compris entre 0 et 7. Tous les nombres 5 et supérieurs sont supprimés et 1 est ajouté à chacun des autres avant d'être imprimés. J'ai fait une simulation pour montrer que ce n'est pas fortement biaisé .

Vous devez fournir votre propre fonction r()pour accéder au 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())
Veuillez vous lever
la source
C'est vraiment bien fait! J'aime la façon dont vous court-circuitez la valeur d'incrémentation.
snmcdonald
Vous pourriez générer 7 bits et extraire 3 nombres aléatoires pour réduire les appels à BrokenRand, mais cela coûterait probablement quelques coups de plus
gnibbler
5

scala 79 caractères:

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

Maintenant, pour le vrai golf, l'alias defektRNG brokenRand est renommé b.

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

Comment ça marche: Le plus souvent, b renvoie une séquence de 2s. Mais si vous faites 5 appels à b, vous finirez très souvent avec un résultat de 4x2 et 1x5, c'est le deuxième événement le plus probable, et peut être 5-2-2-2-2, 2-5-2-2 -2, 2-2-5-2-2, 2-2-2-5-2 et 2-2-2-2-5.

Ceux-ci ont en commun que la somme est 4 * 2 + 5 = 13. L'index des cinq premiers peut être utilisé pour définir un nombre aléatoire valide. S'il y a plus ou moins un 5, une somme supérieure ou inférieure à 13, répétez.

Un compteur en «rnd» alias «r» peut montrer combien d'appels sont nécessaires en moyenne pour produire les numéros. Il y a 121 200 appels à r pour 50 000 numéros aléatoires, ce qui n'est pas impressionnant. :)

Utilisateur inconnu
la source
3

> <> (Poisson) - 55 octets

Mis à jour pour utiliser le même algorithme que @user unknown dans sa réponse scala

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

Il s'attend à ce que le générateur cassé soit connecté à stdin; voici le script python que j'ai utilisé . Le code correspond à la spécification Fish actuelle, mais j'ai utilisé une version modifiée de l'ancien interpréteur.

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

Je ferais un plus gros échantillon mais c'est lent.

cthom06
la source
2

GolfScript, 23 octets

Réponse tardive, mais comme cela vient d'apparaître en première page ...

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

Utilise le même algorithme que la solution Scala de l'utilisateur inconnu . Suppose que le générateur de nombres aléatoires biaisé est donné sous la forme d'un sous-programme GolfScript r; vous pouvez définir vous-même un RNG biaisé approprié, par exemple:

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

Voici un test rapide démontrant l'absence de parti pris. Malheureusement, le serveur GolfScript en ligne est assez lent, j'ai donc dû réduire la démonstration à seulement 100 échantillons pour la terminer à temps. Si vous exécutez le test localement avec l' interpréteur GolfScript , essayez d'augmenter le 100*à 1000*ou même 10000*.

(Le serveur GolfScript se bloque parfois de manière aléatoire et expire de toute façon. Si cela se produit pour vous, réessayez généralement le résout. Cela se produit également avec un autre code, et ne se produit que sur le serveur, pas sur mon propre ordinateur, donc je suis confiant que c'est un problème avec le serveur et non avec mon code.)

Ilmari Karonen
la source
-1

javascript, 160 caractères sans réduire la lisibilité aka optimisation

function giveRandom(){
    var result = Math.floor(5 * Math.random()) + 1;
    while(BrockenRand() != 5){
        result = Math.floor(5 * Math.random()) + 1;
    }
    return result;
}
www0z0k
la source
@ snmcdonald -certaines ne sont pas une faute de frappe, c'est un moyen d'améliorer js random par un générateur aléatoire parfait approuvant uniquement (totalement aléatoire!) 20% les résultats
www0z0k
Voulez-vous expliquer ce que BrockenBand()c'est, alors?
Mateen Ulhaq
6
Je pense que vous avez manqué le point
cthom06
@muntoo - sensBrockenRand
www0z0k
Enregistrez quelques octets de cette façon:function giveRandom(){return Math.ceil(Math.random()*5)}
user300375