Repariere eine kaputte Zufallsfunktion

18

Ein Freund hat eine Zusatzkarte in seinem Computer, die eine perfekte Zufallszahl von 1 bis einschließlich 5 generiert. Leider haben sie irgendwie Cola darauf verschüttet, und es werden nur noch 2er für alle Zahlen von 1 bis 4 generiert. Glücklicherweise bleibt die Zufälligkeit erhalten, aber 2 hat eine Wahrscheinlichkeit von 80% und 5 hat eine Wahrscheinlichkeit von 20%, und es gibt keine 1er, 3er oder 4er generiert. BrokenRand()Schreiben Sie mit dieser Zufallsquelle (nennen Sie es oder ähnliches) einen funktionierenden Zufallszahlengenerator, der Zahlen von 1 bis 5 mit einer Wahrscheinlichkeit von 20% mit der gleichen perfekten Zufälligkeit wie die ursprüngliche Quelle erzeugt.

Kürzeste Sendung gewinnt. Bonuspunkte, die für die Mindestanzahl von Anrufen vergeben werden, die BrokenRandvon einer demografisch ausgewählten Beratungsfirma mit Fokus auf Kundenservice unparteiisch entgegengenommen werden, aufgeschlüsselt nach Alter und Geschlecht - dh ich.

Thomas O.
quelle

Antworten:

10

JavaScript - 69 Zeichen

Dies verwendet den von Neumann-Extraktor , um unverzerrte Bits zu erzeugen; Der allgemeine Algorithmus ist auch auf der HotBits-Website beschrieben . Drei Bits werden verwendet, um eine Zahl von 0 bis 7 zu bilden. Alle Zahlen ab 5 werden verworfen, und vor dem Drucken wird zu jedem Rest eine 1 hinzugefügt. Ich habe eine Simulation gemacht, um zu zeigen, dass dies nicht stark voreingenommen ist .

Sie müssen Ihre eigene Funktion bereitstellen, r()um auf das RNG zuzugreifen.

 for(;;v<5&&alert(v+1))for(v=i=0;i<3;a-b&&(v*=2,v+=a<b,i++))b=r(a=r())
PleaseStand
quelle
Das ist wirklich gut gemacht! Mir gefällt, wie Sie den Inkrementwert kurzschließen.
snmcdonald
Sie könnten 7 Bits generieren und 3 Zufallszahlen extrahieren, um die Aufrufe von BrokenRand zu reduzieren, aber das würde wahrscheinlich ein paar weitere Schläge
kosten
5

Scala 79 Zeichen:

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

Für das echte Golfspiel wird der Alias ​​"defektRNG brokenRand" in "b" umbenannt.

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

So funktioniert es: Meistens gibt b eine Folge von 2s zurück. Wenn Sie jedoch 5 Anrufe nach b tätigen, werden Sie sehr oft mit einem Ergebnis von 4x2 und 1x5 enden. Dies ist das zweitwahrscheinlichste Ereignis und kann 5-2-2-2-2, 2-5-2-2 sein -2, 2-2-5-2-2, 2-2-2-5-2 und 2-2-2-2-5.

Diesen ist gemeinsam, dass die Summe 4 * 2 + 5 = 13 ist. Der Index der ersten fünf kann verwendet werden, um eine gültige Zufallszahl zu definieren. Wenn es mehr oder weniger als eine 5 gibt, eine Summe größer oder kleiner 13, wiederholen Sie.

Ein Zähler in 'rnd' oder 'r' kann anzeigen, wie viele Anrufe durchschnittlich erforderlich sind, um die Nummern zu produzieren. Es gibt 121 200 Anrufe für 50 000 Zufallszahlen, was nicht beeindruckend ist. :)

Benutzer unbekannt
quelle
3

> <> (Fisch) - 55 Bytes

Aktualisiert, um den gleichen Algorithmus wie @user zu verwenden, der in seiner Scala-Antwort unbekannt ist

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

Es wird erwartet, dass der defekte Generator an stdin angeschlossen ist. Hier ist das Python-Skript, das ich verwendet habe . Der Code stimmt mit der aktuellen Fish-Spezifikation überein, aber ich habe eine modifizierte Version des alten Interpreters verwendet.

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

Ich würde ein größeres Sample machen, aber es ist langsam.

cthom06
quelle
2

GolfScript, 23 Bytes

Späte Antwort, aber da dies zufällig auf der Titelseite auftauchte ...

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

Verwendet den gleichen Algorithmus wie die Scala-Lösung des Benutzers unknown . Es wird davon ausgegangen, dass der voreingenommene Zufallszahlengenerator als benannte GolfScript-Unterroutine angegeben ist r. Sie können einen geeigneten voreingenommenen RNG selbst definieren, z. B .:

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

Hier ist ein kurzer Test, der zeigt, dass es an Voreingenommenheit mangelt. Leider ist der Online-GolfScript-Server etwas langsam, so dass ich die Demo auf nur 100 Samples reduzieren musste, um sie pünktlich fertigzustellen. Wenn Sie den Test lokal mit dem GolfScript-Interpreter ausführen , erhöhen Sie den Wert100* auf 1000*oder sogar 10000*.

(Der GolfScript-Server friert auch manchmal nach dem Zufallsprinzip ein und es tritt trotzdem eine Zeitüberschreitung auf. Wenn dies bei Ihnen auftritt, wird dies normalerweise durch einen erneuten Versuch behoben. Dies geschieht auch mit anderem Code und nur auf dem Server, nicht auf meinem eigenen Computer. Ich bin also zuversichtlich dass es ein Problem mit dem Server ist und nicht mit meinem Code.)

Ilmari Karonen
quelle
-1

Javascript, 160 Zeichen ohne Einschränkung der Lesbarkeit aka Optimierung

function giveRandom(){
    var result = Math.floor(5 * Math.random()) + 1;
    while(BrockenRand() != 5){
        result = Math.floor(5 * Math.random()) + 1;
    }
    return result;
}
www0z0k
quelle
@ snmcdonald - einige davon sind kein Tippfehler, es ist eine Möglichkeit, js zufällig zu verbessern, indem ein perfekter Zufallsgenerator nur (total zufällig!) 20% der Ergebnisse
genehmigt
Möchtest BrockenBand()du erklären, was dann ist?
Mateen Ulhaq
6
Ich denke, Sie haben den Punkt verpasst
cthom06
@ muntoo - meaningBrockenRand
www0z0k
Speichern Sie ein paar Bytes auf diese Weise:function giveRandom(){return Math.ceil(Math.random()*5)}
user300375