+ 37

# Brain teaser

Imagine you have a function that returns either 1 or 2 with the same statistical probability. Make a function (using only the given function, no built functions allowed) that returns 1, 2 or 3 with the same probability. Generate a set of 90000 numbers. Test conditions: 1. 1, 2, 3 should appear about the same number of times with a threshold of 0.05%. 2. sequence of at least four consecutive 1s, 2s and 3s should appear at least once in that set.

15 odpowiedzi

+ 34

A humble trial that I have come up with.
// Assuming preexisting function which returns either 1 or 2.
int randval();
// self-defined function to return either 1, 2 or 3 with equal probability
int selfval()
{
int i, j;
while (true)
{
i = randval();
j = randval();
if ((i - 1) && (j - 1)) return 1;
if (!(i - 1) && !(j - 1)) return 2;
if (!(i - 1) && (j - 1)) return 3;
}
}
// theoretically, selfval() has equal probability to generate either 1, 2 or 3 (0.25 each). The remaining 0.25 will cause a loop, reassigning values to i and j and re-evaluating final return value.

+ 16

By the way - for those more interested also in failed (I mean *really* failed) projects on pseudoRNGs - ever heard of IBM's RANDU?
V(j+1) = 65539 * V(j) % 2**31
See how the big ones can also fail big time :)
https://en.m.wikipedia.org/wiki/RANDU

+ 16

https://code.sololearn.com/cUeWaA6JIHs6/#cpp
edit: sorry, forgot that stuff. :D
Its a start :D

+ 13

Following @Hatsy's trail I made the recursive version:
from random import randint as r
def prim():
return r(1,2)
def bis():
b1, b2 = prim(), prim()
if (b1, b2) != (1, 2):
return 2*b1-b2
return bis()
for i in range(30):
print(bis())
# should cast around 10 ones, 10 twos and 10 threes in longterm perspective...

+ 12

So you're saying: write yourself your own RNG? :)

+ 11

Will try this later. Thanks for the brain teaser. :>

+ 10

That is just another proof that recursion can theoretically always be replaced with simple looping.
At least until memory overflow... :)
There is one major drawback of such an approach, though. I can't think of a way to 'seed' it effectively.

+ 8

I had to tackle with that somewhere else. Though you might be interested, it's a good teaser.

+ 8

@Kuba - I also solved it recursively. 😃

+ 7

@Kuba - you can use the build in functionality for the first function, I.e
function one_two (){
return Math.floor(Math.random()*2 + 1);
},
but the second one should be based on the first one.

+ 6

O.o

+ 5

nice one @Hatsy 😃

+ 5

gotta try this out

+ 5

Here's how our PRNG's aren't secure (and more importantly, aren't meant to be):
https://code.sololearn.com/cBBw0NzqjlFL/?ref=app
I'm reversing the previous value from the current one. In that hot mess (sorry, separating my/public code) there are, I distractedly think:
- the actual PRNG (XORShift128+) we get by default (Python, c++ snippets, same as used in semi-recent browsers).
- maybe (or still private)...the worse PRNG algorithm used not so long ago.
I've been meaning to machine learn/predict the background seeds (is game over) but...priorities.
OS provides better rands than langs, e.g.
Python:
from Random import SystemRandom
c++:
https://msdn.microsoft.com/en-us/library/windows/desktop/aa379942(v=vs.85).aspx
Web:
window.crypto.getRandomValues() from DOM:
https://code.sololearn.com/WVxar9XmY1N4/?ref=app
Or any lang: true randoms from a public service:
https://code.sololearn.com/WxkraG1imWtm/?ref=app

+ 4

the one from @hatsy is good, it does what is needed, but is expensive. this one need less flops to the same:
public int myFunction(){
int a = randVal();
int b = randVal();
if( a == 1 && b == 2){
// return this function in order to
//make all nums appear with same %
return myFunction();
}
a = a*b;
if(a == 4){
a--;
}
return a;
}
// the recursive call is donr in order to eliminate one //chance of getting the result '2', which would have //50% chances instead of 33%