your're are task: implement a random number generator which works according to the following specification:
takes two command-line arguments; first will be the seed, second will be how many numbers to generate
outputs numbers separated by newline to stdout
if called \(2^{32}\) times, it will output each \(x\) defined as \(0 <= x < 2^{32}\) exactly once
order of such outputs will not be trivially predictable, but it doesn't have to be cryptographically secure: \(0, 1, 2, 3 ... 2^{32}\) is not ok but an LSFR is
each seed should generate a different sequence, there should not be a single sequence with seeds working as offsets into it
you have one week. the shortest code (in bytes of source code or compiled executable) wins, but submissions will be scored in two separate categories: those that achieve uniqueness algorithmically and those that guarantee it by explicitly caching the results. the category which does not use caching should be seen as the more prestigious one since caching is a trivial hack and it will ruin performance and/or memory usage for large sequences
disregard, I suck cocks Edited on 22/01/2019 17:24.
py3 solution, no caching. guess how it works, you anuses↵
import struct↵
import random↵
import sys↵
i='I';s=struct;l=sys.argv;m=range;a=[b];exec('random.s%s'*2%('eed(l[1]);','huffle(a)'))↵
def g(x,y,z):↵
c=0xFF&(z>>8);d=0xFF&z;e=a[d^x[(4*y+0)%10]]^c;f=a[e^x[(4*y+1)%10]]^d;h=a[f^x[(4*y+2)%10]]^e; i=a[h^x[(4*y+3)%10]]^f;return((h<<8)+i)↵
def j(k,b):↵
c=0;d=(b[0]<<8)+b[1];e=(b[2]<<8)+b[3]↵
for _ in k:↵
e^=g(k,c,d)^c;c+=1;d^=g(k,c,e)^c;c+=1↵
return bytes((e>>8,d&0xFF,e>>8,d&0xFF))↵
for x in m(int(l[2])):↵
print(s.unpack(i,j(b'0'*12,s.pack(i,x)))[0])
disregard, I suck cocks
Name:
Anonymous2019-01-22 17:17
so just to be clear, you're essentially asking for a program that computes a permutation (bc uniqueness) of the 32-bit integers. Since each seed should generate a different permutation, you'd need a function F : nat -> nat -> nat, such that (F n) is a non-trivial permutation for each n. (and then just call it in sequence to print the first k numbers)
There are only finitely many permutations, so it's impossible to generate a different one for __every__ seed. There should be a requirement that we can assume the seed to have log(2^32-factorial) many bits, so there are at most 2^32-factorial different seeds.
Name:
Anonymous2019-01-22 17:24
python 3, no caching. try figuring out how it works, you anuses import struct import random import sys i='I';s=struct;l=sys.argv;m=range;a=[x for x in m(256)];exec('random.s%s'*2%('eed(l[1]);','huffle(a)')) def g(x,y,z): c=0xFF&(z>>8);d=0xFF&z;e=a[d^x[(4*y+0)%10]]^c;f=a[e^x[(4*y+1)%10]]^d;h=a[f^x[(4*y+2)%10]]^e; i=a[h^x[(4*y+3)%10]]^f;return((h<<8)+i) def j(k,b): c=0;d=(b[0]<<8)+b[1];e=(b[2]<<8)+b[3] for _ in k: e^=g(k,c,d)^c;c+=1;d^=g(k,c,e)^c;c+=1 return bytes((e>>8,d&0xFF,e>>8,d&0xFF)) for x in m(int(l[2])): print(s.unpack(i,j(b'0'*12,s.pack(i,x)))[0])
There are only finitely many permutations, so it's impossible to generate a different one for __every__ seed. There should be a requirement that we can assume the seed to have log(2^32-factorial) many bits, so there are at most 2^32-factorial different seeds.
OP here, your're are right, of course. sorry if I wasn't being clear
Name:
Anonymous2019-01-22 17:43
>>6,8 to be absolutely precise: you don't need to be able to generate exactly \(2^{32}!\) permutations, although doing that would certainly be impressive. if you have a 32-bit seed and each of them gets a unique permutation, that's ok. the solution in >>7 looks like it has \(255!\) solutions, which is even better. I just want to prevent anuses gaming the system by e.g. creating a single cyclic group and having the 'seed' be generator's starting point.
tl;dr if your're are seed acts like an actual seed, I'll accept it
Name:
Anonymous2019-01-22 22:54
warning, slow! also seed 0 means no randomness import System.Environment;import Data.List; a=(permutations[1..2^32]!!).(`mod`2^32).(*(2^31-1)) b x=take(y!!1)(a(y!!0)) where y=map(read::String->Int)x main=getArgs>>=(print.unlines.(map show).b)
Name:
Anonymous2019-01-23 7:03
>>10 this code manages to be as slow as the caching solution without actually caching!
the winner in the non-cached category is: >>15 the winner in the cached category is: fucking nobody because the only submitted entry (>>13) didn't meet the spec special award for strongest randomness and uniqueness guarantees goes to: >>7 (as this solution basically amounts to a block cipher in CTR mode)