Znajomy ma w komputerze dodatkową kartę, która generuje całkowicie losową liczbę od 1 do 5 włącznie. Niestety rozlali na nią colę i teraz generuje tylko 2 dla wszystkich liczb od 1 do 4. Na szczęście losowość zostaje zachowana, ale prawdopodobieństwo 2 wynosi 80%, a prawdopodobieństwo 5 wynosi 20% i nie ma Wygenerowano 1, 3 lub 4. Korzystając z tego losowego źródła (nazwij to BrokenRand()lub coś podobnego), napisz działający generator liczb losowych, który produkuje liczby od 1 do 5, z prawdopodobieństwem równym 20% z tą samą idealną losowością jak oryginalne źródło.

Najkrótszy program wygrywa. Punkty premiowe przyznawane za minimalną liczbę połączeń BrokenRandbezstronnie przez wybraną demograficznie firmę doradczą skoncentrowaną na obsłudze klienta, w podziale na wiek i płeć - tj. Mnie.

JavaScript - 69 znaków

Używa to ekstraktora von Neumanna do generowania obiektywnych bitów; ogólny algorytm jest również opisany na stronie HotBits . Trzy bity są używane do utworzenia liczby od 0 do 7. Wszystkie liczby 5 i więcej są odrzucane, a 1 jest dodawany do każdej z pozostałych przed wydrukowaniem. Przeprowadziłem symulację, aby pokazać, że nie jest to zbyt stronnicze .

Musisz podać własną funkcję r()dostępu do 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 znaków:

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

Teraz dla prawdziwego golfa zmieniono alias defektRNG na brokenRand na b.

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

Jak to działa: Najczęściej b zwraca ciąg 2. Ale jeśli wykonasz 5 połączeń do b, bardzo często zakończysz wynikiem 4x2 i 1x5, jest to drugie najbardziej prawdopodobne zdarzenie i może być 5-2-2-2-2, 2-5-2-2 -2, 2-2-5-2-2, 2-2-2-5-2 i 2-2-2-2-5.

Łączy je to, że suma wynosi 4 * 2 + 5 = 13. Indeks pierwszych pięciu można użyć do zdefiniowania prawidłowej liczby losowej. Jeśli jest więcej lub mniej niż jedna 5, suma większa lub mniejsza 13, powtórz.

Licznik w „rnd” aka „r” może pokazywać, ile połączeń potrzeba średnio do wyprodukowania numerów. Istnieje 121 200 połączeń z r dla 50 000 losowych numerów, co nie robi wrażenia. :)

> <> (Ryba) - 55 bajtów

Zaktualizowano, aby używał tego samego algorytmu, co @user nieznany w swojej odpowiedzi Scala

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

Oczekuje, że uszkodzony generator zostanie podłączony do standardowego wejścia; oto skrypt Pythona, którego użyłem . Kod odpowiada bieżącej specyfikacji Fisha, ale użyłem zmodyfikowanej wersji starego interpretera.

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

Zrobiłbym większą próbkę, ale jest wolny.

GolfScript, 23 bajty

Późna odpowiedź, ale odkąd to się właśnie pojawiło na pierwszej stronie ...

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

Używa tego samego algorytmu, co rozwiązanie Scala dla nieznanego użytkownika . Zakłada, że ​​tendencyjny generator liczb losowych jest podany jako podprogram Golfs o nazwie r; możesz sam zdefiniować odpowiedni stronniczy RNG, np. jako:

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

Oto szybki test wykazujący brak uprzedzeń. Niestety, internetowy serwer GolfScript działa dość wolno, więc musiałem ograniczyć demonstrację do zaledwie 100 próbek, aby ukończyć ją na czas. Jeśli uruchamiasz test lokalnie za pomocą interpretera GolfScript , spróbuj zwiększyć wartość 100*do 1000*lub nawet 10000*.

(Serwer GolfScript czasami czasami zawiesza się i limit czasu. Jeśli tak się stanie, ponowna próba zwykle go rozwiązuje. Dzieje się tak również z innym kodem i dzieje się to tylko na serwerze, a nie na moim komputerze, więc jestem pewien że jest to problem z serwerem, a nie z moim kodem).

javascript, 160 znaków bez zmniejszania czytelności czyli optymalizacji

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