У друга в компьютере есть дополнительная карта, которая генерирует совершенно случайное число от 1 до 5 включительно. К сожалению, они как-то пролили колу, и теперь она генерирует только 2 для всех чисел от 1 до 4. К счастью, случайность сохраняется, но вероятность 2 равна 80%, вероятность 5 - 20%, а 1, 3 или 4 сгенерированы. Используя этот случайный источник (назовите его BrokenRand()или что-то подобное), напишите работающий генератор случайных чисел, который производит числа от 1 до 5 с вероятностью равной 20% с той же идеальной случайностью, что и исходный источник.

Кратчайшая программа выигрывает. Бонусные баллы начисляются за минимальное количество BrokenRandбеспристрастных звонков с помощью демографически отобранных консультантов, специализирующихся на обслуживании клиентов, с разбивкой по возрасту и полу - т.е. мне.

JavaScript - 69 символов

При этом используется экстрактор фон Неймана для генерации несмещенных битов; общий алгоритм также описан на сайте HotBits . Три бита используются для формирования числа от 0 до 7. Все числа от 5 и выше отбрасываются, и 1 добавляется к каждому из остальных, прежде чем они будут напечатаны. я сделал симуляцию, чтобы показать, что это не сильно смещено .

Вы должны предоставить свою собственную функцию r()для доступа к ГСЧ.

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

Скала 79 символов:

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

Теперь для настоящего гольфа defactRNG alias brokenRand переименован в b.

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

Как это работает: Чаще всего b возвращает последовательность 2s. Но если вы сделаете 5 вызовов на b, вы очень часто закончите с результатом 4x2 и 1x5, это второе наиболее вероятное событие, и может быть 5-2-2-2-2, 2-5-2-2 -2, 2-2-5-2-2, 2-2-2-5-2 и 2-2-2-2-5.

Общее у них то, что сумма равна 4 * 2 + 5 = 13. Индекс первых пяти можно использовать для определения действительного случайного числа. Если больше или меньше одного 5, сумма больше или меньше 13, повторите.

Счетчик в 'rnd' aka 'r' может показать, сколько вызовов необходимо в среднем, чтобы получить числа. На 50 000 случайных номеров поступило 121 200 звонков, что не впечатляет. :)

> <> (Рыба) - 55 байт

Обновлен, чтобы использовать тот же алгоритм, что и @user unknown в своем ответе scala

<? V = D + &: я & + &: я & + &: я & + &: & я: я
 0
 > 1 + $ 5 (vnao;
 ^ <

Он ожидает, что сломанный генератор будет подключен к stdin; вот скрипт Python, который я использовал . Код соответствует текущей спецификации Fish, но я использовал модифицированную версию старого интерпретатора.

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

Я бы сделал большую выборку, но она медленная.

GolfScript, 23 байта

Поздний ответ, но так как это только что появилось на первой странице ...

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

Использует тот же алгоритм, что и решение Scala от неизвестного пользователя . Предполагается, что смещенный генератор случайных чисел задан как подпрограмма GolfScript с именем r; Вы можете определить подходящий смещенный RNG самостоятельно, например, как:

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

Вот быстрый тест, демонстрирующий отсутствие предвзятости. К сожалению, онлайн-сервер GolfScript работает довольно медленно, поэтому мне пришлось сократить демонстрацию до 100 образцов, чтобы завершить ее вовремя. Если тест выполняется локально с помощью интерпретатора GolfScript , попробуйте увеличить 100*до 1000*или даже 10000*.

(Сервер GolfScript также иногда произвольно зависает и останавливается в любом случае. Если это происходит для вас, повторная попытка обычно решает его. Это происходит и с другим кодом, и происходит только на сервере, а не на моем собственном компьютере, поэтому я уверен что это проблема с сервером, а не с моим кодом.)

JavaScript, 160 символов без снижения читабельности ака оптимизация

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