This is an algorithmic challenge from the factory game Shapez2, essential for building what's known as a TMAM (True Make Anything Machine).
I’ve been researching this problem over the past month. While I’ve managed to solve most of Problem 1, I’m still struggling with certain edge cases.
These difficulties stem from emergent complexity — simple rules giving rise to complex and unpredictable behaviors, similar to Conway’s Game of Life.
Below, I’ve outlined the problem description and provided some examples.
I’d greatly appreciate any insights, suggestions, or approaches from those who may have a deeper understanding of this problem.
(Note: The problems are well-known within the Shapez2 community.
At least 100,000 players have indirectly encountered them,
but only around five people are known to have solved an unoptimized version of Problem 2.
Problem 3 remains without a complete solution.)
Shapez2 Shape Crafting Optimization Problem
Problem Overview
The problem is about creating a factory to produce complex shapes.
Shapes are composed of multiple layers, and each layer is divided into four quadrants. We aim to create a target shape by combining a few predefined types of pieces.
There are basic rules for building shapes and a set of available operations. The challenge is to use these to create the target shape with the minimum number of operations.
The starting shape is a single layer completely filled with four S pieces, represented as "SSSS".
Any shape, once created, can be reused an infinite number of times.
1. Shape Structure
Shapes can have a maximum of 5 layers.
Each layer is divided into 4 quadrants with circular connectivity.
The quadrant numbers are as follows:
[4 (TL)] [1 (TR)]
[3 (BL)] [2 (BR)]
Therefore, a single shape is represented by a 5x4 grid.
2. Piece Types
The pieces that make up a shape are as follows:
Symbol Description
S Solid piece
P Pin piece
c Crystal piece
- Empty space
SSSS, PPPP, cccc, ----
3. Shape Representation
Shapes are represented as strings.
Each layer is a 4-character string, representing the pieces in quadrants 1(TR), 2(BR), 3(BL), and 4(TL) respectively.
Multiple layers are separated by a colon (:).
For example:
S--- → A shape with one layer, having an S piece in quadrant 1 and empty spaces elsewhere.
-S--:----:---S → An S piece in quadrant 2 of layer 1, and an S piece in quadrant 4 of layer 3.
Trailing empty layers (e.g., :----) can be omitted.
An empty shape is represented as ----, not null.
4. Physics Rules
Pieces must be stacked in a stable manner, following these rules.
4.1 Connectivity
S pieces are connected only to adjacent pieces (up, down, left, right) within the same layer.
e.g., All connected: SS--, S--S (Quadrant 1 and Quadrant 4 are circularly connected).
c pieces are connected to adjacent pieces within the same layer, as well as to pieces in the same quadrant on the layers directly above and below.
Crystals (c) have strong connectivity but are fragile.
If a crystal is destroyed in any way, all other crystals connected to it are also destroyed simultaneously.
This chain reaction of destruction only propagates through c-to-c connections, not through S connections.
e.g., All connected: -c--:ccc-:-c--
S pieces and c pieces are connected only to adjacent pieces within the same layer.
e.g., Connected only on layer 2: -S---:ScS-
P pieces have no connectivity.
4.2 Support Conditions
Pieces on Layer 1 are always supported.
e.g., S---
A piece on an upper layer is supported if there is a piece directly below it in the same quadrant.
e.g., Supported: S---:S---, Not supported: S---:-S--
A piece can be supported if it is connected to an already supported S piece on the same layer.
e.g., Supported: S---:SS--
If at least one piece within a connected group is supported, the entire group is considered supported.
e.g., Supported: S---:SS--:-S--
4.3 Gravity and Unstable Pieces
All unsupported shapes fall down to the lowest possible level.
Unsupported S and P pieces fall as a group.
e.g., Case 1: S---:S---:-S--:-S-- → SS--:SS--.
The pieces from layers 3 and 4 do not connect to the pieces on layer 2 as they fall.
e.g., Case 2: S---:P---:----:SPSS → SP--:P---:S-SS
Crystal pieces (c) are fragile.
If a c piece moves due to gravity or is separated by a cut, that c piece and its entire connected group of c pieces are destroyed.
e.g., Case 1: ----:--cc:--Sc → --S-
e.g., Case 2: cccc:----:cccc → cccc (The two crystal groups are separate).
This process repeats until the shape stabilizes.
5. Operations
Shapes can only be processed using the following six operations.
5.1 Rotate
rotate(A: shape) -> shape
Rotates the shape 90 degrees clockwise.
Quadrant numbers change as follows: [1,2,3,4] → [4,1,2,3].
Example:
rotate(PP--:-SS-) -> -PP-:--SS
5.2 Stack
stack(A: shape, B: shape) -> shape
Stacks shape B on top of shape A.
All c pieces in shape B are destroyed due to the impact of stacking (as if affected by gravity).
If the combined shape exceeds 5 layers, the top layers are removed.
Physics rules are then applied.
Examples:
stack(SSSS:SS--, --SS:SSSS) -> SSSS:SSSS:SSSS
stack(cSSc, cccS) -> cSSc:---S (Crystals are destroyed)
stack(SSSS:SSSS:SSSS, SSSS:SSSS:SSSS) -> SSSS:SSSS:SSSS:SSSS:SSSS (Excess layers removed)
stack(-SSS:-SSS:-SSS:-SSS:-SSS, PPPP:SSSS) -> PSSS:-SSS:-SSS:-SSS:-SSS (Application: Creating a layer with only pins)
5.3 Destroy Half
destroy_half(A: shape) -> shape
Cuts the shape vertically in half, through all layers.
The left half of the shape (quadrants 4(TL) and 3(BL)) is destroyed.
Only the right half (quadrants 1(TR) and 2(BR)) remains.
Physics rules are then applied.
Examples:
destroy_half(SSSS:SSSS) -> SS--:SS--
destroy_half(ScSc:ccSS) -> Sc--:cc--
destroy_half(ccSS:SccS) -> S--- (Crystal chain reaction destruction)
destroy_half(PPPP:cccc) -> PP-- (Application: Creating a layer with only pins)
destroy_half(cSSc:SSSS:cSSS) -> -S--:SS--:cS-- (Application: Creating *Sc- with a space below the crystal in Q1)
destroy_half(S-S-:PSS-:ScS-) -> SS--:P---:Sc-- (Application: Creating *-cS with a space below the crystal in Q2 and shape drop)
*User-defined pattern names.
5.4 Swap
swap(A: shape, B: shape) -> (shape, shape)
Cuts both shapes in half (left/right), and applies physics to the resulting four half-shapes.
Creates a new shape by combining the right half of A with the left half of B. Creates another new shape with the remaining halves.
Physics rules are applied to each of the two new shapes.
Examples:
swap(SSSS:SSSS, PPPP) -> (SSPP:SS--, PPSS:--SS)
swap(P---:S--S, P---:S--S) -> (P--S:S---, P--S:S---) (Gravity is applied)
swap(SS--, --SS) -> (SSSS, ----)
swap(cc--:S--S, c--c:S--S) -> (cc-S:S---, S--S) (Crystals destroyed due to separation)
5.5 Pin Push
pin_push(A: shape) -> shape
Lifts the entire shape up by one layer.
Adds a P piece to the new 1st layer in every quadrant that contained a piece in the original shape's 1st layer.
If the shape now exceeds 5 layers, the top layer is destroyed.
Physics rules are then applied.
Examples:
pin_push(SSSS) -> PPPP:SSSS
pin_push(-SPc:SSSS) -> -PPP:SPc:SSSS
pin_push(Sc--:SSSS:cccc:c---:c---) -> PP--:Sc--:SSSS (Crystal chain reaction from exceeding layer limit)
pin_push(ccP-:cSP-:cSS-:c---:c---) -> PPP-:-SP-:--P-:-SS- (Separation principle)
pin_push(cc--:cP--:cP--:cP--:cS--) -> PP--:-P--:-P--:-P-- (Shape destruction principle)
pin_push(ccc-:c-S-:c-c-:c---:c---) -> PPP-:--S- (Secondary crystal destruction)
pin_push(cccc:cccc:cccc:cccc:cccc) -> PPPP (Application: Pin layer creation)
pin_push(c-P-:cScS:c---:c---:c---) -> P-P-:--P-:-ScS (Application: Claw* creation)
pin_push(cccP:SPcS:cSc-:--c-:--c-) -> PPPP:-P-P:S--S:cS-- (Application: Pin Gate* creation)
pin_push(ccSP:SccS:PScc:ScSc:---c) -> PPPP:-SSP:S--S:P---:ScS- (Application: Shape Gate* creation)
pin_push(S-Sc:PScc:S-Sc:ScSc:---c) -> PSPP:S-S-:P-S-:S---:ScS- (Application: Drop + Gate* creation)
*User-defined pattern names.
5.6 Crystal Generator
crystal_generator(A: shape) -> shape
Identifies the topmost layer of the shape.
Fills all empty spaces (-) and P pieces with c pieces, from layer 1 up to that topmost layer.
Examples:
crystal_generator(SSSS) -> SSSS
crystal_generator(P-S-:SP--) -> ccSc:Sccc
crystal_generator(SPc-) -> Sccc
6. Game Rules
The starting shape is a single layer completely filled with four S pieces, represented as "SSSS".
Any shape, once created, can be reused an infinite number of times.
7. The Problems
Problem 1. Shape Craftability
is_craftable(target: str) -> bool
Given a random shape as a string input, determine if it can be created using only the starting shape and the operations above.
Examples:
"SSSS" -> True
"----" -> True
"PPPP:SSSS:cccc" -> True
"----:SSSS" -> False
"S---:SSSS" -> True
"cPSP:ScSP" -> True
"S---:cccc" -> False
"-S--:PS--" -> False
Advanced Examples:
"cS--:-S--:cS--" -> False
"cS--:-S--:SS--:cS" -> False
"-S--:SS--:cS--" -> True
"SS--:-S--:cS--" -> True
"-S--:SS--:-S--:cS--" -> True
"PS--:-S--:SS--:-S--:cS--" -> True
"SS--:-S--:SS--:-S--:cS--" -> True
"P-PP:SSSS:P--P:PcS-:ScSS" -> True
"P-P-:--P-:-ScS" -> True
"-S--:-S--:-SS-:SScS" -> True
"PP--:PS--:S-SS:P---:ScS-" -> False
Problem 2. Optimal Crafting Sequence (Challenge)
craft_sequence(target: str) -> List[str]
Given a random, craftable shape as a string input, return the sequence of operations with the minimum number of steps to create it.
The output format for shapes must follow the specified string representation. There may be multiple correct solutions.
Example Input: "SS--:SS--"
Example Output:
[
"stack(SSSS, SSSS) -> SSSS:SSSS",
"destroy_half(SSSS:SSSS) -> SS--:SS--"
]
Example Input: "cc--:cc--"
Example Output:
[
"stack(SSSS, SSSS) -> SSSS:SSSS",
"destroy_half(SSSS:SSSS) -> SS--:SS--",
"crystal_generator(--SS:--SS) -> SScc:SScc",
"rotate(ccSS:ccSS) - > SccS:SccS",
"rotate(SccS:SccS) - > ccSS:ccSS",
"destroy_half(SScc:SScc) -> cc--:cc--"
]
Example Input: "-c--:-P--"
Example Output:
[
"destroy_half(SSSS) -> SS--",
"rotate(SS--) -> -SS-",
"destroy_half(-SS-) -> -S--",
"rotate(-SS-) -> --SS",
"stack(--SS, -S--) -> -SSS",
"crystal_generator(-SSS) -> cSSS",
"destroy_half(cSSS) -> cS--",
"rotate(cS--) -> -cS-",
"destroy_half(-cS-) -> -c--",
"stack(-SSS, -SSS) -> -SSS:-SSS",
"stack(-SSS:-SSS, -SSS:-SSS) -> -SSS:-SSS:-SSS:-SSS",
"stack(-SSS:-SSS:-SSS:-SSS, -SSS) -> -SSS:-SSS:-SSS:-SSS:-SSS",
"pin_push(SSSS) -> PPPP:SSSS",
"stack(-SSS:-SSS:-SSS:-SSS:-SSS, PPPP:SSSS) -> PSSS:-SSS:-SSS:-SSS:-SSS",
"destroy_half(PSSS:-SSS:-SSS:-SSS:-SSS) -> PS--:-S--:-S--:-S--:-S--",
"rotate(PS--:-S--:-S--:-S--:-S--) -> -PS-:--S-:--S-:--S-:--S-",
"destroy_half(-PS-:--S-:--S-:--S-:--S-) -> -P--",
"stack(-c--, -P--) -> -c--:-P--"
]
Problem 3. Generalization (Challenge)
Generalize the solutions for Problems 1 and 2 to work not just for a 5-layer, 4-quadrant structure, but for an n-layer, m-quadrant structure (where 0 < n <= 20, 0 < m <= 20).
8. Notes
All rules and operations are based on the game Shapez2. If there is a logical conflict, the rules of the original game take precedence.
(I've removed the detailed shape classification and colours from the actual problem and simply redefined the core)
If an input to an operation is a completely empty shape (----), the operation does nothing.
All optimization techniques, such as caching and lookup tables, are permitted.
The answers to this problem are not yet fully established.
What I’ve Tried
I have fully implemented all six operations and the physics engine, with automated testing to ensure correctness.
I also implemented reverse operations for each transformation, but the search space quickly became intractable, making this approach impractical.
It seems the core challenge lies in designing effective pruning and heuristics, but the abundance of edge cases makes it very difficult to build intuitive rules.
For example, patterns like the “Claw” — which requires crystal-breaking via pin_push and cannot be handled via swap — and the “Hybrid,” which requires stack, are among the most complex patterns I’ve encountered so far.
{P-PP:SSSS:P--P:PcS-:ScSS}
I've added unusual patterns like this as examples, which is why the list of examples is so long.
In terms of shape composition, although the theoretical number of shape combinations is 4^5^4, I analyzed that when only considering one corner, there are 1024 possibilities — of which exactly 478 are actually valid.
Among them, there are 48 specific edge cases where there is an empty space somewhere below a corner piece (c).
Example: -:S:c, S:-:c, -:S:-:c, S:-:S:-:c, P:-:S:-:c
These corner configurations are a key factor contributing to the overall complexity of the problem.
I’ve defined five specific rules that apply only to corners that work correctly up to the 5th floor.
It has been confirmed that as the number of floors increases, additional rules must be added to maintain correctness.
