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
• Your program must finish.
• 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? – Adám Jul 9 '18 at 12:55
• @Adám yes, you can return in addition – Luis felipe De jesus Munoz Jul 9 '18 at 12:59
• Do I need to seed my RNG? – SIGSTACKFAULT Jul 9 '18 at 16:16
• May we print without delimiters? – Titus 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. – J.Doe 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 – charliefox2 Jul 10 '18 at 21:03 • @charliefox2: No, that would be 2 bytes longer. – raznagul Jul 11 '18 at 8:41 • How can you use WriteLine and ReadLine without the Console Prefix? – Snowfire 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 – charliefox2 Jul 11 '18 at 12:51
• @Snowfire: Try it Online automatically includes using static System.Console for C# Interactive Compiler. – raznagul 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. – manatwork Jul 10 '18 at 20:08
• Welcome to PPCG! :) – Shaggy Jul 11 '18 at 9:39
• Grr! I always forget the {..} enclosed for block which can reduce it to 50 characters. – manatwork Jul 11 '18 at 14:15
• Thanks for your welcome. I've discovered a few cool bash tricks which i didn't know before. :) – Bazil 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]). – manatwork 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() – Kevin Cruijssen 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 – mazzy 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. – Davіd Jul 11 '18 at 11:32
• Why don´t you just append 0 instad of two newlines? – Titus Jul 30 '18 at 15:42
• Thanks @Titus! That's very helpful, I've updated my solution (-1 byte). – Davіd 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.

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.

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

Elixir, 157 148 bytes

-9 bytes from Okx

defmodule N do def f(0,k)do IO.puts 0 end;def f(n,k)do IO.puts n;f Enum.random(0..k),k end end;k=String.to_integer IO.gets"";N.f Enum.random(0..k),k

Try it online!

Formatted:

defmodule N do
def f(0,k) do
IO.puts n
end

def f(n,k) do
IO.puts n
f Enum.random(0..k), k
end
end
{k,_} = Integer.parse IO.gets""
N.f Enum.random(0..k),k

We define a module with 2 functions - one is recursive, the other is the base case with a guard so it only executes when our random is 0 (Elixir doesn't necessarily assign anything, it does pattern matching for e.g. arguments- and thus f(0,k) only matches when n=0, otherwise f(n,k) matches). After defining that module (since functions can't be defined outside a module), we parse an integer from input and start our recursive looping.

Notably, k=String.to_integer IO.gets"" is the same length as the other method I've found to parse integers from input, {k,_}=Integer.parse IO.gets"", which is kinda neat.

• def f(n,k) when n <= 0 can be shortened to def f(0,k) – Okx Jul 29 '18 at 11:34