# Implement a bag without replacement

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

### "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.

# Vyxal, 5 bytes

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

{7Þ℅⟑,

Try it Online!

Explanation

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

Bonuses:

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

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

• 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? Jan 13, 2023 at 18:36
• @Giuseppe or show instead of print? Jan 13, 2023 at 19:18
• @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... Jan 13, 2023 at 22:19
• @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. Jan 13, 2023 at 22:24
• @Giuseppe - But a variant of your suggestion that remembers the pieces in each bagful seems to work well: thanks a lot! Jan 13, 2023 at 22:40

# 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

# Raku, 23 bytes

{grab $||=SetHash(^7):} Try it online! Ungolfed: { state$bag ||= SetHash(0..6);

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
};

Try it online!

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

# Brachylog, 7 bytes

7>ℕ≜₁|↰

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>ℕ        Take an unknown integer between 0 and 6
≜₁     Assign a value to it, with a random choice
|    Else
↰   Recursive call

Since our variable is constrained in [0..6], ≜₁ 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 ᶠ - 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 ≜₁ are exhausted.

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

[7R7zPZw{ZK

Attempt This Online!

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

# 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
}