Fix a broken random function

Question

A friend has an add-on card in their computer which generates a perfectly random number from 1 to 5 inclusive. Unfortunately, they spilt cola on it somehow, and it now generates only 2's for all numbers from 1 to 4. Luckily the randomness is preserved, but 2 has a probability of 80% and 5 has a probability of 20%, and there are no 1's, 3's or 4's generated. Using this random source (call it BrokenRand() or something similar), write a working random number generator which produces numbers from 1 to 5 each with an equal 20% probability with the same perfect randomness as the original source.

Shortest program wins. Bonus points awarded for the minimum number of calls to BrokenRand impartially by a demographically-selected customer service focus consultancy, broken down by age and sex - i.e. me.

Answer 1

JavaScript - 69 characters

This uses the von Neumann extractor to generate unbiased bits; the general algorithm is also described on the HotBits website. Three bits are used to form a number from 0 to 7. All numbers 5 and above are discarded, and 1 is added to each of the rest before they are printed. I made a simulation to show that this is not heavily biased.

You need to provide your own function r() to access the 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())

Answer 2

scala 79 chars:

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

Now for the real golf, defektRNG alias brokenRand is renamed to b.

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

How it works: Most often, b returns a sequence of 2s. But if you do 5 calls to b, you will very often end with a result of 4x2 and 1x5, it is the second most probable event, and can be 5-2-2-2-2, 2-5-2-2-2, 2-2-5-2-2, 2-2-2-5-2 and 2-2-2-2-5.

These have in common, that the sum is 4*2+5=13. The index of the first five can be used to define a valid random number. If there is more or less than one 5, a sum greater or lower 13, repeat.

A counter in 'rnd' aka 'r' can show how many calls are necessary in average to produce the numbers. There are 121 200 calls to r for 50 000 random numbers, which is not impressing. :)

Answer 3

><> (Fish) - 55 bytes

Updated to use the same algorithm as @user unknown in his scala answer

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

It expects the broken generator to be connected to stdin; here's the python script I used. The code matches the current Fish spec, but I used a modified version of the old interpreter.

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

I'd do a bigger sample but it's slow.

Answer 4

GolfScript, 23 bytes

Late answer, but since this just happened to pop up on the front page...

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

Uses the same algorithm as user unknown's Scala solution. Assumes that the biased random number generator is given as a GolfScript subroutine named r; you can define a suitable biased RNG yourself e.g. as:

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

Here's a quick test demonstrating lack of bias. Unfortunately, the online GolfScript server is kind of slow, so I had to cut the demonstration down to just 100 samples to make it complete on time. If running the test locally with the GolfScript interpreter, try increasing the 100* to 1000* or even 10000*.

(The GolfScript server also sometimes randomly freezes and times out anyway. If this happens for you, trying again usually solves it. It happens with other code too, and only happens on the server, not on my own computer, so I'm confident that it's a problem with the server and not with my code.)

Answer 5

Python 3, 119 bytes

def F():
  l=[]
  while 1:
    l=[]
    for i in range(5):
      l.append(B())
    if l.count(5) == 1:
      return l.index(5)

Could be golfed to below 100 probably, but it's decent for now. Have no idea how a Python answer (or one with this method) hasn't popped up. Assumes the broken random function is B.