29
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ If the submission is a function, may it return 0 in addition to printing it? \$\endgroup\$ – Adám Jul 9 '18 at 12:55
  • 1
    \$\begingroup\$ @Adám yes, you can return in addition \$\endgroup\$ – Luis felipe De jesus Munoz Jul 9 '18 at 12:59
  • \$\begingroup\$ Do I need to seed my RNG? \$\endgroup\$ – SIGSTACKFAULT Jul 9 '18 at 16:16
  • \$\begingroup\$ May we print without delimiters? \$\endgroup\$ – Titus Jul 30 '18 at 15:44
  • \$\begingroup\$ 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. \$\endgroup\$ – J.Doe Sep 21 '18 at 14:02

69 Answers 69

2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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/… \$\endgroup\$ – qwr Jul 26 '18 at 19:57
2
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – charliefox2 Jul 10 '18 at 21:03
  • \$\begingroup\$ @charliefox2: No, that would be 2 bytes longer. \$\endgroup\$ – raznagul Jul 11 '18 at 8:41
  • \$\begingroup\$ How can you use WriteLine and ReadLine without the Console Prefix? \$\endgroup\$ – Snowfire Jul 11 '18 at 11:14
  • \$\begingroup\$ @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 \$\endgroup\$ – charliefox2 Jul 11 '18 at 12:51
  • 1
    \$\begingroup\$ @Snowfire: Try it Online automatically includes using static System.Console for C# Interactive Compiler. \$\endgroup\$ – raznagul Jul 11 '18 at 13:36
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ “Input must be printed at first”. Try with more Bash specific syntax. \$\endgroup\$ – manatwork Jul 10 '18 at 20:08
  • \$\begingroup\$ Welcome to PPCG! :) \$\endgroup\$ – Shaggy Jul 11 '18 at 9:39
  • \$\begingroup\$ Grr! I always forget the {..} enclosed for block which can reduce it to 50 characters. \$\endgroup\$ – manatwork Jul 11 '18 at 14:15
  • \$\begingroup\$ Thanks for your welcome. I've discovered a few cool bash tricks which i didn't know before. :) \$\endgroup\$ – Bazil Jul 11 '18 at 21:27
  • \$\begingroup\$ 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]). \$\endgroup\$ – manatwork Jul 12 '18 at 14:16
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

><>, 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
\$\endgroup\$
  • \$\begingroup\$ You could do something like this to get rid of that last line \$\endgroup\$ – Jo King Jul 17 '18 at 6:35
  • 1
    \$\begingroup\$ Or reversing the whole thing (91 bytes) \$\endgroup\$ – Jo King Jul 17 '18 at 7:01
2
\$\begingroup\$

Java, 56 bytes

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

Try It Online

Acknowledgments

\$\endgroup\$
  • 2
    \$\begingroup\$ (int)(Math.random()*n) can be golfed to n*=Math.random() \$\endgroup\$ – Kevin Cruijssen Jul 19 '18 at 9:59
2
\$\begingroup\$

Kotlin, 60 bytes

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

Try it online!

Solution with recursion.

\$\endgroup\$
  • 1
    \$\begingroup\$ random is function from java.lang.Math, isn't it? java.lang.Math module is required explicit import or Math.random() code \$\endgroup\$ – mazzy Jul 25 '18 at 7:39
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Med Jul 11 '18 at 9:54
  • \$\begingroup\$ Right you are @Med! Thanks for letting me know, I've updated my answer. \$\endgroup\$ – Davіd Jul 11 '18 at 11:32
  • 1
    \$\begingroup\$ Why don´t you just append 0 instad of two newlines? \$\endgroup\$ – Titus Jul 30 '18 at 15:42
  • \$\begingroup\$ Thanks @Titus! That's very helpful, I've updated my solution (-1 byte). \$\endgroup\$ – Davіd Jul 30 '18 at 16:00
2
\$\begingroup\$

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.

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

Charcoal, 11 bytes

IθW⊟θI⊞Oθ‽ι

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

Iθ

Cast the input to string and print it.

W⊟θ

While the input is non-zero...

⊞Oθ‽ι

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

θNθWθ«≔‽θθ⸿Iθ

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

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

Jelly, 6 bytes

X’$¹Ð¿

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Jonathan Allan Jul 9 '18 at 16:23
  • \$\begingroup\$ @JonathanAllan Dennis's previous revision? Bah. \$\endgroup\$ – Erik the Outgolfer Jul 9 '18 at 16:23
1
\$\begingroup\$

JavaScript, 34 bytes

Outputs a space-delimited string of integers.

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

Try it online

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

Red, 41 bytes

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

Try it online!

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

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.

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

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

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

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)
\$\endgroup\$
  • \$\begingroup\$ This does not quite meet the spec, as it does not print the first number. Consider modifying your code to something like this \$\endgroup\$ – Taylor Scott Jul 9 '18 at 18:48
  • \$\begingroup\$ Also, you can save bytes by removing whitespace and submitting as a function instead of a full program \$\endgroup\$ – Jo King Jul 10 '18 at 6:38
  • \$\begingroup\$ I see that you've been posting mostly Python answers. Have you had a look at Tips for golfing in Python? \$\endgroup\$ – Jo King Jul 10 '18 at 6:46
1
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ The rules say "Input must be printed at first". \$\endgroup\$ – Ciaran_McCarthy Jul 9 '18 at 18:43
  • 1
    \$\begingroup\$ I do apologise... no idea how I missed that, having already looked at half a dozen answers. \$\endgroup\$ – VisualMelon Jul 9 '18 at 18:47
1
\$\begingroup\$

Ruby, 31 29 bytes

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

Try it online!

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

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
\$\endgroup\$
1
\$\begingroup\$

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

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

AWK, 56 bytes

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

Try it online!

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

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.

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

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!

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

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
\$\endgroup\$
1
\$\begingroup\$

Racket, 52 bytes

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

Try it online!

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

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.

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

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!

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

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))))
\$\endgroup\$
1
\$\begingroup\$

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.

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

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.