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

22nd Jun 2017, 1:47 PM
Nikolay Nachev
Nikolay Nachev - avatar
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.
22nd Jun 2017, 3:16 PM
Hatsy Rei
Hatsy Rei - avatar
+ 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
22nd Jun 2017, 9:26 PM
Kuba Siekierzyński
Kuba Siekierzyński - avatar
+ 16
https://code.sololearn.com/cUeWaA6JIHs6/#cpp edit: sorry, forgot that stuff. :D Its a start :D
23rd Jun 2017, 1:01 AM
jay
jay - avatar
+ 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...
22nd Jun 2017, 8:40 PM
Kuba Siekierzyński
Kuba Siekierzyński - avatar
+ 12
So you're saying: write yourself your own RNG? :)
22nd Jun 2017, 1:56 PM
Kuba Siekierzyński
Kuba Siekierzyński - avatar
+ 11
Will try this later. Thanks for the brain teaser. :>
22nd Jun 2017, 2:03 PM
Hatsy Rei
Hatsy Rei - avatar
+ 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.
22nd Jun 2017, 9:09 PM
Kuba Siekierzyński
Kuba Siekierzyński - avatar
+ 8
I had to tackle with that somewhere else. Though you might be interested, it's a good teaser.
22nd Jun 2017, 1:48 PM
Nikolay Nachev
Nikolay Nachev - avatar
+ 8
@Kuba - I also solved it recursively. 😃
22nd Jun 2017, 9:03 PM
Nikolay Nachev
Nikolay Nachev - avatar
+ 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.
22nd Jun 2017, 3:04 PM
Nikolay Nachev
Nikolay Nachev - avatar
+ 6
O.o
22nd Jun 2017, 2:35 PM
jay
jay - avatar
+ 5
nice one @Hatsy 😃
22nd Jun 2017, 3:28 PM
Nikolay Nachev
Nikolay Nachev - avatar
+ 5
gotta try this out
22nd Jun 2017, 4:00 PM
Nomeh Uchenna Gabriel
Nomeh Uchenna Gabriel - avatar
+ 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
25th Jun 2017, 2:13 PM
Kirk Schafer
Kirk Schafer - avatar
+ 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%
24th Jun 2017, 8:56 AM
rule 31
rule 31 - avatar