Randomizing until 0

Question

Challenge

Sandbox post

Given a positive integer (K) Output a uniformly-random integer (Y) between [0, K).

If Y > 0 Assume K = Y and repeat the process until Y = 0.

Rules

• Input must be printed at first
• Output format as you wish
• Your program must finish.
• 0 must be the final output, Optionally an empty line instead 0

Answer 1

Lua, 58 bytes

p,r=print,...+0 p(r)while r>0 do r=math.random(0,r)p(r)end

Try it online!

For some more Lua love here :)

Answer 2

Atari 400/800 6502 Assembler – 16 bytes

K set initially to #$FF (but can set to any byte value), then calls the POKEY PRNG at $D20A, if greater than or equal, try again, else save as the new upper limit. Keep going until it reaches zero.

define K $FF
* = $600
    LDA #K
.1: STA $80
    BEQ .3
.2: LDA $D20A
    CMP $80
    BCC .1
    BCS .2
.3: BRK       ; if you assume memory is cleared, can omit for 15 bytes

Which, when assembled, is:

a9 ff 85 80 f0 09 ad 0a d2 c5 80 90 f5 b0 f7 00

Output is by running a monitor, single stepping, and spying on $80! The rules indicated “output format as you wish”!

Answer 3

C# (Visual C# Interactive Compiler), 84 82 bytes

var k=int.Parse(ReadLine());for(Write(k);k>0;)Write($",{k=new Random().Next(k)}");

Try it online!

-2 Bytes thanks to charliefox2

Explenation:

var k = int.Parse(ReadLine());   //1. Read a line from STDIN and convert it to int
for(Write(k);                    //2. Write the original value of k to STDOUT
        k>0;)                    //3. Loop while k > 0
    Write($",{                   //6. Write the separator and the new value to STDOUT
        k =                      //5. Assign it to k
        new Random().Next(k)}"); //4. Get a random int between 0 (inclusive) and k (exclusive)

Answer 4

C# (.NET Core), 71 bytes

Using recursion.

static int f(int k){Console.WriteLine(k);return k==0?k:f(r.Next(0,k));}

Try it online!

Output:

100
9
3
0

Answer 5

Bash, 65 58 56 50 bytes

f()(echo ${a=$1};for((;a;)){ echo $[a=RANDOM%a];})

Try it online!

(Improved thanks to manatwork)

Recursive approach

50 28

f()(echo $1&&f $[RANDOM%$1])

Try

Answer 6

CJam, 7 9 bytes

ri{_pmr}h

Try it online!

Annotated

r       e# read input token
i       e# convert to int
{       e# do {
    _   e# duplicate topOfStack
    p   e# pop topOfStack and print it
    mr  e# rand(0, topOfStack)
}h      e# } while(topOfStack != 0)
        e# implicitly convert stack to string and print it

Answer 7

><>, 147 + 2 bytes

 :0=?\:0&:0=?\:2%-2,&1+&80.
   ;n/       \r:r&:0=?\1-&2*\
          /oan:{/?(}:~/44+\ v
<         \:0=?;>{~00.\*1.^0x
                          \1/

Try it online!

The idea is the same as @Sasha's—generate random bits, making sure not to exceed the original number—but just in a different layout. My solution uses the register to record the number of bits of n.

There is unfortunately a certain amount of wasted space, particularly on the last line.

How it works:

 :0=?\:0&                      n = 0?   No: duplicate n; let reg = 0
   ;n/                                  Yes: print then end

         :0=?\:2%-2,&1+&80.    n = 0?   No: n = floor(n / 2); increment reg; loop to (8,0)
             \                          Yes: enter loop to construct random number r

              r:r&:0=?\1-&2*\  reg = 0? No: r = 2 * r + (0 or 1); loop to (16, 1)
                      /44+\ v           Yes: check if r <= n
<                     \*1.^0x           
                          \1/

          /oan:{/?(}:~         r > n?   No: print r and newline; 
          \:0=?;>

                 {~00.         Go back to (0,0), using either r or n

Answer 8

Java, 56 bytes

Object f(int n){return n<1?0:n+","+f(n*=Math.random());}

Try It Online

Acknowledgments

• -6 bytes thanks to Kevin Cruijssen

Answer 9

Kotlin, 60 bytes

fun f(k:Int){println(k);if(k>0)f((Math.random()*k).toInt())}

Try it online!

Solution with recursion.

Answer 10

PHP, 43 42 bytes

<?while($a=$a?rand(0,$a-1):$argn)echo$a?>0

To run it:

echo '<input>' | php -nF <filename>

Or Try it online!

Example output:

10019128410

-1 byte thanks to Titus's suggestion.

Answer 11

J, 8 bytes

?^:*^:a:

Try it online!

How it works

f^:g^:_ is a J idiom for "do while", which means to repeatedly apply f to the input while g gives true. g should always give 0 or 1. Change the last _ (infinity) to a: (boxed empty), and the resulting verb gives the list of intermediate values.

Monadic ? is "roll", i.e. given N, generates a random integer between 0 and N-1 inclusive. Monadic * is "signum", i.e. gives 1 for positive, 0 for zero, -1 for negative input.

Answer 12

Vyxal M, 4 bytes

{℅…|

Try it Online!

the M flag generates a range 0-n implicitly

{         # while true
 ℅        # random in range 0-n
  …|      # print w/o popping

Answer 13

Charcoal, 11 bytes

ＩθＷ⊟θＩ⊞Ｏθ‽ι

Try it online! Link is to verbose version of code. Slightly unusual input format. Explanation:

Ｉθ

Cast the input to string and print it.

Ｗ⊟θ

While the input is non-zero...

⊞Ｏθ‽ι

... replace it with a random number in the implicit range...

Ｉ

... and cast the result to string and print it.

13-byte version with more standard input format:

θＮθＷθ«≔‽θθ⸿Ｉθ

Try it online! Link is to verbose version of code.

Answer 14

Jelly, 6 bytes

X’$¹Ð¿

Try it online!

Answer 15

JavaScript, 34 bytes

Outputs a space-delimited string of integers.

f=n=>n&&n+" "+f(Math.random()*n|0)

Try it online

Answer 16

Red, 41 bytes

func[n][print n if 0 < n[f random n - 1]]

Try it online!

Answer 17

Batch, 54 bytes

@echo %1&if %1 gtr 0 set/an=%random%%%%1&call %0 %%n%%

Four %s in a row... just a typical day for Batch. Only works up to 32768 (and not terribly uniform at that) due to limitations of Batch's random number generator. See my Batch answer to Pick a random number between 0 and n using a constant source of randomness for large uniform randomness.

Answer 18

Japt, 10 bytes

Outputs an array of integers.

_Ì}f@NpU=ö

Try it

---

Explanation

               :Implicit input of integer U
  }f           :Loop until left function returns falsey and return final value of right function
    @          :Right function
         ö     :  Random integer in the range [0,U)
       U=      :  Reassign to U
      p        :  Push
     N         :   To the array of inputs
_              :Left function
 Ì             :Get the last element of N. If it's 0, which is falsey, then the loop will be broken

---

Alternative, 8 bytes

A direct port of my JavaScript solution.

©U+S+ßUö

Try it

Answer 19

Python 2.7, 112 bytes

from random import randint
k=int(raw_input())
def r(k):
    y=randint(0, k-1)
    print y
    if y!=0:
        r(y)
r(k)

Answer 20

F#, 70 bytes

let r=System.Random()
let rec x K=printfn"%i"K;if K>0 then r.Next K|>x

Try it online!

Answer 21

Ruby, 31 29 bytes

->n{n=rand p n until 1>n;p 0}

Try it online!

Answer 22

Excel VBA, 42 bytes

An anonymous function that takes input from range [A1] and outputs to the console.

k=[A1]:?k:While k:y=Int(k*Rnd):?y:k=y:Wend

Answer 23

Julia 0.6, 33 bytes

~n=(println(n);n>0&&~rand(0:n-1))

Try it online!

Defines the function as an operator ~ (to save bytes). Print the given number, and if we haven't reached 0, call itself recursively with a new uniformly random number from range 0:n-1.

(Could've used @show instead of println since OP says "output format as you wish" (@show prints the variable name before the value every time, eg. n = 8 instead of 8), but the 2 byte saving doesn't seem worth it relative to total bytecount, and I like this neater output.)

Answer 24

AWK, 56 bytes

{print($0);k=$0;for(srand();k>0;)print(k=int(k*rand()))}

Try it online!

Answer 25

Pascal (FPC), 89 bytes

var K:word;begin Randomize;read(K);repeat writeln(K);K:=Random(K)until K<1;writeln(K)end.

Try it online!

Not only Pascal code is as long as usual, you also need to Randomize; beforehand...

Instead of writing of the initial value before the loop, 0 is written after the loop. This approach saves a byte because 1end. isn't valid; instead od separating this into 2 tokens, it tries to find a meaningful scientific notation.

Answer 26

Ruby, 23 bytes

f=->k{k<1||f[rand p k]}

Try it online!

Non-recursive, 25 bytes

->k{k=rand p k while k>0}

Try it online!

->k{(k=rand p k)>0&&redo}

Try it online!

Answer 27

MATLAB, 36 bytes

K
Y=1;while Y>0,Y=randi(K)-1;K=Y,end

Sample output: For K = 25

K =

    25


K =

    15


K =

    11


K =

     6


K =

     4


K =

     1


K =

     0

Answer 28

Racket, 52 bytes

(define(f n)(println n)(unless(= n 0)(f(random n))))

Try it online!

Answer 29

Julia 0.6, 49 bytes

~x=(println(x);x-1)
!x=(y=rand(0:~x))>0 ? !y : ~0

Try it online!

If one were willing to accept outputting all output except the last to STDOUT, and the last 0 as returning false, then it can be

~x=(println(x);x-1)
!x=(y=rand(0:~x))>0&&!y

Which is a bit short. But I think mixing outputs like that is not really in spirit.

Answer 30

K4, 13 12 11 bytes

Solution:

(*1?)\[0<;]

Examples:

q)k)(*1?)\[0<;] 100
100 77 30 17 12 2 0
q)k)(*1?)\[0<;] 100
100 37 28 20 2 0
q)k)(*1?)\[0<;] 100
100 77 61 55 53 6 2 0
q)k)(*1?)\[0<;] 100
100 12 1 0

Explanation:

Iterate over expression while x is greater than zero.

(*1?)\[0<;] / the solution
(   )\[0<;] / iterate over brackets whilst 0< evaluates true
  1?        / 1 choose (returns a 1-item list)
 *          / take the first

Bonus:

A 14 byte solution that also works in K (oK); this one is an if/else version of the same theme:

{$[x;*1?x;x]}\

Try it online!