41
\$\begingroup\$

Given an input string S, print S followed by a non-empty separator in the following way:

  • Step 1: S has a 1/2 chance of being printed, and a 1/2 chance for the program to terminate.

  • Step 2: S has a 2/3 chance of being printed, and a 1/3 chance for the program to terminate.

  • Step 3: S has a 3/4 chance of being printed, and a 1/4 chance for the program to terminate.

  • Step n: S has a n/(n+1) chance of being printed, and a 1/(n+1) chance for the program to terminate.

Notes

  • The input string will only consist of characters that are acceptable in your language's string type.

  • Any non-empty separator can be used, as long as it is always the same. It is expected that the separator is printed after the last print of S before the program terminates.

  • The program has a 1/2 chance of terminating before printing anything.

  • A trailing new line is acceptable.

  • Your answer must make a genuine attempt at respecting the probabilities described. Obviously, when n is big this will be less and less true. A proper explanation of how probabilities are computed in your answer (and why they respect the specs, disregarding pseudo-randomness and big numbers problems) is sufficient.

Scoring

This is , so the shortest answer in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Can the separator be an empty string? \$\endgroup\$ – rturnbull Jun 12 '17 at 7:13
  • 16
    \$\begingroup\$ @rturnbull Well no, because in that case there is no separator. \$\endgroup\$ – Fatalize Jun 12 '17 at 7:18
  • \$\begingroup\$ Do we have to print these one after the other, or can we just print all of them when the program terminates? \$\endgroup\$ – Dennis Jun 12 '17 at 18:21
  • \$\begingroup\$ @Dennis One after the other. \$\endgroup\$ – Fatalize Jun 13 '17 at 6:42

40 Answers 40

1
\$\begingroup\$

Dart - 73 chars

import"dart:math";p(s,{i=2}){while(new Random().nextInt(i++)>0)print(s);}

This function implements the algorithm by taking a string as input and printing it as necessary. The separator is obviously newline. To run it, you need a main method like main(){p("foo");}.

It's hard to be small when you need to import the math library and instantiate the Random class.

Try it online

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

APL (Dyalog), 17 bytes

Requires ⎕IO←0 which is default on many systems.

{⎕←⍺⋄×?⍵:⍺∇1+⍵}∘2

This is a monadic function derived from a dyadic function by currying the right argument.

{ anonymous function

⎕←⍺ print ⍺ (the string)

 ⋄  then

×?⍵: if the signum of a random int in the range [0,-1] is 1, then:

⍺ ∇ 1+⍵ recurse with 1+ as new right argument

 (implicit, else: stop)

}∘2 with 2 as bound right argument

Try it online! Sets ⎕RL←0 (Random Link) to avoid TIO's regeneration of the same random number.)

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

C# 79 bytes

does a divide by 0 error count as terminating?

using System;s=>{for(int i=1;2>1/new Random().Next(++i);Console.Write(s+' '));}
\$\endgroup\$
1
\$\begingroup\$

Scala 76 72 Bytes

def w[T](s:T)={var x=2;while(Random.nextFloat>1f/x){x=x+1;print(s+" ")}

This uses a template because it works fine for strings, and saves a character. Other than that, it's a pretty basic implementation. Scala picks up a couple bytes by not having a proper++ operator. Random.nextFloat returns a random value between 0 and 1, and 1f/x forces float division. This implementation uses a space as a separator, with no trailing newline.

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

Lua, 50 46 bytes

i=2while 1<math.random(i)do i=i+1print(...)end

Assumes that it is already seeded

Try it online!

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

k, 20 bytes

`0:((*1?2+)(1+)/0)#,

Explanation:

`0:((*1?2+)(1+)/0)#,
                0    /set x to 0
           (1+)      /add 1 to x...
    (*1?2+)    /     /...while randint [0,2+x) is > 0
   (             )#, /make array with that many copies of the string
`0:                  /output array line by line

Probabilities:

 5#{(((#:'=x{(*1?2+)(1+)/0}\0)@!x))%x}2000000      /experimental
0.5001625 0.1667005 0.083024   0.050034 0.0333645
 {(1%x)*-1_1.,*\{(x-1)%x}x}2+!5                    /calculated
0.5       0.1666667 0.08333333 0.05     0.03333333
\$\endgroup\$
  • \$\begingroup\$ @ValueInk Oh, I believe I misread! Fixing this now... \$\endgroup\$ – zgrep Jun 15 '17 at 22:44
  • \$\begingroup\$ @ValueInk Fixed. \$\endgroup\$ – zgrep Jun 15 '17 at 23:12
1
\$\begingroup\$

Forth (gforth), 71 bytes

include random.fs
: f 1 1 do i 1+ random i = ?leave 2dup type cr loop ;

Try it online!

Technically will end after the [maximum single-cell number]th iteration, but the chance of that happening is at least 2-64 on most systems (and likely 2-32 on others)

Code Explanation

include random.fs  \ load the random library to generate random numbers

: f                \ start a new word definition
  1 1 do           \ loop from 1 to 0 (start at 1 stop when we reach 0 via integer overflow)
    i 1+ random    \ get a random integer from 0 to n
    i =            \ check if the value equals n
    ?leave         \ end the loop if true
    2dup type cr   \ otherwise, print the input string followed by newline
  loop             \ go back to beginning of loop
;                  \ end the word definition
\$\endgroup\$
0
\$\begingroup\$

Bash, 71 59 bytes

i=1;while((0<`shuf -i0-$i -n1`));do echo $1;i=$((i++));done

Try it online!

While is a better tool for this job

\$\endgroup\$
0
\$\begingroup\$

TI-BASIC, 24 22 bytes

-2 thanks to @lirtosiast

:Prompt Str1           //4 bytes
:While randInt(0,Ans+1 //9 bytes
:Disp Str1             //4 bytes
:Ans+1                 //4 bytes
:End                   //1 byte

Since all non-zero values are truthy, taking a random integer in between 0 and n-1 will give a random boolean with the correct probability.

\$\endgroup\$
  • \$\begingroup\$ Why not Ans instead of A? \$\endgroup\$ – lirtosiast Jul 11 '17 at 1:30
  • \$\begingroup\$ @lirtosiast Either works, but they have the same byte count and there is no reason to use Ans over A. A takes up less screen space, so I chose it. \$\endgroup\$ – Scott Milner Jul 15 '17 at 16:41
  • \$\begingroup\$ I was thinking you could avoid the →A, since you don't use Ans for anything else, and both Ans and A default to 0. \$\endgroup\$ – lirtosiast Jul 15 '17 at 22:40
  • \$\begingroup\$ @lirtosiast Ah, OK, thanks. \$\endgroup\$ – Scott Milner Jul 16 '17 at 0:36
0
\$\begingroup\$

Runic Enchantments, 20 bytes

i0q11+:'RA0=?;S:$S4?

Try it online!

Note that input is implicitly split on whitespace characters, so they need to be escaped.

Explanation

>                        Implicit entry
 i0q1                    Read input and set up stack
     1+                  Increment counter (value needs to be 2 for first loop)
       :'RA0=            Generate random value (non destructive to stack) and compare with 0
             ?;          If *not* 0, terminate
               S:$S      Otherwise duplicate and print string
                   4?    Skip next 4 instructions (implicit loop)

Newline variant, as printing a whitespace character as a separator costs an extra byte.

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