Implement a bag without replacement

Question

Intro

The Tetris Guidelines specify what RNG is needed for the piece selection to be called a Tetris game, called the Random Generator. Yes, that's the actual name ("Random Generator"). In essence, it acts like a bag without replacement: You can draw pieces out of the bag, but you cannot draw the same piece from the bag until the bag is refilled.

Write a full program, function, or data structure that simulates such a bag without replacement.

Specification

Your program/function/data structure must be able to do the following:

• Represent a bag containing 7 distinct integers.
• Draw 1 piece from the bag, removing it from the pool of possible pieces. Output the drawn piece.
• Each piece drawn is picked uniformly and randomly from the pool of existing pieces.
• When the bag is empty, refill the bag.

Other Rules

• This is code-golf, so lowest byte count wins!
• Standard loopholes are forbidden.
• You can use any reasonable I/O method.

"Bonuses"

These bonuses aren't worth anything, but imaginary internet cookies if you are able to do them in your solution.

• Your bag can hold an arbitrary n distinct items.
• Your bag can hold any type of piece (a generic bag).
• Your bag can draw an arbitrary n number of pieces at once, refilling as needed.

• bigyihsuan: Related, but closed 2 years ago
• bigyihsuan: Sandbox

Answer 1

Vyxal, 5 bytes

Inspired by Kevin Cruijssen's 05AB1E answer
6 bytes without the bonus:

{7Þc/o⟑,

Try it Online!

Explanation

{7Þc/o⟑,
{ Loop forever
 7Þc/o Random permutaton of range(7)
 ⟑, Lazily evaluated lambda, print each item

Bonuses:

• 5 bytes for Arbitrary n items: {Þc/o⟑,. Implicitly takes an integer as the input.
• 5 bytes for Generic bag: {Þc/o⟑,. Implicitly takes a list as the input. Same program as above :P
• 8 bytes for Draw n items: {7Þc/o?Ẏ⟑,. Slices the list until the input before applying it to the lambda.

Answer 2

JavaScript (ES6), 50 bytes

A function that draws one piece at a time.

m=f=_=>m^(m|=1<<(i=Math.random()*7))?-~i:f(m%=127)

Try it online!

Commented

m = // m (aka "the bag") is a global bitmask holding
 // drawn pieces, initialized to a zero'ish value
f = _ => // f is a recursive function ignoring its argument
m ^ ( // if m is modified when ...
 m |= 1 << ( // ... the floor(i)-th bit of m is set
 i = // where i is uniformly chosen
 Math.random() // in [0, 7[
 * 7 //
 ) //
) ? // then:
 -~i // return floor(i + 1)
: // else:
 f( // try again
 m %= 127 // and reset m to 0 if it's 127 (0b1111111),
 ) // meaning that the bag is empty

Answer 3

R, (削除) 50 (削除ここまで) 40 bytes

-10 bytes thanks to inspiration from Giuseppe

{b=n=1;\()(b<<-c(b,sample(7)))[n<<-n+1]}

Attempt This Online!

A reuseable function that on each call returns a single random nunber in the range 1..7, sampled across calls using the 'tetris' distribution.
This is how I interpret the intent of the challenge.

A 62-byte recursive variant of this satisfies all 3 bonuses (try it here):

f={b=n=1;\(m,p)if(m)c((b<<-c(b,sample(p)))[n<<-n+1],f(m-1,p))}

---

R, 24 bytes

repeat cat(sample(7),"")

Attempt This Online!

Alternative: a full program that outputs an infinite sequence of random permutations of 1..7.
This probably satisfies the letter of the challenge, and other answers have used this approach, although it does seem rather trivial.

• Giuseppe: print is a byte shorter for your second response. And I think \(n)replicate(n,sample(7))[n] would be good for the first one?
• pajonk: @Giuseppe or show instead of print?
• Dominic van Essen: @Giuseppe & @pajonk - re: print or show - I considered this, but didn't like the way that the output is separated into chunks of 7, which seemed to go against the "Draw 1 piece from the bag" notion...
• Dominic van Essen: @Giuseppe - re: suggestion for first one - I interpreted "Your program/function/data structure must ... Draw 1 piece from the bag ... from the pool of existing pieces ... [and] When the bag is empty, refill the bag" to imply that the function should output one-at-a-time, and sequential runs should keep in account the pieces left in the bag.
• Dominic van Essen: @Giuseppe - But a variant of your suggestion that remembers the pieces in each bagful seems to work well: thanks a lot!

Answer 4

Raku, 23 bytes

{grab $||=SetHash(^7):}

Try it online!

Ungolfed:

{
 state $bag ||= SetHash(0..6);
 $bag.grab;
}

This is a function which, when called repeatedly, will return the integers 0-6 in a random order, then the same integers in a (likely) different random order, and so on, ad infinitum.

Raku has a built-in data type SetHash which stores a set of objects, and has a grab method that chooses one of them randomly, removes it from the set, and returns it. All that's left to do for this challenge is the refilling. A state variable ($ in the golfed version, $bag in the ungolfed one) stores the SetHash, which is reset to a new object with full contents (using ||) when the variable is undefined, as on the first call to the function, or has become empty, as after every seventh call.

Answer 5

JavaScript (Node.js), 62 bytes

f=_=>x.match(i=Math.random()*7|0)?f(x=x[6]?'':x):(x+=i,i);x=''

Try it online!

I hope I understood question correctly

Answer 6

05AB1E, 9 bytes

[7L.r) ̃ć,

Uses a bag with integers [1,2,3,4,5,6,7]. Outputs the random piece indefinitely on separated newlines.

Try it online.

1. (9 bytes) Replace 7 with I for the first bonus, where n is given as input-integer: try it online.
2. (8 bytes) Replace 7L with I for the second bonus, where the bag is given as input-list: try it online.
3. (11 bytes) Add Iô after ̃ for the third bonus, where n is given as input-integer and it'll output those n items as a list each iteration: try it online. _{Will use a combination of the existing list and a new shuffled list if the bag doesn't hold enough items anymore (e.g. let's say \$n=3\$ and the first two iterations where [4,2,5] and [1,7,3], then the third iteration will be [6,a,b], where the 6 is from the existing bag, and a,b are two random integers from a new bag).}

Explanation:

[ # Loop indefinitely:
 7L # Push a list in the range [1,7]
 .r # Randomly shuffle it
 ) # Wrap the entire stack into a list
 ̃ # Flatten it to a single list
 ć # Extract head; pop and push remainder-list and first item separately
 , # Pop and output this first item

Answer 7

Excel (ms365), 121 bytes

enter image description here

Formula in A1:

=LET(p,7,n,8,DROP(TAKE(REDUCE(0,SEQUENCE(ROUNDUP(n/p,0)),LAMBDA(a,b,VSTACK(a,SORTBY(SEQUENCE(p),RANDARRAY(p))))),n+1),1))

Idea here is that:

• 'p' - Represents the amount of distinct items in our bag;
• 'n' - Represents the amount of tokens we take out of the bag at once (with refilling it offcourse). You may change this to any reasonable integer;
• 'SEQUENCE(p)' - Represents our array. In this specific case we create an array of integers, but SORTBY() can take any array of any type. This however will start changing byte-count!

Below another sample where 'n' == 14 and another one where 'n' == 14 and 'p' == 3:

enter image description here enter image description here

Answer 8

Jelly, (削除) 6 (削除ここまで) 5 bytes

ẊÐḶFY

Implements the first bonus

Runs until a pattern is repeated

-1 byte thanks to Jonathan Allan!

How?

ẊÐḶFY : Main Link, One arg(Number of pieces)
Ẋ : Shuffle; return a random permutation
 ÐḶ : Loop; Repeat until the results are no longer unique
 F : Flatten list
 Y : Join z, separating by linefeeds

Attempt This Online!

• Baby_Boy: @JonathanAllan idek how I didn't catch that while golfing, thanks for the spot!

Answer 9

Factor, (削除) 63 (削除ここまで) 62 bytes

[ 0 get [ 7 iota 7 sample >vector dup 0 set ] when-empty pop ]

Try it online!

A quotation (anonymous function) that takes no arguments and outputs one piece each time it is called. You can look in the bag in between function calls with 0 get.

Answer 10

Go, (削除) 182 (削除ここまで) 165 bytes

import(."math/rand";."slices")
func f()func()int{b:=[]int{}
return func()int{n:=Intn(7)
for;Contains(b,n);n=Intn(7){}
b=append(b,n)
if len(b)>6{b=[]int{}}
return n}}

Attempt This Online!

A generator function that returns a function. When the returned function is called, it returns an int in the range [0,7).

• -17 bytes by using the now-stdlib slices package. Also applies to all "bonuses" below.

"Bonuses"

Arbitrary n distinct items, (削除) 204 (削除ここまで) 187 bytes

import(."math/rand";."slices")
func f(I[]int)func()int{b,l:=[]int{},len(I)
return func()int{e:=I[Intn(l)]
for;Contains(b,e);e=I[Intn(l)]{}
b=append(b,e)
if len(b)>=l{b=[]int{}}
return e}}

Attempt This Online!

Generator function now takes a list of elements to choose from.

Arbitrary n items + generic (comparable), (削除) 208 (削除ここまで) 191 bytes

import(."math/rand";."slices")
func f[T comparable](I[]T)func()T{b,l:=[]T{},len(I)
return func()T{e:=I[Intn(l)]
for;Contains(b,e);e=I[Intn(l)]{}
b=append(b,e)
if len(b)>=l{b=[]T{}}
return e}}

Attempt This Online!

Works for any comparable type (bool, int, float, string, pointer, channel, struct of comparables, array of comparables, typeset of comparable).

Arbitrary n items + generic (comparable) + k items at a time, (削除) 288 (削除ここまで) 271 bytes

import(."math/rand";."slices")
func f[T comparable](I[]T)(func()T,func(int)[]T){b,l:=[]T{},len(I)
A:=func()T{e:=I[Intn(l)]
for;Contains(b,e);e=I[Intn(l)]{}
b=append(b,e)
if len(b)>=l{b=[]T{}}
return e}
return A,func(n int)(N[]T){for i:=0;i<n;i++{N=append(N,A())};return}}

Attempt This Online!

A function that returns 2 functions. The first function takes 1 item, the second function takes k items.

Answer 11

Jelly, (4) 5 bytes

7ẊṄ€ß

A full program that prints forever.

Try it online!

\4ドル\$ bytes - ẊṄ€ß - taking either an arbitrary alphabet size TIO or an arbitrary alphabet (as a list) TIO.

How?

7ẊṄ€ß - Main Link: no arguments
7 - seven
 Ẋ - (implicit range [1..7]) shuffle
 € - for each:
 Ṅ - print with trailing newline
 ß - call this link again with the same arity

Answer 12

Pip, 11 bytes

{l|:SHaPOl}

This is a function that takes as an argument a list of possible piece values (implementing the first two bonuses) and returns a single piece each time it is called.

Attempt This Online!

Explanation

We store the current state of the bag in the global variable l. Initially, l is [].

{l|:SHaPOl}
{ } Define a function:
 l|: If l is empty, set it to
 SHa the function argument, randomly shuffled
 POl Pop the first element from l and return it

Answer 13

PHP, 79 bytes

$y=function()use(&$a){$a=$a!=[]?$a:range(0,6);shuffle($a);echo array_pop($a);};

Try it online!

Commented

$y = function() use (&$a) { // anonymous function with use clause by-reference
 $a = $a != [] // equal comparison, if $a is neither null nor empty array
 ? $a // then use $a 
 : range(0,6); // else create range array
 shuffle($a); // shuffle array 
 echo array_pop($a); // splice off and return last element of $a
};

• rydwolf: Welcome to Code Golf, and nice answer! Unless I'm missing something, I don't think the function calls itself anywhere, in which case you don't actually need the $y= under site rules.

Answer 14

Pip, (削除) 11 (削除ここまで) 8 bytes

LhP*SH,a

Implements the first bonus

-3 bytes thanks to DLosc!

How?

LhP*SH,a : One arg(Number of items)
 a : First arg
L : Loop x times;
 h : Literal for 100
 , : Range zero to a
 SH : Shuffle: random permutation of iterable
 * : Map
 P : Print

Try It Online!

• Baby_Boy: @DLosc thanks for the spot! :)

Answer 15

Zsh, 35 bytes

exec<<(while shuf -i1-7)
f()read -e

Attempt This Online!

Uniquely for zsh, this is a function f, not a full program.

If you want to cheat and output infinitely, you only need the while shuf -i1-7.

Setup:

• while shuf -i1-7: repeatedly output the shuffled range 1 to 7
• <(): create a pipe from the output of that loop
• exec<: move that pipe to standard input

f:

• read: read one word from standard input
• -e: and print it

Answer 16

Python 3, 59 bytes

-6 bytes thanks to @att

from random import*
while[*map(print,sample(range(7),7))]:1

Try it online!

Infinitely prints integers.

I dont know if this is valid: (54 bytes)
Prints all 7 integers of permutation in one line before a newline.

from random import*
while 1:print(*sample(range(7),7))

Try it online!

• att: *map(print,sample(range(7),7))

Answer 17

Haskell, 149 bytes

import System.IO.Unsafe
import System.Random
import Data.List
d(o,[])=d([],o)
d(o,p)=(\n->(n:o,p\\[n]))$(p!!)$unsafePerformIO$randomRIO(0,length p-1)

Try it online!

Answer 18

Clojure, 56 bytes

(run! #(run! println %)(repeatedly #(shuffle(range 7))))

Creates an infinite list containing random permutations of 0 to 6 and prints each number.

Try it online!

Answer 19

Brachylog, 7 bytes

7>N≜1|↰

Try it online!

This is a predicates that unifies its output with a random integer between 0 and 6, exhausting each possibility before beginning a new cycle.

Try generating 14 random unifications here!

You can change 7 to any other number to get bigger bags.

Explanation

7>N Take an unknown integer between 0 and 6
 ≜1 Assign a value to it, with a random choice
 | Else
 ↰ Recursive call

Since our variable is constrained in [0..6], ≜1 will randomly unify it with one of those 7 values, leaving a choice point for each one. Brachylog will try each choice point when asked (e.g. with f - findall, failure loops, or by pressing ; in Prolog’s REPL), so each integer value. | creates another choice point that will get called only once all the choice points created by ≜1 are exhausted.

Answer 20

Thunno, \$ 11 \log_{256}(96) \approx \$ 9.05 bytes

[7R7zPZw{ZK

Attempt This Online!

Port of mathcat's Vyxal answer.

Explanation

[7R7zPZw{ZK
[ # Forever:
 ZK # Print
 { # Each element of
 Zw # A random element of
 7zP # The permutations
 7R # Of range(7)

Bonuses

• Arbitrary n items: \$ 13 \log_{256}(96) \approx \$ 10.70 bytes, [z0Rz0zPZw{ZK
• Generic bag: \$ 12 \log_{256}(96) \approx \$ 9.88 bytes, [z0DLzPZw{ZK

Answer 21

C (gcc), 60 bytes

b;f(i,j){b-127||(b=0);for(;b&1<<(i=rand()%7););b|=1<<i;j=i;}

Try it online!

Explanation

b; // Bag: initialized with nothing selected
f(i,j){
 b-127||(b=0); // Reset bag when all 7 pieces selected
 for(;b&1<<(i=rand()%7);); // Find a random unselected piece
 b|=1<<i; // Mark it as selected
 j=i; // Return the piece
}

• Todd Lehman: Cool trick!! So, I have a question, and this isn't criticism, just a curiosity... Why write for(;X;) instead of while(X)? They're the same number of characters, so the for version doesn't provide a golfing advantage.
• ErikF: @ToddLehman I just prefer using for, that's all: I find it to be more flexible overall.
• emanresu A: 58

Answer 22

Perl 5 -MList::Util=shuffle, 29 bytes

,ドル=$/;1while say shuffle 1..7

Try it online!