Processing Tetris queues with hold slots

2026-11-07

I really should have written this 1-2 years ago, but now I am here writing it after publishing the initial version of a tool implementing the algorithm. If (1) there are enough readers and (2) there are enough complaints about the lack of rigour/detail, I may write a follow-up article. I am also open to anyone showing me my work is completely wrong and dumb.


Context

Consider a Tetris piece sequence, like the classic 7-bag IJLOSTZ. Now, imagine we have access to a hold slot (as we do in modern Tetris) and we can use it to permute the sequence. For instance, we can hold the J piece until the T piece arrives, and subsequently hold the T piece until the end.

IJLOSTZ _
I_LOSTZ J
I_LOSJZ T

Our sequence becomes ILOSJZT.

Problem

Given sequences 𝑠 and 𝑠′, let’s define that 𝑠′ is reachable from 𝑠 iff 𝑠 can be permuted with the hold slot into 𝑠′. Let 𝑓(𝑠)={𝑠′|𝑠reaches𝑠′with hold} for a piece sequence 𝑠.

Suppose we are given a set 𝑆 of sequences with the same length 𝑛. We can assume that these are given as strings in some form. We would like to compute the set 𝑓(𝑆)=βˆͺπ‘ βˆˆπ‘†π‘“(𝑠), which is the set of all sequences that are reachable with hold by some π‘ βˆˆπ‘†.

Note. It should be noted that (unless stated otherwise) I am assuming a constant-size alphabet Ξ£ and that integer/pointer/word operations run in 𝑂(1) time. I believe most of this analysis can be extended, though.

An obvious method

We can compute 𝑓(𝑆) β€œliterally”. For each π‘ βˆˆπ‘†, we will compute 𝑓(𝑠), and somehow compute their union over all 𝑠. Given 𝑠, we can simulate the hold sequences: so long as there is a subsequent piece, we can choose (not) to press the hold key, so there are 2π‘›βˆ’1 possibilities. This yields an upper bound of |𝑓(𝑠)|=𝑂(2𝑛) distinct queues, which can be less than 2π‘›βˆ’1 with duplicate symbols in 𝑠. We output each 𝑠′ as a string of length 𝑛, so at best we can compute and output these 𝑂(2𝑛) queues in 𝑂(𝑛) time each. We thus obtain a running time of 𝑂(𝑛⋅2𝑛) for each π‘ βˆˆπ‘† and 𝑂(𝑛⋅2𝑛⋅|𝑆|) total. To compute the union of all 𝑂(2𝑛⋅|𝑆|) strings, we can insert them into a trie in 𝑂(𝑛⋅2𝑛⋅|𝑆|) time, matching the preceding phase and achieving an overall running time of 𝑂(𝑛⋅2𝑛⋅|𝑆|).

Alternative formulation of holding

Above, we described the process of holding as choosing (not) to press the hold key. We can instead think of it as choosing whether to place the held piece before or after the current one. The hold slot is initially empty, so we consider the first piece held (this has no effect on what sequences are reachable). Now, our decisions line up: the current piece is held iff the held piece is put before it.

At each step 𝑖=1,2,…,π‘›βˆ’1 we optionally swap the symbols at positions 𝑖 and 𝑖+1 to model our before/after choice. Consider the initial example IJLOSTZ, aligned to our current model (I is held). Recall that we held J and T, so with our new formulation we would perform the following procedure:

IJLOSTZ
IJLOSTZ  dont swap I,J =      hold J
ILJOSTZ       swap J,L = dont hold L
ILOJSTZ       swap J,O = dont hold O
ILOSJTZ       swap J,S = dont hold S
ILOSJTZ  dont swap J,T =      hold T
ILOSJZT       swap T,Z = dont hold Z

Using the alternative

Our observation immediately yields a nice method for actually computing 𝑓(𝑠) given 𝑠.

let f(s):
  let T = {s}
  for i = 1, 2, ..., n-1:
    let T_swap =
      {t with i, i+1 swapped | t in T}
    T = T union T_swap
  return T

It’s also obvious that the running time is 𝑂(𝑛⋅2𝑛) since the set 𝑇 does not more than double in size every iteration, giving us a geometric series. Then, to compute 𝑓(𝑆):

let f(S):
  let T = {}
  for s in S:
    T = T union f(s)
  return T

An improved method

It’s not immediate to me the properties that make it correct (I may not even know them), but I think it should be relatively obvious that we can avoid computing all 𝑓(𝑠) and taking their union. Instead, we let the initial value of 𝑇 be 𝑆 itself to process all π‘ βˆˆπ‘† β€œin parallel”.

let f(S):
  let T = S
  for i = 1, 2, ..., n-1:
    let T_swap =
      {t with i, i+1 swapped | t in T}
    T = T union T_swap
  return T

Running time

We can obtain a (generally) loose upper bound on running time using the number of reachable sequences |𝑓(𝑆)|. Clearly, the size of 𝑇 is non-decreasing across iterations, so it always holds that |𝑇|β©½|𝑓(𝑆)|. Each iteration, we produce |𝑇| new strings in 𝑂(𝑛⋅|𝑇|) time and perform a union, giving us either an expected 𝑂(𝑛⋅|𝑇|) with hashing or a worst-case 𝑂(𝑛⋅|𝑇|lg|𝑇|) running time with various methods (ordered set, sort + unique). Thus, the overall running time over all iterations is 𝑂(𝑛2β‹…|𝑓(𝑆)|lg|𝑓(𝑆)|).

This is already an improvement to the worst case over the initial method. Let 𝑀=|𝑓(𝑆)| and consider when 𝑆 is near saturation i.e. |𝑆|∼|𝑓(𝑆)|=𝑀. The initial method runs in 𝑂(𝑛⋅2𝑛⋅𝑀), while the new method runs in 𝑂(𝑛2⋅𝑀lg𝑀). While 𝑀 can be rather large, lg𝑀 should be linearithmic in 𝑛. So the extra factor on top of 𝑀 is a polynomial 𝑂(𝑛𝑑) vs exponential 𝑂(𝑛⋅2𝑛).

Using a better data structure

Since we eliminated the concept of a hold slot by using swaps instead, it’s easy to pick a different data structure for storing sets of strings. From a trie 𝑇, we can produce 𝑇swap also as a trie; this happens in linear time and it can be shown the number of nodes in 𝑇swap is linear to that of 𝑇. Then, we can take their union in linear time as well. Similarly to before, the number of nodes in 𝑇 is non-decreasing since π‘‡βŠ†(𝑇βˆͺ𝑇swap) and a subset certainly does not need more nodes. If we let 𝑁 be the number of nodes in the resulting trie 𝑓(𝑆), then our algorithm for computing 𝑓(𝑆) runs in 𝑂(𝑁) time per iteration for 𝑂(𝑛⋅𝑁) overall running time.

The value of 𝑁 can fluctuate as |𝑓(𝑆)|⩽𝑁⩽𝑛⋅|𝑓(𝑆)|. However, if we consider some worst-case, very saturated sets 𝑓(𝑆):

  • 𝑓(𝑆) contains (nearly) all permutations of a string with many distinct symbols
  • 𝑓(𝑆) contains (nearly) all possible strings

…then 𝑁 is closer to |𝑓(𝑆)| because the trie is dense.

Don’t we accept/return a set of strings?

If we get a set of |𝑆| strings, we can construct a trie for this set in 𝑂(𝑛⋅|𝑆|) time. Streaming the final set of |𝑓(𝑆)| strings runs in 𝑂(𝑛⋅|𝑓(𝑆)|) time. Since |𝑆|β©½|𝑓(𝑆)|⩽𝑁, the overall running time is 𝑂(𝑛⋅𝑁), including computing 𝑓(𝑆).

Brief running time comparison

Let’s assume 𝑆 contains all permutations of a string that has 𝑛 distinct symbols (all distinct). We have 𝑆=𝑓(𝑆) and |𝑆|=|𝑓(𝑆)|=𝑛!, and it turns out that the number of nodes in a trie storing these strings is also Θ(𝑛!).

  • Initial: 𝑂(𝑛⋅2𝑛⋅𝑛!)
  • Improved: 𝑂(𝑛3lg𝑛⋅𝑛!) or expected 𝑂(𝑛2⋅𝑛!)
  • Improved + trie: 𝑂(𝑛⋅𝑛!)

Alternatively, let’s assume 𝑆 contains all possible strings, and the alphabet is the 7 tetrominoes. we have 𝑆=𝑓(𝑆) and |𝑆|=|𝑓(𝑆)|=7𝑛. The trie has Θ(7𝑛) nodes.

  • Initial: 𝑂(𝑛⋅2𝑛⋅7𝑛)
  • Improved: 𝑂(𝑛3β‹…7𝑛) or expected 𝑂(𝑛2β‹…7𝑛)
  • Improved + trie: 𝑂(𝑛⋅7𝑛)

So, I think we did a good job.

Actual performance

I wrote up a serial trie implementation that packs nodes as a contiguous pre-order traversal. Random access isn’t needed, so it’s optimized for setwise operations and streaming. I’ll write another article about that if I want to. It’s quite fast on my machine: given 𝑆 as all permutations of IIJJLLOOSSTZ, it builds the trie 𝑓(𝑆)=𝑆 in about 700ms. You can check its performance.


Conclusion

I had fun designing this algorithm and engineering its Rust implementation. This section will answer small questions that don’t warrant a separate post, and I might add to it.

What if I want to compute the reverse?

Let 𝑔(𝑠)={𝑠′|𝑠′reaches𝑠with hold}, and 𝑔(𝑆)=βˆͺπ‘ βˆˆπ‘†π‘”(𝑠). To compute 𝑔(𝑆), we follow a similar procedure to 𝑓(𝑆) but perform the swaps in reverse order:

let g(S):
  let T = S
  for i = n-1, n-2, ..., 1:
    let T_swap =
      {t with i, i+1 swapped | t in T}
    T = T union T_swap
  return T

Combining 𝑓 and 𝑔 is a nice workflow for research. Given the set of queues 𝑆, we would like to determine which ones can stack a specific shape, but we also want to consider hold slots. We compute 𝐴=𝑓(𝑆) and run our solver on the queues in 𝐴 to get 𝐡, those that can stack the shape. Then, we compute 𝐢=𝑔(𝐡) to get all queues that can stack the shape using a hold slot, and we take the intersection π‘†βˆ©πΆ to restrict it to the input queues.

What if I have multiple hold slots?

The tool I wrote generalizes to any number of slots, but I think it requires a more involved correctness argument even when hand-waved. I can write about it in another post, because this one is already quite long despite the lack of detail and rigour.


@2026 bzy.