Random
Take a look at the following puzzle:
"Given a function which produces a random integer from 1 to 5, write one that produces a random integer from 1 to 7"
I immediately thought of this:
function naiveRand(f){
return (f() + f()) % 7 + 1;
}But it is not random enough, since we have more chances of getting 7
than any other number; with these two executions of f, each one producing
an interger from 0 to 5 we have 25 possibilities:
1 : 4 chances: 5+2, 2+5, 3+4, 4+3 2 : 3 chances: 3+5, 5+3, 4+4 3 : 3 chances: 4+5, 5+4, 1+1 4 : 3 chances: 1+2, 2+1, 5+5 5 : 3 chances: 3+1, 1+3, 2+2 6 : 4 chances: 1+4, 4+1, 2+3, 3+2 7 : 5 chances: 5+1, 1+5, 4+2, 2+4, 3+3
Or check it in real life:
We can see that this results are not uniform there is always this
peak on the right, so in my attempt to flatten out this I added a few more
executions of f():
function newRand(){
return (
f() +
f() +
f() +
f() +
f() +
f()
) % 7 + 1;
}The number of combinations is 5^6 (15625) and as you can see in the graphic
above, it seems pretty flat, but if you count the number of chances
of geting each integer from 1 to 7 you'll find this:
1 : 2229 2 : 2224 3 : 2224 4 : 2229 5 : 2238 6 : 2243 7 : 2238
Number 6 is slightly more likely to come out. So how could this task be achieved? I spent around an hour trying to think of a better solution, but I couldn’t. Surfing the web I found a couple of different approaches, none of them was good enough until I found Simon's, which I think is more elegant and effectively random, or at least as random as the given function should be:
function simonsRand(){
var randtab = [
[1,1,1,2,2],
[2,3,3,3,4],
[4,4,5,5,5],
[6,6,6,7,7],
[7,0,0,0,0]
];
var r = 0;
while(r == 0)
r = randtab[ f() -1][ f() -1];
return r;
}By creating this table, he uses just two executions of f() to produce a [i,j] position.
The table contains each integer from 0 to 7 exactly 3 times which is the best way
to fill the table with minimum wasted spaces, if it gets 0, just repeat.
We end up with 1/25 possibilities of hitting each position.