Brain teaser

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Its a start :D

Answer 4

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...

Answer 5

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

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

@Kuba - I also solved it recursively. 😃

Answer 10

@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.

Answer 11

O.o

Answer 12

nice one @Hatsy 😃

Answer 13

gotta try this out

Answer 14

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

Answer 15

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%