Output a random value from the last 16 values outputted

Question

Output the numbers 1-16 (or any other set of 16 distinct items). Then, repeatedly, output a random value chosen uniformly from the last 16 items outputted.

After the same item is printed 16 times in a row, halt.

If a number appears multiple times in the last 16 values, it should have proportionally more chance to be chosen as the next number. If a number did not appear in the last 16 elements, it can't be chosen ever again.

_{0 bonus points to whoever can provide the probability distribution of each number becoming the last one standing.}

Answer 1

Python, 102 88 86 85 84 bytes

from random import*;*t,=range(16)
while~-len({*(x:=t[-16:])}):t+=choice(x),
print(t)

Attempt This Online!

• -14 thanks to mousetail
• -1 thanks to loopy walt

Prints a list of numbers from 0 to 15.

Commented

from random import*;     # Import the random module for later
*t,=range(16)            # Set t equal to [0, 1, ..., 15]
                         # ([* ... ] unpacks it into a list)
while~-len(              # Loop while the number of unique items
      {*(x:=t[-16:])}):  # in the last 16 elements of t is not 1
                         # (setting x to the last 16 elements of t)
    t+=choice(x),        # Append a random element of x to t
print(t)                 # At the end, output t

Answer 2

Ruby, 55 51 48 bytes

puts x=[*1..16];_,*x=x<<p(x.sample)while(x|x)[1]

Try it online!

Answer 3

R, 66 61 bytes

x=Map(show,L<-1:16)
while(sd(L))L=c(L[-1],print(sample(L,1)))

Try it online!

Explanation outline:

1. Map the show function over 1:16 (and save the vector to variable L).
2. We assign the result of the Map to x to avoid outputting its value (ugly list of nulls).
3. Then we sample one element from L and append to L[-1] (L without the first element).
4. Loop until sd(L)==0 (this means that the last 16 numbers are all the same).

Answer 4

R, 52 bytes

a=b=16:1;while(sd(a[b]))a=c(sample(a[b],1),a);rev(a)

Try it online!

Full program that yields an R vector containing the sequence of values.
R displays this by default with index numbers (in square brackets) at the start of each line. If this is annoying, add 5 bytes more to wrap the output into a call to cat() like this.

Answer 5

Vyxal, 15 13 12 9 bytes

k6≬℅+Ḣ↔ƒ⋎

Try it Online! Outputs characters from the string "0123456789abcdef"

-3 thanks to emanresu

Explained (old)

k6≬℅+Ḣ↔ḣvt∑+
k6           # The string "0123456789abcdef"
  ≬   ↔      # apply the following and collect results while invariant:
   ℅+        #  append a random item of the string to the string
     Ḣ       #  remove the first character
       ḣvt   # separate the first item from that list and get the tail of each remaining item
          ∑+ # join that into a single string and append to the previously separated head

Answer 6

Brachylog, 18 bytes

15⟦ẉ₂ᵐ{=|ṛRẉ&b,R↰}

Try it online!

15⟦                  The list [0, …, 15]
   ẉ₂ᵐ               Map writeln
      {           }  If
       =               All elements of the list are equal, then stop
        |            Else
         ṛR            R is a random element of the list
          Rẉ           writeln R
            &b         Remove the first element of the list
              ,R       Append R to the list
                ↰      Recursive call on this list

Answer 7

JavaScript (ES7), 74 bytes

Same algorithm as the other version, but using the weirder set "5368709124,false".

f=(s=2**29+[4,k=!1])=>/(.)\1{15}/.test(s)?s:f(s+s[Math.random()*16+k++|0])

Try it online!

How?

\$2^{29}=536870912\$ contains all digits from \$0\$ to \$9\$ exactly once, except \$4\$. Adding [4,!1] forces a coercion to a string and appends "4", followed by a comma, followed by "false".

---

JavaScript (ES6), 83 bytes

Uses the hexadecimal characters 0-9 and A-F.

f=(s=(k=0)+'123456789ABCDEF')=>/(.)\1{15}/.test(s)?s:f(s+s[Math.random()*16+k++|0])

Try it online!

Commented

f = (                 // f is a recursive function taking:
  s = (k = 0) +       //   s = output string
    '123456789ABCDEF' //   k = counter
) =>                  //
/(.)\1{15}/.test(s)   // if s contains the same character repeated
?                     // 16 times in a row:
  s                   //   stop and return s
:                     // else:
  f(                  //   do a recursive call:
    s +               //     append to s
    s[                //     the character from s
      Math.random()   //     whose index is randomly chosen in
      * 16 + k++ | 0  //     [k .. k+15] (increment k afterwards)
    ]                 //     i.e. one of the last 16 characters
  )                   //   end of recursive call

Answer 8

C (gcc), 105 bytes

j,k;a[16];f(i){for(k=i=16;a[--i]=i;);for(;k;j-(a[i++%16]=a[rand()%16])?k=16:--k)printf("%d ",j=a[i%16]);}

Try it online!

Answer 9

Japt, 20 19 bytes

Far too long but seeing as Japt has no infinite loops and can't loop until invariant, it'll have to do for now.

Go
@òÎÌʨG}a@pUsX ö

Test it

Go\n@òÎÌʨG}a@pUsX ö
G                        :16
 o                       :Range [0,G)
  \n                     :Assign to variable U
    @                    :Left function
     ò                   :  Partition U between elements where
      Î                  :    Sign of difference is truthy (non-zero)
       Ì                 :  Last element
        Ê                :  Length
         ¨G              :  >=16
           }             :End function
            a            :Run right function until left function returns true and return final result
             @           :Right function, taking 0-based iteration index X as argument
              p          :  Push to U
               UsX       :    Slice U from index X
                   ö     :    Random element

Answer 10

05AB1E --no-lazy, 15 14 bytes

16L€=[DΩ=ª¦DË#

Try it online!

• -1 thanks to Kevin Cruijssen

Alternative 15 bytes solution (thanks to Kevin Cruijssen)

16L[D16.£©Ωª®Ë#

Try it Online!

Explanation

16L             # Push [1..16]
   €=           # Print each item
     [          # Start an infinite loop:
      DΩ        #  Duplicate and push a random element of the list
        =ª      #  Print and append to the list
          ¦     #  Remove the first item
           DË#  #  If all items are equal, break

Answer 11

Python, 77 bytes

from random import*
t=range(16)
while t:T,*s=*t,choice(t);t=s[t==s:];print(T)

Attempt This Online!

Prints one number per line.

How?

The two mildly clever bits are

1. the rolling tail end of the sequence is all equal if and only if it's equal to its next iteration
2. for the winding down it doesn't matter whether we truncate from the right (more logical) or the left (shorter) since all elements are equal

Answer 12

Nibbles, 10 bytes (20 nibbles)*

/`.,16>>:$=`#$16$:/

*Nibbles is a pure functional language and has no random number capability.
So, this program uses the hash-modulo-16 of the last 16 values after each pick to select the next index. This is pseudo-random, but obviously will be the same on each run of the program.
To more-closely mimic PRNGs from other programming languages, we can select a 'salt' value for the hash, to act as a 'seed': this needs to be appended to the program, and, additionally, the otherwise-implicit variables of the program then need to be explicitly specified, costing +3 nibbles (+1.5 bytes, so 11.5 bytes not including the 'seed' itself).

/`.,16>>:$=`#$16$:/
 `.                     # iterate while unique
   ,16                  # starting with 1..16:
        :$              #   join the last list to
          =     $       #   its element at index
           `#$          #   itself hashed
              16        #   modulo-16
/                       # now, fold over this list from the right:
                 :      #   joining 
                  /     #     the (implicit) first element of the (implicit) left argument
                        #     to the (implicit) right argument

Answer 13

J, 31 bytes

(,1}._1{"1(}.,?@#{])^:a:)@i.@16

Try it online!

0 bonus points to whoever can provide the probability distribution of each number becoming the last one standing.

┌──┬──────┐
│0 │1/136 │
├──┼──────┤
│1 │2/136 │
├──┼──────┤
│2 │3/136 │
├──┼──────┤
│3 │4/136 │
├──┼──────┤
│4 │5/136 │
├──┼──────┤
│5 │6/136 │
├──┼──────┤
│6 │7/136 │
├──┼──────┤
│7 │8/136 │
├──┼──────┤
│8 │9/136 │
├──┼──────┤
│9 │10/136│
├──┼──────┤
│10│11/136│
├──┼──────┤
│11│12/136│
├──┼──────┤
│12│13/136│
├──┼──────┤
│13│14/136│
├──┼──────┤
│14│15/136│
├──┼──────┤
│15│16/136│
└──┴──────┘

Proof: For example, the system of equations you'd solve for the n=3 case is:

$$ \begin{align} x_1 &= \frac{x_3}{3} \\ x_2 &= x_1 + \frac{x_3}{3} \\ x_3 &= x_2 + \frac{x_3}{3} \\ x_1 + x_2 + x_3 &= 1 \end{align} $$

where \$x_1\$ is the chance that number in positon 1 wins, etc -- where 1, if it is not picked the first round, vanishes forever.

The first equation represents that 1/3 of the time \$x_1\$ will be picked and move into position 3, and the rest of the time of vanish. Thus its "value" is 1/3 of \$x_3\$'s.

Similarly, \$x_2\$ will always move into slot 1, where it has \$x_1\$ chance of winning, and 1/3 of the time will also move into slot 3, giving it \$x_3\$ chance of winning. And so on...

Answer 14

Excel (ms365), 109 bytes

I do hope that this could get OP's approval. Since volatility would stand in the way of using a list of elements, the only way I could think about a repetitive function that would auto-stop when last 16 elements are exactly the same is to use a custom function made with the name-manager. In this case my function is called 'Z':

=LAMBDA(x,LET(y,RIGHT(x,16),IF(y=REPT(RIGHT(y),16),x,Z(x&MID(y,RANDBETWEEN(1,16),1)))))

Formula in A1:

=Z("ABCDEFGHIJKLMNOP")

This would make for a combined total of 87 + 22 = 109 bytes.

Answer 15

TI-Basic, 54 bytes

For(I,1,16
Disp I
End
cumSum(1 or rand(16
While max(Ans≠max(Ans
augment(ΔList(cumSum(Ans)),{Ans(randInt(1,16
Disp Ans(16
End

max(abs(ΔList(Ans can be used instead of max(Ans≠max(Ans alternatively.

Answer 16

Pyth, 16 15 bytes

pK<TGWt{=t+KpOK

Try it online!

Thanks @isaacg for -1 byte

Explanation

 K<TG              # K = "abcdefghijklmnop" (all but the last ten elements of the alphabet)
p                  # print(K)
     Wt{           # while deduplicated K has more than one element
            pOK    #   print a random element of K
          +K       #   append this to K
        =t         #   remove the first element of K

Answer 17

Retina, 43 bytes

16*.
Y`.`L
/(.)\1{15}$/^+-16,@v`(.).*
$&$1

Try it online! Uses ABCDEFGHIJKLMNOP. Explanation:

16*.

Insert 16 .s.

Y`.`L

Transliterate them to uppercase letters using a different letter each time.

/(.)\1{15}$/^+

Repeat until the last 16 letters are identical.

-16,@v`

Randomly choose between one of the last 16 overlapping matches.

(.).*

Match any character and the rest of the string.

$&$1

Append the initial character to the match, i.e. append it to the string.

Answer 18

Go, 177 bytes

import."math/rand"
func f(){N,M,l:=[]int{},1,16;for i:=1;i<17;i++{N=append(N,i);println(i)}
for M<16{k:=Intn(16)
x:=N[k]
println(x)
N=append(N[1:],x)
if x!=l{l=x;M=1}else{M++}}}

Attempt This Online!

Answer 19

Zsh, 73 bytes

set {a..p};<<<${(F)@};while 17=$@[RANDOM%16+1];shift;<<<$16;((${#@:#$1}))

Try it online!

I use single letters instead of up-to-two-digit numbers as the “16 distinct items”, which saves a byte. (It also gives extra flexibility, which I took advantage of in an earlier version of this answer with a more complex termination condition.)

Expanded and commented:

set {a..p}                    # set positional arguments 1=a, 2=b, ...
<<<${(F)@}                    # join arguments with newline, call implicit cat
while
  17=$@[RANDOM%16+1];         # append a random element
  shift;                      # remove the first element
  <<<$16;                     # print the last element
  ((${#@:#$1}))               # termination condition (see below)
                              # no loop body = empty loop body

For those unfamiliar with zsh: the positional arguments can be accessed through $1, $2, … like in other shells, and also through the variable @ which mostly behaves like an array. Zsh array indexes start at 1. RANDOM is a special variable that returns a random number each time it's accessed; fortunately the range 0..32767 is dividible by 16 so all values are equally likely modulo 16.

Now for the termination condition. It's the arithmetic expression ${#@:#$1}: the command is true if the integer expression has a nonzero value. The expression uses several parameter expansion features. From the outside in, first, we have ${#spec} to count the number of elements in the parameter expansion of spec. Inside, we have ${name:#pattern} which, when name is an array, removes the elements that match pattern. The name is @, i.e. the positional parameters. The pattern is $1. Thus we count the number of positional parameters that are not equal to the first one: this is 0 if and only if all the positional parameters are equal.

Answer 20

Julia, 73 70 69 bytes

^,~=last,rand
s=[1:16;]
while s∩s^16!=s^1
push!(s,~s^16)end
show(s)

Attempt This Online!

• -1 byte thanks to MarcMush: reassign operators on the same line
  • (Otherwise, a space is needed between ^ and =)
• -2 bytes thanks to MarcMush: replace !allequal(s^16) with s∩s^16!=s^1
  • (!allequal(last(s,16)) with s∩last(s,16)!=last(s,1))
• -1 byte thanks to MarcMush: remove the newline before end
• Thanks also to MarcMush for spotting an error or two!

Answer 21

Charcoal, 24 bytes

≔…α¹⁶θθＷ∧⁻θ⌊θ‽θ«ι≔⁺Φθλιθ

Try it online! Link is to verbose version of code. Uses ABCDEFGHIJKLMNOP. Explanation:

≔…α¹⁶θθ

Get and print the first 16 uppercase letters.

Ｗ∧⁻θ⌊θ‽θ«ι

While there is a choice of at least two different letters, pick and output a random letter from those remaining.

≔⁺Φθλιθ

Update the string of available letters.

23 bytes if the last letter does not need to be printed (it will be the same as the preceding 15):

≔…α¹⁶θＷ⁻θ⌊θ«→Ｐθ≔⁺Φθλ‽θθ

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

Answer 22

Pip, 21 bytes

P*Y,16T$=yY SyAE PRCy

Uses 0 to 15. Attempt This Online!

Explanation

P*Y,16T$=yY SyAE PRCy
   ,16                 ; Range(16)
  Y                    ; Yank, storing in y variable
P*                     ; Print each
      T                ; Loop till
       $=y             ; all elements of y are equal:
                  RCy  ;  Choose a random element of y
                 P     ;  Print it
              AE       ;  Append that element to
            Sy         ;  y without its first element
          Y            ;  Yank that list as the new value of y

Answer 23

Factor, 69 bytes

16 iota [ dup 16 tail* dup all-eq? ] [ random suffix ] until drop ...

Try it online!

Answer 24

Raku, 56 bytes

|(1..16),{@_.tail(16).pick}...{~@_~~/(\d+)[' '$0]**15$/}

Try it online!

This is a sequence of the form initial-elements, { generator } ... { termination-check }.

• The initial elements are from the range 1..16, flattened with |.
• The generator takes the entire sequence generated so far in @_, then randomly picks an element from the last sixteen of them.
• The termination check stringifies the sequence, then checks that the string satisfies a regex: a space-separate sequence of digits that repeats sixteen times before the end of the string.

Answer 25

CJam, 24 23 bytes

G,_:p;{_mR_p+(;__|,(}g;

Try it online!

Explanation

G,_:p;                        create and print an array [0-16)
      {             }g        do...
       _mR                      pick a random number from the last 16
          _p+(;                 print, add to the list, and remove the oldest number
               __|,(          ...while the number of unique numbers in the last 16 != 1
                      ;       cleanup

(-1 byte) replacing 1- with (, courtesy of my bestie

Answer 26

Arturo, 74 70 67 bytes

a:@0..15prints a until[prints->a\0[]=a--a\0][a:@[sample a]++chop a]

Try it

Answer 27

Swift 5.6+, 107 bytes

var a=[_](1...16),i=0
a.map{print($0)}
while Set(a).count>1{a[i]=a.randomElement()!
print(a[i])
i=(i+1)%16}

Uses a as a circular buffer, overwriting a different position each run through the loop. For lack of a builtin "all elements are the same" operation, the loop condition converts it to a Set to count the number of unique elements.

SwiftFiddle link

Ungolfed:

var arr = Array(1...16)

for el in arr {
  print(el)
}

var i = 0
while Set(arr).count > 1 {
    let x = arr.randomElement()!
    print(x)
    arr[i] = x
    i = (i + 1) % arr.count
}

Answer 28

PHP 8, 110 bytes

$o=range(1,16);do$o[]=$o[count($o)-rand(1,16)];while(count(array_unique(array_slice($o,-16)))>1);print_r($o);

I wish PHP's array syntax was a little less verbose...

Works by building up an array by appending a random element from the last 16 elements, then printing it all at once, when the last 16 elements are all the same.

Answer 29

Zsh, 101 bytes

seq 16|tee a;set `shuf a`
while shift;16=`shuf -n1 a`;<<<$16;s=(${(n)@});((s[1]<s[16]))&&<<<${(F)@}>a

Try it online!   _{114 bytes   117b}

Writes/reads from file a. Uses the shell $argv array to randomise and pick new values, and a sorted array $s to check equality.

_{Whoops, the initial version incorrectly ran forever. And then the second version was not uniformly random. Fixed now. Thanks to @Gillies for -13 bytes.}

Answer 30

Java 8, 135 bytes

()->{int a,m=16,i=0,c=1,t[]=new int[m];for(;c<m;c=a==t[(i+++15)%m]?c+1:1)System.out.println(t[i%m]=a=i<m?i:t[(int)(Math.random()*m)]);}

Try it online!

Even if Java always loses by far, it was still a fun challenge to code!