Shapez 2 Shape Enumerator and Solver

An exhaustive enumerator and solver for all buildable shapes in Shapez 2. The program discovers every shape that can be constructed using the game's buildings, and can decompose any buildable shape into a step-by-step construction plan.

Building

Requires Linux, C++23, and CMake 3.16+.

mkdir build && cd build
cmake ..
make -j$(nproc)

This produces three main executables:

• search -- run the half search, pin-push-essential search (Algorithm B), and/or full shape enumeration (Algorithm A), writing a single section-based data file
• build_plan -- decompose a shape into construction steps
• verify -- cross-validate the sections of a data file produced by search

Running

Run the search

./search Quad4 output/quad4.bin --pp-parents

Arguments: <config> <output.bin> [--half-parents] [--pp-parents] [--full-set].

Config names (case-insensitive): Quad3 Quad4 Quad5 Quad6 Quad7 Hex3 Hex4 Hex5 Oct3 Dec3.

Flags select which sections to write. The halves bitset is always written.

• --half-parents: record how each half was first discovered (needed by build_plan).
• --pp-parents: run Algorithm B and record PP-essential parents (needed by build_plan; implies --half-parents).
• --full-set: run Algorithm A and write the full non-swappable trie.

Decompose a shape

./build_plan output/quad4.bin "CuCu----:RrRr----"

Arguments: <shape_file.bin> <shape_code>. NC and ML are inferred from the file header. The file must have been produced with --pp-parents (which also implies --half-parents).

Example:

$ ./build_plan output/quad5.bin "P-P-P-P-:P-P-P-P-:CyCrCrCy:cb----Cg:CgcgCy--"
[pin_push] P-P-P-P-:P-P-P-P-:CyCrCrCy:cb----Cg:CgcgCy--
  [rotate_180] P-P-P-P-:CyCrCrCy:cb----Cg:CgcgCycu:------cu
    [swap] P-P-P-P-:CrCyCyCr:--Cgcb--:CycuCgcg:--cu----
      [pin_push] P-P-----:CrCy----:--Cg----:Cycu----:--cu----
        [cut_east] CrCy----:--Cg----:Cycu----:--cu----
          [swap] CrCy--Cu:cuCg--cu:Cycu----:--cu----
            [input] CrCy----:cuCg----:Cycu----:--cu----
            [input] ------Cu:------cu
      [rotate_180] ----P-P-:----CyCr:----cb--:----Cgcg
        [cut_east] P-P-----:CyCr----:cb------:Cgcg----
          [rotate_cw 1] P-P-Cu--:CyCrCu--:cb--P---:CgcgCu--
            [swap] P-Cu--P-:CrCu--Cy:--P---cb:cgCu--Cg
              [cut_east] P-Cu----:CrCu----:--P-----:cgCu----
                [swap] P-Cu--Cu:cuCu--cu:CrP-----:cgCu----
                  [stack] P-Cu----:cuCu----:CrP-----:cgCu----
                    [pin_push] P-------:cu------:Cr------:cg------
                      [input] cu------:Cr------:cg------
                    [input] --Cu----
                    [input] --Cu----
                    [input] --P-----
                    [input] --Cu----
                  [input] ------Cu:------cu
              [pin_push] ------P-:------Cy:------cb:------Cg
                [input] ------Cy:------cb:------Cg

Each node is an operation whose output is the shape on that line; its indented children are the operands. [input] leaves are half-set shapes the plan bottoms out on.

Verify a data file

./verify output/quad4.bin

Runs whichever cross-checks the file's sections support:

• full_set + pp_parents: every PP shape is in the full set; every full-set entry is PP or stackable from a known base.
• half_parents + pp_parents: build a plan for every half and for every PP shape; each plan must validate against its target (catches cycles in the PP parent chain -- a loop would fail validate or recurse forever).

Exits with status 0 on PASS, 1 on any failure. The first few failing shapes are printed to stderr as shape codes.

Run tests

cd build
ctest        # run all tests
./test_shape # run a specific test

---

Algorithm Overview

Shape representation

In Shapez 2, each shape is composed of layers, each layer is composed of parts, and each part has a type and a color (see Shape). A part can be empty, normal (circle, square, etc), a pin, or a crystal. Normal parts and crystals also carry a color. The parts at the same position across all layers form a column. Layers are numbered 0 from the bottom up; columns are numbered 0 from the top-right going clockwise.

Note on terminology: The codebase uses the term "corner" interchangeably to refer to a part or a column.

For search, shapes are compactly encoded as a CompactShape -- a single uint64_t with 2 bits per part (EMPTY=00, NORMAL=01, PIN=10, CRYSTAL=11). This discards the specific shape type and color, since they do not affect whether a shape is buildable.

Game operations

The search models these Shapez 2 buildings:

• Cutter: splits a shape into east and west halves. Crystals spanning the cut boundary shatter (chain reaction through connected crystals), then gravity applies.
• Stacker: places one shape on top of another with gravity.
• Swapper: exchanges the west halves of two input shapes. Equivalent to cutting both, then recombining crosswise.
• Pin Pusher: pushes pins under a shape -- shifts all layers up by one and inserts pins at the bottom under every occupied part. Top-layer overflow may trigger crystal shattering and gravity.
• Painter: colors all normal parts in the topmost layer. Pins and crystals are unaffected.
• Crystal Generator: fills empty and pin positions with crystals of a given color, up to the shape's highest occupied layer.
• Gravity: not a building, but a physics rule applied after most operations. Parts must be supported (by ground contact, horizontal adjacency to other supported non-pin parts, or crystal hanging from above). Unsupported crystals shatter; unsupported normal parts fall as connected groups. Note: the game has a bug that can produce floating shapes under certain conditions; this implementation does not replicate that bug.

Search pipeline

The search has two stages. First, the half search discovers all buildable half-shapes -- shapes occupying only the east half of each layer, as produced by the Cutter. The BFS (Ops 1-5) is followed by an outer loop (Op 6) that discovers halves requiring cross-boundary stacking anchors.

Then, either Algorithm A or Algorithm B is run on the half set. They are independent of each other:

• Full search (Algorithm A) enumerates all buildable full shapes. Memory-intensive -- Hex 4-layer requires ~28 GB.

• Pin-push search (Algorithm B) finds only the small set of PP-essential shapes -- sufficient to decompose any buildable shape without enumerating all of them. Faster and far more memory-efficient than Algorithm A.

Both algorithms also verify the completeness of the half search.

After search, the build plan decomposer reconstructs a step-by-step construction plan for any target shape by tracing parent pointers recorded during search.

Key terms

• NC: number of parts per layer (4 for quad, 6 for hex).

• ML: maximum number of layers.

• Half-shape: a shape with content only in the east half (parts 0 through NC/2 - 1), as produced by the Cutter.

• Canonical form: the lexicographically smallest CompactShape value over all rotations and mirrors of a shape.

• Half-canonical form: for half-shapes, min(h, mirror(rotate_180(h))) -- the only two orientations that preserve the east half.

• Swappable: a full shape where, in some orientation, both its east and west halves appear in the half set. Can be trivially built via the Swapper; does not need separate storage.

• Stackable: a shape decomposable into a base shape plus valid Stacker operations.

• PP-essential (pin-push-essential): a shape that is neither swappable nor stackable from any known base. The only way to build it is with the Pin Pusher as the final step.

---

Benchmarks

Benchmarked on an Intel i7-11700K (8 cores / 16 threads, 3.6 GHz base / 5.0 GHz turbo), 32 GiB DDR4-3600 (dual-channel, running at 2400 MHz). Times are wall time from search step timers (stderr).

Shape counts are canonical; non-canonical partners are recovered by symmetry. Dashes mark configurations where Algorithm A exceeds 32 GiB RAM; only Algorithm B was run.

Configuration	Halves (canonical)	Total (swap + non-swap)	Non-swappable	PP-essential	Halves	Full set	PP
Quad 3-layer	1,796 (917)	502,906	11,627	7	0.00 s	1.00 s	2.88 s
Quad 4-layer	16,193 (8,148)	44,233,241	2,002,457	504	0.02 s	1.05 s	2.88 s
Quad 5-layer	135,074 (67,669)	3,378,515,280	251,172,538	39,296	0.25 s	40.70 s	2.84 s
Quad 6-layer	1,058,849 (529,749)	-	-	2,567,294	3.97 s	-	28.82 s
Quad 7-layer	7,905,398 (3,953,472)	-	-	144,114,323	65.56 s	-	22 min 12 s
Hex 3-layer	81,352 (41,574)	675,495,801	2,920,982	80	0.04 s	13.16 s	2.88 s
Hex 4-layer	2,331,921 (1,174,057)	633,883,327,124	8,929,915,941	180,146	2.16 s	3 h 14 min	29.11 s
Hex 5-layer	59,985,914 (30,060,494)	-	-	170,267,313	2 min 39 s	-	5 h 39 min
Oct 3-layer	3,649,792 (1,825,794)	-	-	458	2.96 s	-	13.98 s
Dec 3-layer	163,768,112 (81,924,732)	-	-	3,463	3 min 26 s	-	1 h 24 min

PP-essential counts are the true PP count (final PP set size minus the redundant "kept for parent chain" leftovers).

---

Algorithm Details

This section provides implementation-level detail for each component.

1. Shape Representation

Geometry

A shape is a stack of up to ML layers (layer 0 = bottom). Each layer has NC parts arranged in a ring. The parts at the same position across layers form a column. Layers are numbered 0 from the bottom up; columns are numbered 0 from the top-right going clockwise. See the Shapez 2 wiki for the full list of part types and colors.

Shape code

Shapes are encoded as shape codes -- layers separated by colons, bottom to top. Each layer is NCx2 characters, with pairs of (type char, color char) per part. Examples:

CuCu----           single layer: circles at columns 0-1, empty at 2-3
CuCu----:RrRr----  two layers: circles on bottom, red squares on top
--------            empty shape

CompactShape

For search, shapes are stored as a CompactShape<Trait> -- a single uint64_t with 2 bits per part (the Trait parameter pins NC and ML at compile time):

Encoding	Bits	Meaning
EMPTY	00	No content
NORMAL	01	Any normal part (circle, square, star, etc.)
PIN	10	Pin
CRYSTAL	11	Crystal

Layout: layer 0 in the least-significant bits, column 0 in each layer's LSBs. Each layer occupies NC x 2 bits. Total width is NC x ML x 2 bits (e.g., 32 bits for Quad4, 48 bits for Hex4).

This encoding discards specific shape types and colors, since they do not affect buildability: all normal part types behave identically under every game operation, single-part shapes of any type are available as raw inputs, and the Painter can change any normal part to any color. Types and colors are restored during build plan generation.

Canonical form: the minimum CompactShape value over all 2xNC orientations (NC rotations x 2 mirror states).

2. Game Operations

These model the buildings and physics of Shapez 2.

Cutter

Splits a shape into east and west halves along two boundaries:

• Between columns EC-1 and EC (where EC = NC/2)
• Between columns NC-1 and 0

If a crystal on one side of a boundary is adjacent to a crystal on the other side, both become shatter seeds. Crystal shattering propagates via BFS through all 4-connected crystals (horizontal neighbors within a layer, vertical neighbors across layers). After shattering, gravity applies to each half independently.

Stacker

Places a top shape onto a bottom shape. The implementation uses a workspace of 2xML+1 layers: bottom at layers 0..ML-1, an empty gap at layer ML, and top at layers ML+1..2xML. Gravity is applied to the entire workspace. The result is the bottom ML layers; content above ML is truncated. This is safe because the gap prevented any crystal connections across the boundary.

Stack layer

A simplified Stacker variant used during search: drops a single-layer piece onto a shape. The piece lands at the height of the tallest occupied column among the columns it covers. If that height equals ML, the piece does not fit and the shape is unchanged.

Due to the gravity rules, stacking any shape on top of another is equivalent to consecutively stacking connected single-layer pieces. This means the search only needs to consider connected single-layer pieces rather than arbitrary multi-layer shapes.

Swapper

Exchanges east and west halves between two shapes. Implemented as: cut both shapes, then recombine A's east with B's west, and B's east with A's west.

Pin Pusher

Shifts all layers up by one and inserts pins at layer 0 under each column that was occupied at layer 0. If the shape already uses all ML layers, the top layer is lost to overflow -- any crystals that were in that layer become shatter seeds. After shattering, gravity applies.

Gravity

Determines which parts are supported and handles unsupported content:

1. Support BFS (bottom-up, iterated to fixed point):

   • Layer 0: all occupied parts are supported (resting on ground)
   • Vertical: a part is supported if the part directly below it is supported
   • Horizontal: a non-pin part is supported if a horizontally adjacent non-pin part at the same layer is supported
   • Crystal hanging: a crystal is supported if the crystal directly above it is supported (crystals can hang downward from other crystals)

2. Shatter unsupported crystals: removed immediately.

3. Drop unsupported non-crystal parts: remaining unsupported parts fall downward. Parts that are horizontally adjacent (excluding pins) form groups and fall together as a unit. Each group drops by the smallest gap beneath any of its members. Groups are processed bottom-to-top, since a lower group must land before a higher group can land on top of it.

Crystal shattering

BFS from seed positions through all 4-connected crystals: spreads to horizontal neighbors (columns +/-1 mod NC) and vertical neighbors (layers +/-1). All reached crystals are removed. Triggered by cutting (boundary crystals), pin pushing (top-layer overflow), and gravity (unsupported crystals).

Painter

Recolors all normal parts in the topmost occupied layer. Pins and crystals are unaffected.

Crystal Generator

Fills all empty and pin positions within the shape's occupied layers with crystals of a given color. Existing normal parts and crystals are unchanged.

3. Half Search

Goal: discover all buildable half-shapes -- shapes with content only in the east columns (0 through EC-1), as produced by the Cutter.

The half search discovers buildable halves via BFS. Every half it outputs is provably buildable (each is derived from seeds by valid game operations), but the algorithm does not prove completeness -- it is possible in principle that some buildable half is missed. Completeness is verified externally by Algorithm A or B (see Section 4 and 5).

Half-canonical form

The transformation mirror().rotate_180() maps east columns onto east columns, so each half-shape has a symmetric partner. The half-canonical form is min(h, mirror(rotate_180(h))). The search stores only canonical halves; symmetric partners are added at the end.

Compact key

East columns are packed layer-major into a uint32_t: each layer contributes NC bits (2 bits per east column), for a total key width of NCxML bits.

Seeds

The BFS begins with all east halves where each column independently has height 0..ML, and each occupied part is independently NORMAL or CRYSTAL. These are all trivially buildable: each column can be built by layer-by-layer stacking (for normal parts) or crystal generation (for crystals), using scaffold in the remaining columns, then swapped together. Since these seeds cover all possible outputs of the Crystal Generator (by swapping two such halves), the Crystal Generator does not need to appear as a search operation.

BFS operations (Ops 1-5)

From each dequeued half, the search applies:

Op 1 -- Pin Pusher: apply pin push to the half.

Op 2 -- Stack layer: drop each possible single-layer piece onto the half. Pieces consist of all contiguous arcs of east columns (ECx(EC+1)/2 arcs) plus EC single pins. For example with EC=2: arcs {0}, {1}, {0,1} and pins at 0, 1 -- 5 pieces total.

Op 3 -- Boundary crystal break: simulates swapping a half with a seed that has crystals at the cut boundary, then cutting. For each subset of boundary crystal positions (columns 0 and EC-1 across all layers), computes which crystals would shatter via BFS (shattering does not spread across the cut boundary since the halves are already separated), applies gravity, and inserts the resulting east half. The parent is recorded as SWAP_CUT with the minimum west seed (constructed from the crystal subset) as the second half.

Op 4 -- Rotation projections (batch, runs after each BFS phase): captures halves that arise from swapping two halves into a full shape, rotating it, and then cutting. The rotation means the cut boundary falls at a different position, so the resulting east half mixes parts from both original halves.

To enumerate this efficiently without materializing all full shapes, each half is projected to a subset of its columns. For each column count NumColumns from 1 to EC-1, the first NumColumns columns of each half are extracted with pre-shattering at the projection boundary, recording both the content and an inner_shatter bitmask (which layers had shattering reach column 0, where the two projections will be joined). Complementary projections (NumColumns and EC-NumColumns from two halves) are then combined to form the east half of the rotated-then-cut result. Crystal shattering is propagated across the junction where the two projections meet, gravity is applied, and the result is inserted.

Op 5 -- Crystal column + Pin Pusher + rotate + cut (quad only): Op 1 applies pin push to a half-shape, but this only inserts pins under east columns. When pin push is applied to a full shape, pins are inserted under all columns, and the subsequent crystal shattering and gravity can produce halves (after rotate + cut) that Op 1 alone cannot reach. Op 5 handles this case for a specific class of full shapes. A qualifying west half has column 0 all-crystal with only column 0 occupied in the top layer, and column 1 containing at least one pin, no crystals, and a non-pin as its topmost part. The east half is any half where every column contains at least one crystal and the top layer is empty. The combined full shape is pin-pushed, then rotated through all NC orientations, and each rotation is cut to produce new halves.

This handles columns with the pattern Gap-Shape-Gap-Crystal (bottom to top), where a crystal hangs above an empty gap. In hex shapes, Ops 1-4 can already produce such columns, so Op 5 is not needed.

Concrete example (the only Op 5 result in Quad 4-layer): east half --cu----:CuCu----:cu------ and west qualifying half cuCu----:cuP-----:cuCu----:cu------ are swapped into the full shape --cucuCu:CuCucuP-:cu--cuCu:----cu--. Pin push produces --P-P-P-:CuCu--Cu:------P-:cu----Cu. Rotating 1 step clockwise and cutting yields the east half P-------:CuCu----:P-------:Cucu---- -- a half with a Pin-Shape-Pin-Crystal column that cannot be reached by Ops 1-4.

BFS structure

Phase A (per-half): dequeue a half, apply Ops 1-3. If the half qualifies for Op 5, record it. Phase B (batch): apply Op 4 (rotation projections) and Op 5 (crystal column) across all new halves. Repeat until no new halves are found.

Op 6 -- Cross-boundary stacking closure (outer loop)

After Ops 1-5 stabilize, Op 6 discovers halves that require cross-boundary stacking -- where a stacked piece spans the east-west boundary and the west side provides an anchor that the east side lacks. Ops 1-5 operate on halves independently and cannot reproduce this.

Op 6 enumerates stacking closures of swappable shapes (swap + stack + optional rotate + cut) starting from base halves. It shares a common stacking enumeration strategy with the PP-essential verification (Section 5). A full enumeration would try all valid additions on both east and west sides at each layer. Since we only need the east half (the west side is discarded after cutting), the enumeration is pruned: the west side always fills with normals wherever not blocked, while only the east side varies. This is valid in two directions. Soundness (no spurious east halves): replacing any supported non-blocked position with a normal produces a valid stacking. Since west is filled with normals from the bottom up, every non-blocked west position is automatically supported, so every west normal placed is a valid addition. Completeness (no missed east halves): for any valid stacking with arbitrary west content, replacing west parts with normals layer by layer produces a valid stacking with the same east content (by the soundness property), and more content below only provides more support for subsequent layers. Cross-boundary pieces are naturally included -- a west normal can anchor adjacent east content.

Two cases (parallelized over base halves / projection pairs):

No rotation: for each base half, construct minimum west for each boundary crystal subset -- each column is as high as its highest crystal, with normals below. This is sufficient because any taller west configuration with the same crystal positions can be reproduced by stacking normals onto the minimum shape. Enumerate stacking, cut, and insert new east halves.

With rotation (modified Op 4): each projection records not only the content and inner_shatter bitmask, but also the column heights before pre-shattering, since they determine where stacked pieces land. For columns that end up in the final east half, all heights must be considered. For columns that do not, only the minimum heights under the partial order of column height vectors are needed -- taller configurations can be reproduced by stacking onto shorter ones. Enumerate each projection combination, cut, and insert.

If Op 6 finds new halves, the BFS (Ops 1-5) is re-run on the new halves. This outer loop repeats until no new halves are found.

After the outer loop completes, expand with symmetric partners: for each canonical half h, insert mirror(rotate_180(h)) into the set.

Parent tracking

When parent tracking is enabled (search_halves_with_parents), each half records how it was first discovered. The HalfOp tag identifies the operation and the fixed-size payload carries the operand half keys (plus a stacked-content blob for the last variant):

• SEED: a starting shape (Op seeds)
• PIN_PUSH: parent half + pin push (Op 1)
• STACK_LAYER: parent half + piece (compact half key; Op 2)
• SWAP_CUT: two parent halves -- swap into a full shape, rotate, then cut east. Covers Op 3 (boundary crystal break, with a constructed min-west seed as the second half) and Op 4 (rotation projections, with both projection sources)
• SWAP_PIN_CUT: two parent halves -- swap, pin_push, rotate, cut (Op 5 crystal column, quad only)
• SWAP_STACK_CUT: two parent halves + stacked content -- swap, rotate, stack the recorded pieces, cut (Op 6 cross-boundary stacking)

The rotation index is not stored; the decomposer rediscovers it by searching orientations.

Parents are frozen when a half is dequeued from the BFS queue (Phase A) or when a batch operation completes (Phase B). While still pending, a half's parent may be updated to a lexicographically smaller one (ensuring minimal-cost parents). Once frozen, the parent is immutable. This prevents cycles: a dequeued half A may generate child B, but B can never update A's parent (already frozen), so the parent chain always points to halves frozen earlier.

4. Full Search (Algorithm A)

Goal: enumerate all buildable full shapes by combining halves and expanding via stack layer and pin push.

Swappable vs non-swappable

A full shape is swappable if, in some orientation, both its east and west halves appear in the HalfSet. Swappable shapes can be built trivially via the Swapper, so they need not be stored separately. The search only stores non-swappable shapes in a trie.

Seed generation

For each pair of canonical halves (h_e, h_w) with h_w >= h_e (by compact key):

1. Form full = h_e | rotate_180(h_w) (Variant 1)
2. Form full = h_e | rotate_180(half_sym(h_w)) (Variant 2, if half_sym(h_w) != h_w)

For each variant, check whether this is the minimal pair: no other orientation of the same canonical full shape has a lexicographically smaller (h_e, h_w) pair that is also swappable. If a smaller pair exists, skip -- another iteration will handle it. This avoids double-counting without needing a deduplication set.

If the pair is minimal, count it as swappable and proceed to DFS.

DFS from seeds

From each seed, depth-first search applies:

• Pin push: if the result is non-empty, non-swappable, and unseen, insert into the trie and continue DFS
• Stack layer with each piece (all contiguous NORMAL arcs wrapping around NC columns, plus single PINs): if the shape changed, is non-swappable, and unseen, insert and continue

The seen set is a HierarchicalBitset -- a multi-level trie supporting lock-free concurrent insertion (see Section 7).

Parallelization

The outer loop over east halves is parallelized: threads claim indices via an atomic counter. Each thread has its own DFS stack but shares the global seen set (lock-free). Local counters are periodically flushed to shared atomics.

Orientation counting

Each canonical shape represents 2*NC / |stabilizer| distinct orientations, where the stabilizer is the set of rotations and mirrors that fix the shape. This count is accumulated to report total shapes across all orientations.

Verification

After the search completes, every non-swappable shape in the trie is cut in NC/2 rotations. Both resulting halves must appear in the HalfSet. A failure indicates the half search missed a buildable half.

5. Pin-Push Search (Algorithm B)

Goal: find all shapes whose last construction step must be pin push -- they cannot be produced by stacking as the final operation.

Motivation

Algorithm A stores all non-swappable shapes in a global trie, which requires tens of GB for larger configurations (~28 GB for Hex 4-layer). For Hex 5-layer, the trie would exceed available memory. Algorithm B avoids the global trie entirely: it stores only the small set of pin-push-essential (PP) shapes. Combined with the swappable set (derivable from halves alone), the PP set is sufficient to decompose any buildable shape.

High-level idea

The set of all buildable shapes is the closure of three operations: cut/swap, stack, and pin push. Algorithm B computes this closure without enumerating all shapes:

• Cut/swap closure: assumed to be captured by the half searcher (the set of all swappable shapes). This is verified at the end.
• Stack closure: handled implicitly. Rather than materializing all stackable shapes, the stackability check can determine on the fly whether a given shape is decomposable into a known base plus stacking operations. The stacking closure enumeration generates all shapes reachable by stacking from a given seed.
• Pin push closure: computed explicitly by the algorithm. Starting from swappable seeds, it applies pin push and classifies results as either stackable (from known bases) or PP-essential. Batches iterate until no new PP shapes are found.

The key insight is that every buildable shape is either swappable, stackable from a swappable or PP-essential base, or is itself PP-essential. So storing only the half set and the PP set is sufficient to decompose any buildable shape.

Stackability check

A shape is stackable from a set of bases if it can be decomposed into a base (in the set) plus valid stack layer operations. The check iterates over all valid "height vectors" -- for each column, how many layers belong to the base vs. the stacked portion:

1. For each column, compute candidate split heights. The split must be above any crystal in the column, since stack layer can only place NORMALs and PINs. Only splits just above an occupied layer (or at height 0) are considered, since empty layers in between do not change the base
2. For each height vector, extract the base and the stacked portion
3. Verify the stacked portion is producible by stacking: every contiguous arc of NORMAL parts at a given layer must contain at least one anchor (a column with content directly below, or at layer 0). This is checked across all layers in parallel using bitwise flood-fill
4. Check whether the base is accepted by the is_base predicate (e.g., swappable, or already in the PP set)

Base halves

A base half is a half-shape that cannot itself be un-stacked into another half in the HalfSet. This is a subset of the full half set, but its stack + swap closure produces the same set of full shapes as the full half set. Using base halves as seeds avoids redundant work, since any non-base half can be reconstructed by stacking onto a base. The search starts from pairs of base halves.

Batch-based search

The search computes the pin push closure iteratively in batches. Each batch:

1. Generates seed full shapes from base-half pairs (swappable seeds) or PP shapes from prior batches
2. For each seed, enumerates the stacking closure: all shapes reachable by stacking pieces layer by layer (this is the implicit stack closure from the high-level idea)
3. For each shape in the closure, applies pin push and classifies the result

Layer-by-layer enumeration

To enumerate the stacking closure of a seed, the algorithm builds the shape layer by layer from the bottom up. At each layer, it tries all valid ways to add new parts. A valid addition is a set of connected normal parts and/or single pins that can physically land at that height -- each connected group of normal parts must touch at least one column that already has content in the layer below (an anchor), so the piece has something to rest on.

All valid additions for each layer are precomputed in a LayerTable indexed by which columns provide support and which are blocked (already occupied at or above this layer, so stacking cannot reach them). The enumeration recurses: at height h, look up valid additions, place each one, and recurse to h+1.

Fast pin push with crystal optimization

Pin push is applied to every shape in the stacking closure, so it must be fast. Four optimizations:

Precomputed shatter mask. When the seed has top-layer crystals, pin push shifts them beyond ML and they shatter. Since stacking only adds NORMALs and PINs (which don't affect crystal connectivity), the set of shattered crystals is the same for every shape in the closure. This is computed once and reused.

Support hints. Since stacking only adds content, the set of supported positions after gravity can only grow. The gravity result from a parent shape provides a lower bound on supported positions for its children, avoiding redundant computation.

Enumeration bound. The layer-by-layer enumeration only needs to go up to layer ML-2. Content stacked at layer ML-1 shifts to layer ML after pin push, which is beyond the maximum and gets truncated.

Closure pruning. Let X be the current shape at height h during the layer-by-layer enumeration (layers 0 through h-1 have been fixed), and let Y be any shape reachable from X by stacking additional pieces at height h or above. If pin_push(Y) is always in the stacking closure of pin_push(X), the remaining subtree can be skipped -- every pin_push(Y) is stackable from pin_push(X) and needs no separate classification. Three sufficient conditions guarantee pin_push(Y) = pin_push(X) + stacked pieces:

1. Base is preserved: pin_push(X) appears intact inside pin_push(Y). Condition: gravity causes no falling in pin_push(X). Since Y is a superset of X (stacking only adds content), the additional content can only provide more support, so no falling in X implies no falling in Y.
2. Extra parts are preserved: stacked pieces can only lose support if one of them rests directly on a shattering crystal. A stacked piece can only rest directly on a shattering crystal if that crystal is at the top of its column. Such a crystal must be at layer h-1 or above, because we no longer stack pieces at or below layer h-1. Crystals at layer ML-1 and ML-2 are also excluded: a crystal at ML-1 would require stacking at ML (does not exist), and a crystal at ML-2 would require stacking at ML-1 (truncated, never enumerated -- see enumeration bound above).
3. New pins are stackable: if Y has layer-0 content in a column that was empty in X (implying the whole column is empty in X, since stacking builds bottom-up), pin push inserts a new pin there. But that column is also empty in pin_push(X), so a pin can be stacked onto pin_push(X) at that position. This always holds.

The algorithm checks (1) and (2) jointly.

Classification

Each pin push result is classified into one of the three categories from the high-level idea:

1. Swappable (in cut/swap closure): if any orientation has both halves in the HalfSet, skip
2. Stackable (in stack closure): if decomposable into a known base (swappable or PP) plus stacking, skip. A direct-mapped cache avoids repeating expensive stackability checks
3. PP-essential: otherwise, insert into the PP set

Cleanup between batches

After each batch, any shape it just added is re-tested against the now-larger PP set and erased if a newly-discovered peer makes it stackable. Only the current batch is re-tested; earlier batches' entries are left alone even when later batches render some of them strictly redundant, because they may still appear on the recorded PP parent chain for later entries (see "Parent tracking" below). After the final batch, a dry-run pass reports how many "kept for parent chain" leftovers remain alongside the "true PP" count (final size minus leftovers). The retained shapes are not removed -- decomposition needs them -- so the raw in-memory PP count is true PP + kept, while the benchmark table's PP-essential column is just true PP.

Verification

After the search completes, the algorithm verifies that the half search is complete. Every buildable shape, when cut, must yield halves in the HalfSet. Since every buildable shape is swappable, stackable, or PP-essential, and Op 6 already covers swappable stacking closures, only PP-essential stacking closures need checking.

For each PP shape in all NC rotations, the algorithm enumerates the stacking closure using the same pruned enumeration strategy as Op 6 (east varies, west fills normals), cuts each shape, and checks that the east half is in the HalfSet. A failure indicates the half search missed a buildable half.

Parent tracking

A parallel array indexed by PP set slot stores the pre-push bits -- the raw CompactShape of the shape before pin push was applied. When multiple sources discover the same PP shape, the slot keeps the minimum value. The batch number is packed into the top 4 bits, so it dominates the comparison -- the selected parent always comes from the earliest possible batch. Since decomposition only uses bases from strictly earlier batches, cycles are impossible. This is sufficient to reconstruct the full decomposition during build plan generation.

6. Build Plan Decomposition

Goal: given a target shape, produce an operation tree that constructs it from single-layer inputs.

Node hierarchy

The build plan is a tree of these node types:

Node	Meaning
INPUT	Leaf: a static shape placed on a belt
ROTATE	Rotate child by N steps clockwise
CUT_EAST	Take the east half from cutting the child
SWAP	Combine east child's east half with west child's west half
STACK	Stack pieces onto a base
PIN_PUSH	Apply pin push to child
MIRROR	Pseudo-operation (not a game building); eliminated during simplification

Decomposition strategy

The decomposer tries three strategies in order:

Strategy 1 -- Swappable: try all NC/2 rotations of the target. If some rotation has both halves in the HalfSet, build each half recursively (see below), combine with a SWAP node, and wrap with ROTATE if needed.

Strategy 2 -- Stackable: check if the target is stackable from a swappable base or a PP shape (with batch number strictly less than the target's). If so, extract the base, identify the stacked layers as individual pieces, and create a STACK node with the recursively-decomposed base and the pieces as INPUT nodes.

Strategy 3 -- PP-essential: look up the target's canonical form in the PP parent table to find the pre-push shape. Try all NC rotations x 2 mirror orientations to find which one, after pin push, yields the target. Recursively decompose the pre-push shape and wrap with PIN_PUSH (plus ROTATE/MIRROR as needed). This does not loop: both Strategy 2 and 3 enforce strictly decreasing batch numbers, so recursion always terminates.

Half-node building

For a non-canonical half, build the canonical version and wrap with MIRROR(ROTATE(NC/2, ...)). Then recursively apply the half's recorded parent:

• SEED -> INPUT node
• PIN_PUSH -> PIN_PUSH(child)
• STACK_LAYER -> STACK(child, [piece])
• SWAP_CUT / SWAP_PIN_CUT / SWAP_STACK_CUT -> one unified branch recovers the two stored halves h1, h2 and searches the 2x2 half_sym orientation pairs x NC rotations for the combination whose cut-east equals target (or half_sym(target)). The tree for the winning combination is CUT_EAST(STACK?(ROTATE(r)?(PIN_PUSH?(SWAP(h1, ROTATE(NC/2, h2)))))) -- each optional wrapper enabled by the op tag (SWAP_PIN_CUT -> pin push, SWAP_STACK_CUT -> stack with the recorded pieces) or the winning rotation (r > 0 -> rotate). If the match was against half_sym(target), wrap the whole subtree with ROTATE(NC/2, MIRROR(...)) to bring it back on target.

Simplification

After construction, the tree is simplified by pushing operations inward toward the leaves:

• rotate(input(s)) -> input(rotate(s)) -- absorb into the leaf
• rotate(pin_push(x)) -> pin_push(rotate(x)) -- pin push commutes with rotation
• rotate(stack(base, pieces)) -> stack(rotate(base), rotate(pieces)) -- distribute
• rotate(m, rotate(n, x)) -> rotate(n+m, x) -- merge nested rotations
• mirror(mirror(x)) -> x -- double mirror cancels
• mirror(input(s)) -> input(mirror(s)) -- absorb into the leaf
• mirror(rotate(n, x)) -> rotate(NC-n, mirror(x)) -- swap order, adjust angle
• mirror(pin_push(x)) -> pin_push(mirror(x)) -- pin push commutes with mirror
• mirror(stack(base, pieces)) -> stack(mirror(base), mirror(pieces)) -- distribute
• mirror(swap(e, w)) -> swap(mirror(w), mirror(e)) -- mirror swaps east/west children
• mirror(cut_east(x)) -> rotate_180(cut_east(rotate_180(mirror(x)))) -- mirror changes which half is "east"
• Empty children are removed; nested stacks are flattened

After simplification, no MIRROR nodes remain -- they have all been pushed into INPUT leaves or eliminated by cancellation.

Color assignment

The CompactShape search discards shape types and colors. After decomposition, the assign_color pass restores them by working top-down through the tree. At each node, it needs to determine which type and color each child's parts should have so that, after applying the node's operation, the result matches the target.

To do this, each node assigns unique tracer IDs to its children's parts, then simulates the operation forward. By observing where each tracer ID ends up in the output, it builds a mapping from tracer IDs to the target's actual types and colors. This mapping is applied back to the children, and the process recurses into each child.

7. Data Structures

HierarchicalBitset (trie)

A variadic-template trie for storing sets of uint64_t values. Template parameters specify bits-per-level from MSB to LSB:

HierarchicalBitset<8, 8, 8, 8>  // 32-bit keys, 4 levels, fanout 256 each

Internal nodes are arrays of pointers to child nodes. Leaf nodes are arrays of atomic<uint64_t> words (bitset).

Concurrent insertion: leaf-level insertion uses atomic OR. Internal-level insertion uses compare-and-swap to install new child pointers.

Serialization: after the search completes (no more insertions), the trie is compacted into a CompactTrie binary format. Identical subtrees are deduplicated -- subtrees with the same content are stored only once and shared, significantly reducing size for sparse sets.

ConcurrentFlatSet (hash table)

An open-addressing hash table used for the PP-essential set. Backed by mmap(MAP_ANONYMOUS) for lazy zero-fill (no initialization loop for multi-GB allocations). Insertion is lock-free via compare-and-swap. Operates at ~50% load factor.

HalfSet (bitset)

A flat bitset indexed by compact half-key (up to 2^(NC*ML) entries). Membership test is O(1) -- a single bit lookup. Also maintains sorted vectors of all keys and canonical keys for iteration.