# Randomizing until 0

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
• 0 must be the final output, Optionally an empty line instead 0
• If the submission is a function, may it return 0 in addition to printing it?
Jul 9 '18 at 12:55
• @Adám yes, you can return in addition Jul 9 '18 at 12:59
• Do I need to seed my RNG? Jul 9 '18 at 16:16
• May we print without delimiters? Jul 30 '18 at 15:44
• I got curious. It's quite easy to prove that the average number of steps this program takes before it terminates is H(K-1) + 1 where H(K) is the K'th harmonic number. For n=1000, that's 8.484 steps on average. Sep 21 '18 at 14:02

# 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”!

• Most likely you need to print or write to buffer. Leaving a value in memory is unreasonable unless it is not possible to print or do any kind of I/O. See codegolf.meta.stackexchange.com/questions/2447/…
– qwr
Jul 26 '18 at 19:57

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

• I think you could save a couple of bytes by using Write() instead of WriteLine() and using string formatting to add a separator, e.g. Write($",{k=new Random().Next(k)}" since OP said output format doesn't matter Jul 10 '18 at 21:03 • @charliefox2: No, that would be 2 bytes longer. Jul 11 '18 at 8:41 • How can you use WriteLine and ReadLine without the Console Prefix? Jul 11 '18 at 11:14 • @raznagul not if you do it for WriteLine(k) as well. var k=int.Parse(ReadLine());for(Write(k);k>0;)Write($",{k=new Random().Next(k)}"); should save you 2 bytes Jul 11 '18 at 12:51
• @Snowfire: Try it Online automatically includes using static System.Console for C# Interactive Compiler. Jul 11 '18 at 13:36

# 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


# 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

• “Input must be printed at first”. Try with more Bash specific syntax. Jul 10 '18 at 20:08
• Welcome to PPCG! :) Jul 11 '18 at 9:39
• Grr! I always forget the {..} enclosed for block which can reduce it to 50 characters. Jul 11 '18 at 14:15
• Thanks for your welcome. I've discovered a few cool bash tricks which i didn't know before. :) Jul 11 '18 at 21:27
• If you reverse the logic, you not need if and exit: f()(echo $1;(($1))&&f $[RANDOM%$1]). Or with an error message even f()(echo $1&&f$[RANDOM%$1]). Jul 12 '18 at 14:16 # 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  # ><>, 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  • You could do something like this to get rid of that last line – Jo King Jul 17 '18 at 6:35 • Or reversing the whole thing (91 bytes) – Jo King Jul 17 '18 at 7:01 # Java, 56 bytes Object f(int n){return n<1?0:n+","+f(n*=Math.random());}  Try It Online ## Acknowledgments • (int)(Math.random()*n) can be golfed to n*=Math.random() Jul 19 '18 at 9:59 # Kotlin, 60 bytes fun f(k:Int){println(k);if(k>0)f((Math.random()*k).toInt())}  Try it online! Solution with recursion. • random is function from java.lang.Math, isn't it? java.lang.Math module is required explicit import or Math.random() code Jul 25 '18 at 7:39 # PHP, 43 42 bytes <?while($a=$a?rand(0,$a-1):$argn)echo$a?>0


To run it:

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


Example output:

10019128410


-1 byte thanks to Titus's suggestion.

• rand(0,$a) get a number between 0 and $a included. As $a should not be a possible value, the max argument for rand must be $a-1
– Med
Jul 11 '18 at 9:54
• Right you are @Med! Thanks for letting me know, I've updated my answer. Jul 11 '18 at 11:32
• Why don´t you just append 0 instad of two newlines? Jul 30 '18 at 15:42
• Thanks @Titus! That's very helpful, I've updated my solution (-1 byte). Jul 30 '18 at 16:00

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

# Factor, 21 bytes

[ [ random ] follow ]


Try it online!

Basically, collects the values after each iteration (including zeroth iteration) stopping when the value is f, where each iteration converts the value n to a random integer between 0 and n-1 inclusive. Calling random on zero yields f, conveniently terminating the loop.

Interestingly, the doc page for follow has an example code that solves almost the same task, but it is actually longer since it tries to exclude zero at the end.

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

# Jelly, 6 bytes

X’$¹Ð¿  Try it online! • XƬ;0 saves two since it'll stop when the randrange(1,x+1) returns x at which point we have our 0 :) EDIT: Oh, I just scrolled and saw Dennis's answer. Jul 9 '18 at 16:23 • @JonathanAllan Dennis's previous revision? Bah. Jul 9 '18 at 16:23 # JavaScript, 34 bytes Outputs a space-delimited string of integers. f=n=>n&&n+" "+f(Math.random()*n|0)  Try it online # Red, 41 bytes func[n][print n if 0 < n[f random n - 1]]  Try it online! ## 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. # 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 # 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)  • This does not quite meet the spec, as it does not print the first number. Consider modifying your code to something like this Jul 9 '18 at 18:48 • Also, you can save bytes by removing whitespace and submitting as a function instead of a full program – Jo King Jul 10 '18 at 6:38 • I see that you've been posting mostly Python answers. Have you had a look at Tips for golfing in Python? – Jo King Jul 10 '18 at 6:46 ## 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! • The rules say "Input must be printed at first". Jul 9 '18 at 18:43 • I do apologise... no idea how I missed that, having already looked at half a dozen answers. Jul 9 '18 at 18:47 # Ruby, 31 29 bytes ->n{n=rand p n until 1>n;p 0}  Try it online! # 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  # 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.) # AWK, 56 bytes {print($0);k=$0;for(srand();k>0;)print(k=int(k*rand()))}  Try it online! # 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. # 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! # 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  # Racket, 52 bytes (define(f n)(println n)(unless(= n 0)(f(random n))))  Try it online! # 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. # K4, 1312 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!

# Common Lisp - 52 Bytes

(loop while (/= a 0) do (print (setf a (random a))))


Assumes a is already defined.

Test case:

(setf a 5000000)
(loop while (/= a 0) do (print (setf a (random a))))