Skip links

How To Model A Rubik’s Cube in Algorand’s TEAL

Photo by Fletcher Pride on Unsplash

We’ve all played with one of these at some point in our lives. Maybe even managed to solve it or, failing that, tossed it aside in frustration. In any case, this colorful toy is a must-have household item.
But how does one model a Rubik’s Cube in code? Moreover, how could you implement this in Algorand’s TEAL stack-based Assembly-like blockchain language? Read on!

 

Abstracting ourselves from the code

 

Mathematical model

First of all, let’s think how we could represent a Rubik’s Cube model mathematically.
If we observe the puzzle, we can see there are 9 stickers on each face. If we take it apart, we can see that there are actually only 20 mobile pieces: 8 corner pieces and 12 edge pieces. They all revolve around a “core”, which holds the 6 center pieces fixed, only allowing them to rotate in place.

So what can we do? We could use a sticker-based representation of the cube, recording how each side of the cube is colored at a given moment, or a piece-based representation, taking account of where each piece is located.
We are going to use a piece-based representation for this example, since the effect a single move has on the cube is a bit simpler to describe like that.

 

For the record, a sticker-based representation is usually a better idea if you’re doing some visual representation of the cube state

In order to do this, we have to keep track of where each piece is, and “how they are rotated” in place.
From now on, we are going to refer to “where each piece is” as the permutation, and “how they are rotated” as the orientation (we will cover the latter in depth later on).

 

Pseudocode model

In pseudocode, one could sketch the following:

 

piece {
   name: string,
   orientation: int
}

corners: [piece; 8] //  8 elements
edges: [piece; 12]  // 12 elements

Edges have two sides, therefore only two possible orientations. Corners have three sides, therefore only three possible orientations.
We need to make a distinction using the orientation, since a given piece could be in the exact same spot (for example, an edge between the red-blue centers) but rotated differently (flipped, in the case of an edge). The color configuration would be a totally different one.

Then, the position of the pieces in the array simply tells us everything we need to know. We just need to define an arbitrary order in which we are going to label each piece, and we’re good!

For example, if our original corner state is:

 

[A, B, C, D, E, F, G, H]

And A, B, C, D reference the four corners on the top face, then applying a 90 degree turn on this face may give us the following state afterwards:

 

[B, C, D, A, E, F, G, H]

The same idea applies for edges.

Hold up, so what about centers? In this representation we are not taking into account rotations of the entire Rubik’s Cube, just face moves. Since no face move changes the placement of a center piece, we need not worry about them at all!

Now that we understand the basic idea behind this model, let’s try diving into the code.

 

Implementation in TEAL

 

So what about TEAL?

TEAL is not a language devised to do this kind of stuff. It doesn’t even have variables, functions, or data types as we know them in most programming languages. All it knows is how to check Algorand transaction fields, and approve or reject them based on a certain logic. It is like a blockchain, stack-based version of Assembly.
So how on Earth are we going to do this?

Luckily for us, TEAL can do a bunch of other things. We don’t have variables, but we have the scratch space, and the global state for Apps. We don’t have arrays or objects, but we can make do with a byte array. So why are we complaining? Let’s get to this.

 

 

This implementation is done on a Stateless TEAL contract, therefore nothing can be stored before or after a transaction is processed (no global state). You could as easily implement the same logic on a Stateful App and store cube state in global state, allowing it to persist.

 

Defining the pieces

First, let us store the permutation and orientation or each piece type (corners and edges) separately. This means we could initialize the cube on a solved state as follows:

 

// Edge Permutation (stored in slot 0)
pushbytes "abcdefghijkl"
store 0
// Corner Permutation (stored in slot 1)
pushbytes "abcdefgh"
store 1
// Edge Orientation (stored in slot 2)
pushbytes 0x020202020202020202020202 // 12 bytes
store 2
// Corner Orientation (stored in slot 3)
pushbytes 0x0303030303030303 // 8 bytes
store 3

We can access individual bytes of a byte array in TEAL easily, so storing bytes with a value of "abcdefgh" or 0x0303030303030303 is essentially the same as having an array of 8 elements. Perfect!

 

Notice, the hex constant 0x0303030303030303 and the string "abcdefgh" are the same type: byte[] (out of the two possible types in TEAL, byte[] and uint64). TEAL lets us use both string and hex representation.
Also, why are they initialized in all 03’s and all 02’s? The answer is TEAL trims byte arrays that start with 0x00 bytes after some operations that we’ll be doing, therefore changing their length which is undesired behavior. Initializing them like this prevents this from happening.
The numbers 3 and 2 correspond to them being 0 mod N, with N = number of possible orientations for that piece type. If this sounds a bit odd right now, read on, and hopefully it will make more sense towards the end.

 

Permutation utils in TEAL

 

The atoms

Now, we will have to define the actual moves (face turns). That means, which pieces a single face turn affects and how it changes the orientation and permutation of those pieces.

To do that, we will define some helper subroutines that will ease our work later. (Remember, no functions in TEAL!)
Since every face turn cycles 4 corners and 4 edges, we could generalize this as a subroutine that rotates four bytes of a byte array, using the stack to “pass arguments” to it. Let’s do that:

 

swapbytes:
    // pops: ...stack, X, Y, b
    // b[X], b[Y] = b[Y], b[X]
    // pushes: ...stack, b'
    dup
    dig 2
    getbyte
    swap
    dup
    dig 4
    getbyte
    uncover 3
    swap
    setbyte
    cover 2
    setbyte
    retsub

rotatebytes:
    // pops: ...stack, A, B, C, D, b
    // b[A], b[B], b[C], b[D] = b[D], b[A], b[B], b[C]
    // pushes: ...stack, b'''

    // Swap last two
    dig 2       // A B C D b C
    cover 2     // A B C C D b
    callsub swapbytes // WXYZ -> WXZY (A B C b')
    // Swap mid two
    dig 2       // A B C b' B
    cover 2     // A B B C b'
    callsub swapbytes // WXZY -> WZXS (A B b'')
    // Swap first two
    callsub swapbytes // WZXY -> ZWXY (b''')
    retsub

 

I understand it is not the easiest code to read. If you care about deeply understanding it, I suggest that you try to simulate a stack (using pencil and paper, or a text editor), and go line by line seeing how it is affecting the elements in it. Otherwise, use tealdbg. Read the TEAL opcodes documentation, and be patient!

 

Using the atoms

Sweet! The hardest work is probably done. Now, we can define functions that use the rotatebytes subroutine to affect our pieces. Let’s go ahead and define subroutines to permute both piece types:

 

permute_e:
    // pops: ...stack, A, B, C, D
    // cycles edges A->B->C->D (EP and EO)
    // pushes: ...stack
    dig 3
    dig 3
    dig 3
    dig 3
    load 0
    callsub rotatebytes
    store 0
    load 2
    callsub rotatebytes
    store 2
    retsub

permute_c:
    // pops: ...stack, A, B, C, D
    // cycles corners A->B->C->D (CP and CO)
    // pushes: ...stack
    dig 3
    dig 3
    dig 3
    dig 3
    load 1
    callsub rotatebytes
    store 1
    load 3
    callsub rotatebytes
    store 3
    retsub

As you can see, these two subroutines are almost identical but for the fact that they load a byte array from a different slot in scratch space. This could have been “simplified” by having a single permute_pieces subroutine that receives the piece type as an argument from the stack, but this would imply extra opcodes that in the end make the execution more costly; and this is quite limited in TEAL, so we better save on opcode cost.

We need to apply the same transformation to both the permutation and orientation array, since the two are related to each other strictly by the position of their elements. If we don’t permutate the elements of the orientation array, we would lose the reference of which piece’s orientation we’re describing.

 

Orientation utils in TEAL

Good! But we’re missing something. We need to be able to edit the orientation arrays on their own as well. Right now, we’re only moving pieces around, but no change is being made to the orientation whatsoever. Fortunately, these routines are easier. But we need to recap some Rubik’s Cube theory first.

 

Brief recap of Rubik’s Cube theory

Understanding how the orientation is defined is crucial to construct a correct Rubik’s Cube model.

Let’s say we define 0 as the orientation value of a corner with the Up/Down color facing Up/Down, 1 as it with a clockwise rotation from state 0, and 2 as it with a clockwise rotation from state 1.

This is arbitrary, we could have used another two parallel faces for reference, or considered rotations in the opposite way.

 

Picture showing 0, 1, and 2 orientation states visually

Then, our orientation array would contain this 0,1,2 value for each corner, based on their position. For example, 0x0101010102020202 would mean that our first 4 corners are rotated clockwise, whereas our other 4 corners are rotated counter-clockwise.

Defining orientation is slightly harder for edges. Edges also have an orientation relative to the axis we pick; this means, we can choose to keep track of it relative to the axis orthogonal to the Up/Down faces, Left/Right faces, or Front/Back faces. The three will give different (but equivalent) results, and using only one suffices.
Let’s pick Front/Back this time (doesn’t have to be the same one as for corners). The rules are:

 

  • Every edge has an orientation value of 0 initially
  • A 90 or -90 degree turn of the Front or Back face changes the orientation of the 4 edges in it (0 becomes 1, 1 becomes 0)
  • Every other move doesn’t change the orientation of any edge

Now you can probably see why we were considering stuff to be mod 3 and mod 2 earlier.
For example, for edges, it is easier to just add 1 to the current value, and take mod 2 to bring it into [0,1]. Hopefully it makes sense now.

 

Diving into the code

Alright! We now know what to do. Every move affects edge and corner orientation in some way, so it would be a good idea to make some subroutines to help us with it. Fortunately, these are way easier than the permutation ones:

 

orient_e:
    // pops: ...stack, m
    // applies orientation mask to EO byte array (mod2 at check)
    // pushes: ...stack
    load 2
    b+
    store 2
    retsub

orient_c:
    // pops: ...stack, m
    // applies orientation mask to CO byte array (mod3 at check)
    // pushes: ...stack
    btoi // to save opcode cost
    load 3
    btoi
    +
    itob
    store 3
    retsub

 

Notice the slight hack of temporarily converting the byte[] corner orientation array to an uint64. This lets us use the + opcode instead of b+, which has a cost of 10 instead of just 1. Even with the btoi/itob calls, this still saves us 6 units. Of course, we can’t use this on the edge orientation array since it doesn’t fit in a uint64.

This should make sense. From what we just learnt, an “orientation mask” for a move of the Front face could be 0x 00 00 01 00 00 00 01 01 01 00 00 00, if the 3rd, 7th, 8th, and 9th elements represented the 4 edges on that face. Applying that mask would simply toggle the orientation of those pieces, since we are considering these values to be mod 2.
The same idea applies for corners, just mod 3.

Phew! Now finally, all the hard work is done. The rest will be piece of cake.

 

Putting it all together!

We have all the helper code. Now, let us actually define the moves and how they affect our cube!

As an easy example, we will start with a clockwise 90 degree turn of the Up face, which we will call just U.
This affects the permutation of corners 0, 1, 2, and 3 in my labelling scheme, and edges 0, 1, 2, and 3.
Orientation of the corners remains unaffected (since U is our reference face), and so is the orientation of the edges since we are not turning the Front or Back face. Easy, right? I agree.

 

_U:
    // CP
    int 0
    int 1
    int 2
    int 3
    callsub permute_c
    // EP
    int 0
    int 1
    int 2
    int 3
    callsub permute_e
    retsub

That is all we need for this face!

Let’s do one more together to make sure we’re getting this right. Let’s go with a clockwise 90 degree turn of the Front face (F face).
This affects the permutation of corners 3, 2, 5 and 4 in my scheme, and edges 2, 6, 8 and 7.
This time, we have a change in orientation. It turns out that a single turn of F changes the orientation of corners in a way that can be described as 0x0000010201020000, and edges as 0x000001000000010101000000. You can check this by grabbing a cube and applying a turn to the Front face, and seeing where the Up/Down stickers of the affected corners end up.

Don’t worry if you don’t exactly see that particular bit. Just keep in mind that we are describing the effect that move has on the orientation of our pieces using an orientation mask, and that is all we need. This is the code:

 

_F:
    // CP
    int 3
    int 2
    int 5
    int 4
    callsub permute_c
    // EP
    int 2
    int 6
    int 8
    int 7
    callsub permute_e
    // CO
    pushbytes 0x0000010201020000
    callsub orient_c
    // EO
    pushbytes 0x000001000000010101000000
    callsub orient_e
    retsub

All good! The rest will just be defining every other move in the same fashion.

 

Notice that we don’t really need to define both clockwise and counter-clockwise turns, since a counter-clockwise turn is simply a clockwise turn applied three times, and the same happens with 180 degree turns (clockwise 90 degrees, twice). In any case, we will define counter-clockwise turns as if they were a different face turn, since applying a clockwise turn three times is just too costly.

I will not post the entire code for that here since it is too long and repetitive, but you can check it out over here: TEAL Rubik’s Cube model source code.

 

Checking solved state

Superb! Just one last step now. It would come in handy to have subroutines that check if the cube is solved or not.

This is super simple for most of the arrays: just check if their value is the initial value for the permutation ones, and check if everything is 0 mod 2 for the edge orientation one.
The only hard one is the corner orientation array, since applying mod 3 to every byte individually is not as direct as applying mod 2. In any case, this is how you do it:

 

is_solved:
    // pops: ...stack
    // Pushes a 1 if cube is solved
    // pushes: ...stack, 0|1
    // Check EP
    load 0
    pushbytes "abcdefghijkl"
    ==
    // Check CP
    load 1
    pushbytes "abcdefgh"
    ==
    &&
    // Check EO (item-wise mod2)
    load 2
    pushbytes 0x010101010101010101010101
    b&
    pushbytes 0x000000000000000000000000
    ==
    &&
    // Check CO (item-wise mod3)
    load 3
    callsub check_co
    &&
    retsub

check_co:
    // pops: ...stack, co
    // Checks if co byte[] is solved (all bytes are 0 mod 3)
    // pushes: ...stack, 1|0
    // Copy thing to scratch space to save opcodes
    dup
    store 20
    // Check that every byte mod 3 = 0
    int 0
    getbyte
    int 3
    %
    load 20
    int 1
    getbyte
    int 3
    %
    load 20
    int 2
    getbyte
    int 3
    %
    load 20
    int 3
    getbyte
    int 3
    %
    load 20
    int 4
    getbyte
    int 3
    %
    load 20
    int 5
    getbyte
    int 3
    %
    load 20
    int 6
    getbyte
    int 3
    %
    load 20
    int 7
    getbyte
    int 3
    %
    // We should have eight 8s on the stack, therefore seven ||s should yield a 0
    ||
    ||
    ||
    ||
    ||
    ||
    ||
    ! // If we got 0 it's all good, negate it so that we return 1
    retsub

Perhaps not the prettiest code, but when it comes to opcode cost efficiency this is as good as I could get it on a few tries.

And with that, we are done!

 

Final thoughts

You may have noticed that we are not applying the moves anywhere, we just defined them. Since this is an Algorand Stateless TEAL contract, we cannot make AppCalls to it, so the only way to test this is by hardcoding a test move set, such as:

 

// ... init

callsub _Rp
callsub _Up
callsub _F
callsub _Dp
callsub _Bp
// ... etc

callsub is_solved
return

// ... snip

This scenario changes if we deploy this as a Stateful App. We could even store a “scramble” in global state, and only approve transactions that solve it.

How we call these moves is out of the scope of this post. Should we input them as a single string and parse it in the contract’s code? Should we send individual transactions for every single move? There are many possible options. Here we just thoroughly described the data structure needed to represent a Rubik’s Cube model, and how to use it.

Hope you enjoyed the read!

 

This website uses cookies to improve your web experience.