19
\$\begingroup\$

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 , shortest wins!

\$\endgroup\$
2
  • 10
    \$\begingroup\$ A method to steal: Make a list of m outputs from f, if it has a single 0 output its position, otherwise retry. \$\endgroup\$
    – xnor
    Aug 28 at 6:33
  • 1
    \$\begingroup\$ @tsh 𝑓 is guranteed to produce uniformly random integers. \$\endgroup\$
    – emanresu A
    Aug 29 at 1:12

18 Answers 18

7
\$\begingroup\$

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

ṛ⁴V$ÐṀḊ¿

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:
 ṛ⁴V      |   - The supplied function is run for each list member

Previous answer: Jelly, 16 bytes

³lĊ⁵V¤€ḅʋ⁴¤<³¬$¿

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

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

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

\$\endgroup\$
5
\$\begingroup\$

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, 37 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!

\$\endgroup\$
4
\$\begingroup\$

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`%₁∞

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 "").
However, obviously, without actually having this function it's tricky to test the code, so the TIO link substitutes the last few bytes m`%₁∞ 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
          `%₁        # call black-box function ₁, 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`%₁∞ 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`%₁∞ 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...

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ For R<4.1 62 bytes (this approach matches 55 bytes in R>=4.1) \$\endgroup\$
    – pajonk
    Aug 29 at 6:18
  • \$\begingroup\$ @pajonk - Thanks! \$\endgroup\$ Aug 29 at 6:48
  • \$\begingroup\$ crossed out H is still H \$\endgroup\$ Aug 31 at 19:35
4
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ The 4-byte version seems distinctly non-uniform... \$\endgroup\$ Aug 28 at 18:22
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Shaggy
    Aug 28 at 18:50
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ For some reason it always seems to output 3 (sorry I don't know Haskell if I am wrong please correct me) \$\endgroup\$
    – wasif
    Aug 28 at 8:03
  • \$\begingroup\$ @wasif That's because 3 is the correct answer for the test data provided on TIO. \$\endgroup\$
    – Wheat Wizard
    Aug 28 at 8:04
3
\$\begingroup\$

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

\$\endgroup\$
6
  • 1
    \$\begingroup\$ I think it's necessary to check that the list has exactly one zero, because otherwise taking the leftmost one biases towards smaller outputs. \$\endgroup\$
    – xnor
    Aug 28 at 7:44
  • \$\begingroup\$ @xnor oh sorry edited now \$\endgroup\$
    – wasif
    Aug 28 at 7:46
  • \$\begingroup\$ @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? \$\endgroup\$
    – wasif
    Aug 28 at 8:05
  • \$\begingroup\$ 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/… \$\endgroup\$
    – ovs
    Aug 28 at 8:10
  • \$\begingroup\$ Thank you @ovs !! \$\endgroup\$
    – wasif
    Aug 28 at 9:12
3
\$\begingroup\$

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!

\$\endgroup\$
1
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Nice answer! By the way, you don't need to take n if you're not using it. \$\endgroup\$
    – emanresu A
    Aug 29 at 10:54
  • \$\begingroup\$ Thanks @emanresu that saves 2 bytes \$\endgroup\$
    – James
    Aug 29 at 11:03
  • \$\begingroup\$ "The ranges may be 1...n instead of 0...n-1" so I think you can just return p to save another 2 bytes...? \$\endgroup\$ Aug 29 at 11:34
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 16 bytes

NθW⊖№υ⁰≔EθNυI⌕υ⁰

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⊖№υ⁰

Repeat until the predefined empty list contains exactly one zero.

≔EθNυ

Input m random integers to the predefined empty list.

I⌕υ⁰

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ 67 bytes \$\endgroup\$
    – att
    Aug 28 at 18:33
  • \$\begingroup\$ @att Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Aug 28 at 21:30
2
\$\begingroup\$

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!

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

Vyxal, 29 bytes

{|n÷£$•⌈(¥†⅛)¾nhβ:nṪt>nh(¼_)}

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÷£$•⌈(¥†⅛)¾nhβ:nṪt>nh(¼_)}
{|                             # 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))
        (¥†⅛)                  #   and that many times, push the result of f() onto the global array
             ¾                 #   push the global array, containing ceil(log_n(m)) numbers
              nhβ              #   and convert from base n
                 :nṪt>         #   push ^ > m
                      nh(¼_)   #   and clear the global array
                            }  # close the while loop (we need this because lambda submission)
\$\endgroup\$
1
  • \$\begingroup\$ If you actually wrap it in a lambda you can save a byte since functions autocall, so the closing is unnecessary. \$\endgroup\$
    – emanresu A
    Aug 28 at 7:17
1
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.