Adaptive randomisation

Question

Given a number \$n ≥ 2\$, a blackbox function \$f\$ that takes no arguments and returns a random integer in the range 0...n-1 inclusive, and a number \$m ≥ n\$, your challenge is to generate a random integer in the range 0...m-1 inclusive. You may not use any nondeterministic builtins or behaviour, your only source of randomisation is \$f\$.

The number you produce must be uniformly random. \$m\$ is not limited to powers of \$n\$.

One way to do this could be to generate \$\operatorname{ceil}(\log_n(m))\$ random numbers, convert these from base \$n\$ to an integer, and reject-and-try-again if the result's greater than or equal to \$m\$. For example, the following JS could do this:

function generate(n,m,f){
 let amountToGenerate = Math.ceil(Math.log(m)/Math.log(n)) // Calculating the amount of times we need to call f
 let sumSoFar = 0; 
 for(let i = 0; i < amountToGenerate; i++){ // Repeat that many times...
 sumSoFar *= n; // Multiply the cumulative sum by n
 sumSoFar += f() // And add a random number
 } 
 if(sumSoFar >= m){ // If it's too big, try again
 return generate(n,m,f); 
 } else { // Else return the number regenerated
 return sumSoFar
 }
}

An invalid solution could look something like this:

function generate(n,m,f){
 let sumSoFar = 0;
 for(let i = 0; i < m/n; i++){ // m/n times...
 sumSoFar += f() // add a random number to the cumulative sum
 }
 return sumSoFar
}

This is invalid because it takes the sum of \$\frac{m}{n}\$ calls of f, so the randomness is not uniform, as higher/lower numbers have a smaller chance of being returned.

\$f\$ is guranteed to produce uniformly random integers, and can be independently sampled as many times as you want.

Instead of taking \$f\$ as a function, you may also take it as a stream or iterator of values, or an arbitrarily long list of values. The ranges may be 1...n instead of 0...n-1.

Scoring

This is code-golf, shortest wins!

• xnor: A method to steal: Make a list of m outputs from f, if it has a single 0 output its position, otherwise retry.
• emanresu A: @tsh f is guranteed to produce uniformly random integers.

Answer 1

Jelly, (削除) 6 (削除ここまで) 5 bytes

ÇÐṀḊ¿

Try it online!

A monadic link taking m as its argument and expecting the blackbox function to be in the previous link (e.g. header on TIO). Thanks to @JonathanAllan for pointing this out as per this meta post and also for saving a byte with a suggested switch to 1 indexing!

Explanation

 | Implicit range 1..m
 Ḋ¿ | While list length > 1 (literally while the list with its first member removed is non-empty):
 ÐṀ | - Take the list member(s) that are maximal when:
Ç | - The supplied function is run for each list member

---

If the function had to be provided as an argument, here is an alternative:

Jelly, 8 bytes

ṛ4V$ÐṀḊ¿

Try it online!

A full program taking m and the Jelly code for f as its two arguments. If it’s mandatory to also take n, this can be provided as an (unused) third argument.

Explanation

 | Implicit range 1..m
 Ḋ¿ | While list length > 1 (literally while the list with its first member removed is non-empty):
 $ÐṀ | - Take the list member(s) that are maximal when:
 ṛ4V | - The supplied function is run for each list member

---

Previous answer: Jelly, 16 bytes

3lĊ5V¤€ḅʋ4¤<3¬$¿

Try it online!

A full program that takes n, m and the Jelly code for f as its arguments and prints the resulting random number to STDOUT.

Explanation

 <3¬$¿ | While not < m:
3 ʋ4¤ | - Do the following, taking m as the left argument and n as the right:
 l | - m log n
 Ċ | - Ceiling
 5V¤€ | - Execute f that many times
 ḅ | - Convert from base n

Answer 2

Wolfram Language (Mathematica), (削除) 40 (削除ここまで) 39 bytes

r&@While@!(r=Nest[nn#3+#2[],0,#])<#&

Try it online!

Input [m, f, n]. Interprets m random digits in base n until the result is in [0, m).

Answer 3

J, ^{37 32} 26 bytes

1 :'$:@[`]@.(=&#)I.@:u@$~'

Try it online!

-6 bytes thanks to xnor's suggested method.

Will overflow the stack for larger inputs since it recurses, but works in theory.

base-n method, modified, ³⁷ 32 bytes

1 :'([#.u@#~)/@[^:(]>:1{[)^:_&_'

Try it online!

Uses suggested method, except instead of taking the log first just generates m random base-n digits. This makes it much slower, but saves 5 bytes.

The solution is a J adverb, which modifies the black box function, and takes n as the left arg and m as the right arg.

base n method, fast, 37 bytes

1 :'([#.>.@^.u@#[)/@[^:(]>:1{[)^:_&_'

Try it online!

Answer 4

Husk, (削除) 17 (削除ここまで) (削除) 15 (削除ここまで) 13 bytes

Thanks to xnor for the inspiration for the method: here it's taken to an even-more-inefficient extreme by repeatedly generating m random numbers until all except one are zero, and the only non-zero one is 1

1ドルḟo=1ΣCm`%1∞

Try it online!

Husk is usually rather badly-suited for challenges involving randomness, since it has no built-in random number generator. So it's very welcome to have a challenge where a random number generator is assumed as a black-box function!

In this case, the black-box random number function is assumed to be located on line 2 (called using the Husk command "1").
However, obviously, without actually having this function it's tricky to test the code, so the TIO link substitutes the last few bytes m`%1∞ and input n for a pre-generated-by-me list of random integers between zero and one (so n equals 2).

 ∞ # infinitely repeat arg1;
 m # now, for each element n of this list
 `%1 # call black-box function 1, and return the result modulo n;
 C # now cut this infinite list into sublists of length m = arg2
 ḟo # Return the first sublist for which
 Σ # the sum
 =1 # is equal to 1;
1ドル # what's the index of 1 in this sublist?

Note: the m`%1∞ construction to get the infinite list of random numbers might seem (and is) a bit clunky. This is because (I think), not having any non-deterministic functinos, Husk doesn't have or normally need a higher-order function that will repeat a particular function that takes no arguments.
Luckily in this case, we know that the output of our black-box function is unchanged modulo n, so we can 'use-up' an argument without changing the output.
Here's a Try it online link to the m`%1∞ bit on its own, here with a function on line 2 that simply returns the number 7 each time it's called. Try to pretend that this is a random number...

Answer 5

R, (削除) 70 (削除ここまで) (削除) 69 (削除ここまで) 62 bytes

(or R>4.1, (削除) 56 (削除ここまで) 55 bytes)

Edit: -7 bytes thanks to pajonk

function(m,f){while(sum(F)!=1)for(i in 1:m)F[i]=!f();which(F)}

Try it online!

Port of (削除) my Husk answer (削除ここまで) xnor's approach. Keeps generating sequences of m random numbers until we get one that contains a single 0: then we output the position of the 0. Obviously this is not very efficient, but at least its significantly better than waiting for sequences of all zeros with a single 1 (previous version)...

As explained by Nick Kennedy in his R answer, R] version >4.1 lets us exchange "function" for "\" to save 7 bytes, but unfortunately we can't link to it on TIO or rdrr.io (yet).

• pajonk: For R<4.1 62 bytes (this approach matches 55 bytes in R>=4.1)
• user100887: crossed out H is still H

Answer 6

Japt, (削除) 12 (削除ここまで) 10 bytes

Based on xnor's suggested method in the challenge comments. Takes m as the first input n as the second and assigns f to variable W. Outputs a singleton array

ÈÊÉ}f@oW ð

Try it or check the distribution over 1000 runs (warning: may take a while to complete)
(All 3 inputs are taken in the header, where each line is assigned to one of Japt's input variables in order. The first line is m, the second n and the 3rd f. Doing this makes no difference to the main programme, saving no bytes; it's done purely to keep everything in one place for easier testing as functions cannot be taken as direct input by Japt.)

Black box function W

{Vö :Implicit input of integer V=n
{ :Function
 Vö : Random int in [0,V)

Main programme

ÈÊÉ}f@oW ð :Implicit input of integer U=m
È :Left function, taking an array as argument
 Ê : Length
 É : Subtract 1
 } :End left function
 f :Run the right function continuously, returning the first result that returns falsey (0) when passed through the left function
 @ :Right function
 o : Range [0,U)
 W : Run each through W
 ð : 0-based indices of truthy (non-zero) elements

• Dominic van Essen: The 4-byte version seems distinctly non-uniform...
• Shaggy: Thanks, @DominicvanEssen, meant to remove that after running a similar distribution test over a few runs of 10k; rarely did 2 make an appearance at all, 1 showed up once and 0 never featured.

Answer 7

Haskell, (削除) 49 (削除ここまで) 47 bytes

m!l|[x]<-[x|(x,1)<-zip[1..m]l]=x|1>0=m!drop m l

Try it online!

Implements xnor's algorithm

Make a list of \$m\$ outputs from \$f\$, if it has a single \0ドル\$ output its position, otherwise retry.

However we don't need to make a list since we take a list as the input.

We also use \1ドル\dots n\$ ranges because it saves us 2 bytes.

• wasif: For some reason it always seems to output 3 (sorry I don't know Haskell if I am wrong please correct me)
• Wheat Wizard: @wasif That's because 3 is the correct answer for the test data provided on TIO.

Answer 8

Python 3.8 (pre-release), 72 bytes

f=lambda m,g:(l:=[g()for x in"1"*m]).count(1)==1and-~l.index(1)or f(m,g)

Try it online!

Uses @xnor's method

-6 and fix thanks to @ovs

Generates the blackbox function for m times, and try to pick the index of 0 from it, if not present recurse.

Looks like the relevant function Dosen't need to take n at all, because it is hardcoded inside g()

Also it is needed to check if list has only one zero, so the choosing remains uniform

• xnor: I think it's necessary to check that the list has exactly one zero, because otherwise taking the leftmost one biases towards smaller outputs.
• wasif: @xnor oh sorry edited now
• wasif: @ovs I wonder why it dosen't return 0, 0 can be even in the first position of the random items list, then where is the problem?
• ovs: If l.index(0) evaluates to 0, this is falsy and or f(m,g) results into a recursive call. I think changing to 1-indexing is the easiest fix: tio.run/…
• tsh: stop condition (l:=[g()for x in"1"*m]).count(1)==1 may be replaced by sum(l:=[g()for x in"1"*m])+~m, and find out the only 2 there, as long as you don't care about probability of stack overflow...

Answer 9

R >= 4.1, (削除) 67 (削除ここまで) 64 bytes

\(m,f,x=1:m){while(x-max(x))x=x[max(y<-sapply(x,\(z)f()))==y];x}

Try it online!

An R translation of my Jelly answer. TIO link uses function in place of \ since TIO isn’t on R 4.1 yet.

Thanks to @DominicVanEssen for saving 3 bytes!

If it were permissible to require that the Blackbox function take a single unused argument, this would do for 61:

R >= 4.1, (削除) 64 (削除ここまで) 61 bytes

\(m,f,x=1:m){while(x-max(x))x=x[max(y<-sapply(x,f))==y];x}

Try it online!

• Dominic van Essen: Save 3 bytes by rearrangement and changing to while(x-max(x))

Answer 10

JavaScript (V8), (削除) 63 (削除ここまで) (削除) 61 (削除ここまで) 60 bytes

(m,f,r=(i=m,p)=>i?f()?r(i-1,p):p?r():r(i-1,i):p||r())=>r()-1

Try it online!

Using xnor's method. The recursive function r(i,p) counts down from i = m while i > 0. If finds a zero f() it records position i as p except if there is already a p it restarts by calling r(). If i gets to zero and there is a p it returns p-1 as the result otherwise it restarts.

• emanresu A: Nice answer! By the way, you don't need to take n if you're not using it.
• Dominic van Essen: "The ranges may be 1...n instead of 0...n-1" so I think you can just return p to save another 2 bytes...?

Answer 11

Python 3.8 (pre-release), 70 bytes

h=lambda m,n,f:h(m,n,f)if(s:=sum(n**k*f()for k in range(m)))>=m else s

Try it online!

Generates a random number up to n^m (always larger than m) with n invocations of f, then retries if the result is >=m.

Blows up the stack for large n and m, because n^m is much larger than m.

Answer 12

Charcoal, 16 bytes

NθW⊖Noυ0≔EθNυI⌕υ0

Try it online! Link is to verbose version of code. Uses the method @xor suggested in a comment to the question. Takes m and a stream of random integers as input. Explanation:

Nθ

Input m.

W⊖Noυ0

Repeat until the predefined empty list contains exactly one zero.

≔EθNυ

Input m random integers to the predefined empty list.

I⌕υ0

Output the position of the zero.

24 bytes for fastest code:

NθNη≔ηζW¬‹ζη≔↨E↨⊖ηθNθζIζ

Try it online! Link is to verbose version of code. Takes input as a stream of random integers. Explanation:

NθNη

Input n and m.

≔ηζ

Start with m as the trial result (because we know it is too big).

W¬‹ζη

Repeat until a usable result is achieved.

≔↨E↨⊖ηθNθζ

Input the minimum number of random digits (obtained by converting m-1 to base n) and convert that to base n.

Iζ

Output the final random integer.

Answer 13

APL(Dyalog Unicode), ^{(削除) (削除ここまで)}19 bytes ^SBCS

Implements the algorithm suggested by xnor.

{⍸1=∘⍺⍺ ̈⍣{1=+/⍺}⍳⍵}

Try it on APLgolf!

The blackbox function is called with dummy arguments it ignores, which I think should be fine as there is no way to pass a niladic function to an operator.

⍳⍵ create a range from 1 to n

̈ for each value in the current list ...
⍺⍺ call the blackbox function ...
1= and compare the result to 1 ...
⍣{1=+/⍺} until the result sums to 1

⍸ get all indices of 1's in the resulting boolean mask. This returns a singleton value

3 bytes can be saved by using a full program instead of a dop, but this is quite inconvenient to use:

⍸1=∘⎕ ̈⍣{1=+/⍺}⍳⎕

Try it on APLgolf!

Answer 14

Ruby, 60 bytes

f=->n,g,m,r=0,z=1{z>m ?r<m ?r:f[n,g,m]:f[n,g,m,r*n+g[],z*n]}

Try it online!

Use the log() approach, with a recursive function: z is the maximum possible random number for a given iteration, r is the current accumulated value.

Answer 15

C (gcc), ^{(削除) 76 (削除ここまで) \$\cdots\$ (削除) 70 (削除ここまで)} 67 bytes

i;c;g(n,m,f)int(*f)();{for(;n;)for(n=i=m;i--;)!f()?n-=m,c=i:0;n=c;}

Try it online!

Saved 3 bytes thanks to att!!!

Uses xnor's idea by repeatedly calling \$f()\$ \$m\$-times and if \$f()\$ returns \0ドル\$ once and only once, then returns the time (with \0ドル\$ being the last time and \$m-1\$ being the first) that \$f()\$ was \0ドル\$.

• att: 67 bytes
• Noodle9: @att Nice one - thanks! :D

Answer 16

JavaScript (Node.js), 60 bytes

(n,f,m)=>(g=p=>p*m/d^-~p*m/d?g(p*n+f(),d*=n):p*m/d)(0n,d=1n)

Try it online!

Signature: (n: BigInt, f: () => BigInt, m: BigInt) => BigInt

Input / Output BigInt values.

---

And it would be 47 bytes if we can assume infinite precision of floating point numbers:

n=>f=>g=(m,p=0)=>p*m^-~p*m?g(m/n,p*n+f()):p*m|0

Try it online!

• tsh: To my understanding: The second approach generate integers in range \$\left[0, m\right)\$ with propability \$\frac{1}{m}\pm2^{-53}\$ each.

Answer 17

JavaScript, (削除) 55 (削除ここまで) 53 bytes

Takes arguments by currying, i.e. f(r)(m), where r is the black-box randomisation function. The first 3 bytes could be removed by stipulating that the function be pre-assigned to r.

r=>g=(m,y=x=m)=>y?g(m,--y,r()||(--x,z=y)):m+~x?g(m):z

Try it online! (change the values of n & m in the header)

Answer 18

Vyxal, 29 bytes

{|n÷£$•⌈(\†1⁄8)3⁄4nhβ:nṪt>nh(1⁄4_)}

Try it Online!

This is a whole bunch of yucky stuff that is lowkey disturbing. I really need to make functions nicer to deal with in the rewrite.

A lambda submission, that takes a single argument, [n, m, f].

Explained

{|n÷£$•⌈(\†1⁄8)3⁄4nhβ:nṪt>nh(1⁄4_)}
{| # while the top of the lambda stack is truthy:
 n÷ # push all the contents of the input onto the stack
 £ # and place "f" into the register.
 $•⌈ # push ceil(log_n(m))
 (\†1⁄8) # and that many times, push the result of f() onto the global array
 3⁄4 # push the global array, containing ceil(log_n(m)) numbers
 nhβ # and convert from base n
 :nṪt> # push ^ > m
 nh(1⁄4_) # and clear the global array
 } # close the while loop (we need this because lambda submission)

• emanresu A: If you actually wrap it in a lambda you can save a byte since functions autocall, so the closing is unnecessary.

Answer 19

JavaScript (Node.js), 50 bytes

(r,n,m)=>g=(i=1,j=0)=>i<m?g(i*n,j*n+r()):j<m?j:g()

Try it online!

generate ceil(logn(m)) random numbers, convert these from base n to an integer, and reject-and-try-again if the result's greater than or equal to m.

JavaScript (Node.js), 49 bytes

r=>g=(m,y=x=m)=>y?g(m,--y,r()?z=y:--x):1-x?g(m):z

Try it online!

From Shaggy's

Answer 20

C (gcc), 59 bytes

r;c;g(n,m,f)int(*f)();{for(r=0,c=m;c--;r%=m)r=r*n+f();r=r;}

Try it online!

Answer 21

JavaScript, 36 bytes

(n,m,f)=>(g=p=>p&&g(p-1)*n+f())(m)%m

Try it online!

This answer works in all JS versions after 2015

Edit #1: -3 bytes thanks to Shaggy

• Shaggy: 36 bytes(?): (n,m,f)=>(g=p=>p&&g(p-1)*n+f())(m)%m