I've decided to post another answer. My first answer was very straightforward, but not entirely in the spirit of the question. I think I have a better answer now, after thinking about it for a while.
TL;DR The following code rotates a polycube through all 24 rotations of the cube. It does so with no matrix multiplications, instead using a 3x3x3x3x3 index table which gives a few key rotations of the indices in the polycube, and a length-23 Gray code for the rotation group of the cube. It has only six real lines of code, almost all of which are for loops. It is extremely fast, and fairly compact (except for the index table, which could be generated by the program (see below)).
import numpy as np
# polycube that we want to rotate
A = np.array([[['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', 'i']],
[['j', 'k', 'l'],
['m', '+', 'n'],
['o', 'p', 'q']],
[['r', 's', 't'],
['u', 'v', 'w'],
['x', 'y', 'z']]])
# I just do np.copy here because I don't know how to declare an array
T = np.copy(A)
Idx=np.array([
[[[[2,0,0], [2,1,0], [2,2,0]],
[[2,0,1], [2,1,1], [2,2,1]],
[[2,0,2], [2,1,2], [2,2,2]]],
[[[1,0,0], [1,1,0], [1,2,0]],
[[1,0,1], [1,1,1], [1,2,1]],
[[1,0,2], [1,1,2], [1,2,2]]],
[[[0,0,0], [0,1,0], [0,2,0]],
[[0,0,1], [0,1,1], [0,2,1]],
[[0,0,2], [0,1,2], [0,2,2]]]],
[[[[0,2,0], [1,2,0], [2,2,0]],
[[0,1,0], [1,1,0], [2,1,0]],
[[0,0,0], [1,0,0], [2,0,0]]],
[[[0,2,1], [1,2,1], [2,2,1]],
[[0,1,1], [1,1,1], [2,1,1]],
[[0,0,1], [1,0,1], [2,0,1]]],
[[[0,2,2], [1,2,2], [2,2,2]],
[[0,1,2], [1,1,2], [2,1,2]],
[[0,0,2], [1,0,2], [2,0,2]]]],
[[[[2,2,2], [2,1,2], [2,0,2]],
[[2,2,1], [2,1,1], [2,0,1]],
[[2,2,0], [2,1,0], [2,0,0]]],
[[[1,2,2], [1,1,2], [1,0,2]],
[[1,2,1], [1,1,1], [1,0,1]],
[[1,2,0], [1,1,0], [1,0,0]]],
[[[0,2,2], [0,1,2], [0,0,2]],
[[0,2,1], [0,1,1], [0,0,1]],
[[0,2,0], [0,1,0], [0,0,0]]]]
])
# Gray code gives Hamiltonican circuit through cube rotation group
gray = [3,2,1,2,1,2,3,2,3,2,1,2,1,2,3,2,3,2,1,2,1,2,3]
# Oops, index starting at 0
gray[:] = [x-1 for x in gray]
print(A)
# I'm sure there must be a more efficient way to move T (temp) into A
for g in gray:
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
T[i,j,k] = A[Idx[g,i,j,k,0],Idx[g,i,j,k,1],Idx[g,i,j,k,2]]
A = np.copy(T)
print("-----------------")
print(A)
My solution is to find a Gray code for the rotation group of the cube.
First, we must find a nice representation for the rotation group you are using. Consider a 2x2x2 cube with 1x1x1 cubies labeled in the following manner:
1 2
3 4 4 3
2 1
We number starting at 1 to be consistent with the mathematics literature. The upper left square is meant to be the front face, and the lower right square the rear face. Imagine the 1 connected by edges to the 2 and 3 in the front face, and to the 4 in the rear face, etc.
Note that diagonally opposite cubies have the same number. Now any rotation of the cube corresponds to a permutation of the four numbers on the front face. Furthermore, any permutation of the numbers on the front face corresponds to a rotation. The four rotations in the z-axis coming out of the page are
1 2 3 1 4 3 2 4
3 4 4 3 4 2 2 4 2 1 1 2 1 3 3 1
2 1 1 3 3 4 4 2
We can label the rotations by the effect on the front face. They are 1234, 3142, 4321, and 2413.
Three additional rotations about the x-axis (plus the identity rotation, with which we start) are
1 2 3 4 2 1 4 3
3 4 4 3 2 1 1 2 4 3 3 4 1 2 2 1
2 1 4 3 1 2 3 4
In our more compact notation, the additional rotations are 3421, 2143, and 4312.
Three additional rotations about the y-axis are
1 2 2 3 3 4 4 1
3 4 4 3 4 1 1 4 1 2 2 1 2 3 3 2
2 1 3 2 4 3 1 4
In compact notation, the three additional rotations are 2341, 3412, and 4123.
There are three rotations, including the identity, that fix the 1's diagonal:
1 2 1 4 1 3
3 4 4 3 2 3 3 2 4 2 2 4
2 1 4 1 3 1
with the new ones labeled 1423 and 1342.
There are three rotations, including the identity, that fix the 2's diagonal:
1 2 4 2 3 2
3 4 4 3 1 3 3 1 4 1 1 4
2 1 2 4 2 3
with the new ones labeled 4213 and 3241.
There are three rotations, including the identity, that fix the 3's diagonal:
1 2 2 4 4 1
3 4 4 3 3 1 1 3 3 2 2 3
2 1 4 2 1 4
with the new ones labeled 2431 and 4132.
There are three rotations, including the identity, that fix the 4's diagonal:
1 2 2 3 3 1
3 4 4 3 1 4 4 1 2 4 4 2
2 1 3 2 1 3
with the new ones labeled 2314 and 3124.
Finally, there are six edge flips plus the identity. The flips in the 1-2 edge are
1 2 2 1
3 4 4 3 3 4 4 3
2 1 1 2
with the new one represented by 2134. Similarly there are edge flips in edges 1-3 (3214), 1-4 (4231), 2-3 (1324), 2-4 (1432), and 3-4 (1243).
Each of the 24 rotations corresponds to a distinct permutation of 1234, and since there are 24 permutations and 24 rotations, each distinct permutation corresponds to a rotation. We say that the rotation group of the cube, and the group S_4 of permutations of 1234, are isomorphic. (One way to think of this is that rotations of a cube have the action of permuting the diagonals of the cube, and the correspondence is 1-1.)
We could figure out the effect of each of the 24 rotations on your arrays, but that is tedious and error-prone. Instead, we will see that the rotation group is generated by just three rotations, the edge flips
R1=transpose numbers in position2 1 and 2, and leave numbers in positions 3 and 4 alone
R2=transpose numbers in positions 2 and 3, and leave numbers in positions 1 and 4 alone
R3=transpose numbers in positions 3 and 4, and leave numbers in positions 1 and 2 alone
and their compositions. We'll throw in
R0=identity operation
for completeness. Using just those three generators, we can find a Hamiltonian circuit through the Cayley graph of the rotation group:
01 1234 apply R0 to starting position, i.e., do nothing
02 1243 apply R3 to previous
03 1423 apply R2 to previous
04 4123 R1
05 4213 R2
06 2413 R1
07 2143 R2
08 2134 R3
09 2314 R2
10 2341 R3
11 2431 R2
12 4231 R1
13 4321 R2
14 3421 R1
15 3241 R2
16 3214 R3
17 3124 R2
18 3142 R3
19 3412 R2
20 4312 R1
21 4132 R2
22 1432 R1
23 1342 R2
24 1324 R3
Note that each permutation (i.e., rotation of the cube) appears in this list exactly once, and that moving from one item in the list to the next is accomplished by a transposition of items in positions 1-2, 2-3, or 3-4, which corresponds to the edge flip rotations R1, R2, and R3. This Gray code for S_4 (and much else, which is unfortunately rather difficult to understand if you don't know about reflection groups and Coxeter diagrams) is presented in the famous paper Gray Codes for Reflection Groups by Conway, Sloane, and Wilks.
The Gray code is summarized by this sequence of 23 numbers:
gray = {3,2,1,2,1,2,3,2,3,2,1,2,1,2,3,2,3,2,1,2,1,2,3}
So we have vastly reduced the amount of work we have to do, from figuring the effect of 24 different rotations on a 2x2x2 polycube (and then a 3x3x3 polycube), to figuring the effect of just 3 different rotations on our cubes. Those three rotation functions could be stored in an array indexed by 0..3, and then applied like
nextConfiguration = currentConfiguration.Rotation[gray[i]]
(Note that we can even get all 48 reflection/rotations if we want, by following that sequence of rotations by a single reflection P (any reflection will do, so choose the simplest to implement), and then following that reflection by the gray sequence in reverse, which gives a Gray code for the full group of 48 reflection/rotations. (Building larger sequences by tacking the reverse of a sequence onto itself is one of the "big ideas" in the construction of Gray codes.))
We have come a long way without even considering the representation of the shapes that you want to rotate, but now we have to implement R1, R2, and R3 so we need to consider the data structure that represents the shapes, a 3 dimensional array. Let's consider the effect of R1, the 180 degree edge rotation on an axis through the midpoints of the 1-2 edges, on our 2x2x2 array:
(0,0,0) (1,0,0) (1,0,0) (0,0,0)
(0,1,0) (1,1,0) (0,0,1) (1,0,1) --> (1,0,1) (0,0,1) (1,1,0) (0,1,0)
(0,1,1) (1,1,1) (1,1,1) (0,1,1)
This tells us that our R1 operation can be implemented by
output(0,0,0) = input(1,0,0)
output(1,0,0) = input(0,0,0)
output(0,1,0) = input(1,0,1)
output(1,1,0) = input(0,0,1)
output(0,0,1) = input(1,1,0)
output(1,0,1) = input(0,1,0)
output(0,1,1) = input(1,1,1)
output(1,1,1) = input(0,1,1)
That defines the operation R1 in the 2x2x2 case. It should be clear how to define R2 and R3 in the 2x2x2 case, and also how to define those operations in the 3x3x3 case.
Let me finish by saying that the definition of the Ri operators is tedious and error prone, so we don't want to do it too much if we can help it. We can get away with defining only two operators, R1 (already defined above) and F, the front face rotation:
(0,0,0) (1,0,0) (0,1,0) (0,0,0)
(0,1,0) (1,1,0) (0,0,1) (1,0,1) --> (1,1,0) (1,0,0) (0,1,1) (0,0,1)
(0,1,1) (1,1,1) (1,1,1) (1,0,1)
Then we can represent R2 = F.F.F.R1.F (where . means "followed by"), and R3 = F.F.R1.F.F. (These are "conjugates" of R1.)
For the 3x3x3 case, it is some work to find the index tables by hand, so I have written a routine to do it, and then I found all 24 rotations of an alphabet cube. See code below. I'm sure it can be made much briefer by a Python expert. This is my first program in Python.
The idea is to rotate not the contents of the 3x3x3 array, but its indices.
import numpy as np
# polycube that we want to rotate
A = np.array([[['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', 'i']],
[['j', 'k', 'l'],
['m', '+', 'n'],
['o', 'p', 'q']],
[['r', 's', 't'],
['u', 'v', 'w'],
['x', 'y', 'z']]])
# I just do np.copy here because I don't know how to declare an array
T = np.copy(A)
# matrix representing top front edge rotation (12)
R1 = np.array([[-1, 0, 0],
[ 0, 0, 1],
[ 0, 1, 0]])
# matrix representing right front edge rotation (23)
R2 = np.array([[ 0, 0, 1],
[ 0,-1, 0],
[ 1, 0, 0]])
# matrix representing bottom front edge rotation (34)
R3 = np.array([[-1, 0, 0],
[ 0, 0,-1],
[ 0,-1, 0]])
# Gray code gives Hamiltonican circuit through cube rotation group
gray = [3,2,1,2,1,2,3,2,3,2,1,2,1,2,3,2,3,2,1,2,1,2,3]
# trick for speed: we only need to apply each rotation matrix once
# to this polycube of indices, then we use the result as a table of
# pointers to new positions of polycube after rotation
Idx0 = np.array([[[[0,0,0], [1,0,0], [2,0,0]],
[[0,1,0], [1,1,0], [2,1,0]],
[[0,2,0], [1,2,0], [2,2,0]]],
[[[0,0,1], [1,0,1], [2,0,1]],
[[0,1,1], [1,1,1], [2,1,1]],
[[0,2,1], [1,2,1], [2,2,1]]],
[[[0,0,2], [1,0,2], [2,0,2]],
[[0,1,2], [1,1,2], [2,1,2]],
[[0,2,2], [1,2,2], [2,2,2]]]])
# Again, copy array because I don't know how to declare
Idx1 = np.copy(Idx0)
Idx2 = np.copy(Idx0)
Idx3 = np.copy(Idx0)
# We have to subtract [1,1,1] then add it again to move the center of the
# indexes to [0,0,0]
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
Idx1[i,j,k] = np.matmul(np.array([i,j,k])-np.array([1,1,1]),R1) + \
np.array([1,1,1])
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
Idx2[i,j,k] = np.matmul(np.array([i,j,k])-np.array([1,1,1]),R2) + \
np.array([1,1,1])
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
Idx3[i,j,k] = np.matmul(np.array([i,j,k])-np.array([1,1,1]),R3) + \
np.array([1,1,1])
# note that we have done only 81 vector*matrix multiplications. Now we don't
# have to do any more; we just look up the result in the index tables Idx[123]
print(A)
# I'm sure there must be a more efficient way to move T (temp) into A
for g in gray:
if g == 1:
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
T[i,j,k] = A[Idx1[i,j,k,0],Idx1[i,j,k,1],Idx1[i,j,k,2]]
A = np.copy(T)
elif g == 2:
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
T[i,j,k] = A[Idx2[i,j,k,0],Idx2[i,j,k,1],Idx2[i,j,k,2]]
A = np.copy(T)
elif g == 3:
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
T[i,j,k] = A[Idx3[i,j,k,0],Idx3[i,j,k,1],Idx3[i,j,k,2]]
A = np.copy(T)
print("-----------------")
print(A)
Here is the output from the program
[[['a' 'b' 'c']
['d' 'e' 'f']
['g' 'h' 'i']]
[['j' 'k' 'l']
['m' '+' 'n']
['o' 'p' 'q']]
[['r' 's' 't']
['u' 'v' 'w']
['x' 'y' 'z']]]
-----------------
[[['z' 'w' 't']
['y' 'v' 's']
['x' 'u' 'r']]
[['q' 'n' 'l']
['p' '+' 'k']
['o' 'm' 'j']]
[['i' 'f' 'c']
['h' 'e' 'b']
['g' 'd' 'a']]]
-----------------
[[['x' 'o' 'g']
['y' 'p' 'h']
['z' 'q' 'i']]
[['u' 'm' 'd']
['v' '+' 'e']
['w' 'n' 'f']]
[['r' 'j' 'a']
['s' 'k' 'b']
['t' 'l' 'c']]]
-----------------
[[['r' 's' 't']
['j' 'k' 'l']
['a' 'b' 'c']]
[['u' 'v' 'w']
['m' '+' 'n']
['d' 'e' 'f']]
[['x' 'y' 'z']
['o' 'p' 'q']
['g' 'h' 'i']]]
-----------------
[[['a' 'd' 'g']
['j' 'm' 'o']
['r' 'u' 'x']]
[['b' 'e' 'h']
['k' '+' 'p']
['s' 'v' 'y']]
[['c' 'f' 'i']
['l' 'n' 'q']
['t' 'w' 'z']]]
-----------------
[[['c' 'l' 't']
['f' 'n' 'w']
['i' 'q' 'z']]
[['b' 'k' 's']
['e' '+' 'v']
['h' 'p' 'y']]
[['a' 'j' 'r']
['d' 'm' 'u']
['g' 'o' 'x']]]
-----------------
[[['i' 'h' 'g']
['f' 'e' 'd']
['c' 'b' 'a']]
[['q' 'p' 'o']
['n' '+' 'm']
['l' 'k' 'j']]
[['z' 'y' 'x']
['w' 'v' 'u']
['t' 's' 'r']]]
-----------------
[[['r' 'u' 'x']
['s' 'v' 'y']
['t' 'w' 'z']]
[['j' 'm' 'o']
['k' '+' 'p']
['l' 'n' 'q']]
[['a' 'd' 'g']
['b' 'e' 'h']
['c' 'f' 'i']]]
-----------------
[[['t' 'l' 'c']
['s' 'k' 'b']
['r' 'j' 'a']]
[['w' 'n' 'f']
['v' '+' 'e']
['u' 'm' 'd']]
[['z' 'q' 'i']
['y' 'p' 'h']
['x' 'o' 'g']]]
-----------------
[[['g' 'h' 'i']
['o' 'p' 'q']
['x' 'y' 'z']]
[['d' 'e' 'f']
['m' '+' 'n']
['u' 'v' 'w']]
[['a' 'b' 'c']
['j' 'k' 'l']
['r' 's' 't']]]
-----------------
[[['x' 'u' 'r']
['o' 'm' 'j']
['g' 'd' 'a']]
[['y' 'v' 's']
['p' '+' 'k']
['h' 'e' 'b']]
[['z' 'w' 't']
['q' 'n' 'l']
['i' 'f' 'c']]]
-----------------
[[['z' 'q' 'i']
['w' 'n' 'f']
['t' 'l' 'c']]
[['y' 'p' 'h']
['v' '+' 'e']
['s' 'k' 'b']]
[['x' 'o' 'g']
['u' 'm' 'd']
['r' 'j' 'a']]]
-----------------
[[['t' 's' 'r']
['w' 'v' 'u']
['z' 'y' 'x']]
[['l' 'k' 'j']
['n' '+' 'm']
['q' 'p' 'o']]
[['c' 'b' 'a']
['f' 'e' 'd']
['i' 'h' 'g']]]
-----------------
[[['c' 'f' 'i']
['b' 'e' 'h']
['a' 'd' 'g']]
[['l' 'n' 'q']
['k' '+' 'p']
['j' 'm' 'o']]
[['t' 'w' 'z']
['s' 'v' 'y']
['r' 'u' 'x']]]
-----------------
[[['a' 'j' 'r']
['b' 'k' 's']
['c' 'l' 't']]
[['d' 'm' 'u']
['e' '+' 'v']
['f' 'n' 'w']]
[['g' 'o' 'x']
['h' 'p' 'y']
['i' 'q' 'z']]]
-----------------
[[['z' 'y' 'x']
['q' 'p' 'o']
['i' 'h' 'g']]
[['w' 'v' 'u']
['n' '+' 'm']
['f' 'e' 'd']]
[['t' 's' 'r']
['l' 'k' 'j']
['c' 'b' 'a']]]
-----------------
[[['i' 'f' 'c']
['q' 'n' 'l']
['z' 'w' 't']]
[['h' 'e' 'b']
['p' '+' 'k']
['y' 'v' 's']]
[['g' 'd' 'a']
['o' 'm' 'j']
['x' 'u' 'r']]]
-----------------
[[['r' 'j' 'a']
['u' 'm' 'd']
['x' 'o' 'g']]
[['s' 'k' 'b']
['v' '+' 'e']
['y' 'p' 'h']]
[['t' 'l' 'c']
['w' 'n' 'f']
['z' 'q' 'i']]]
-----------------
[[['x' 'y' 'z']
['u' 'v' 'w']
['r' 's' 't']]
[['o' 'p' 'q']
['m' '+' 'n']
['j' 'k' 'l']]
[['g' 'h' 'i']
['d' 'e' 'f']
['a' 'b' 'c']]]
-----------------
[[['g' 'd' 'a']
['h' 'e' 'b']
['i' 'f' 'c']]
[['o' 'm' 'j']
['p' '+' 'k']
['q' 'n' 'l']]
[['x' 'u' 'r']
['y' 'v' 's']
['z' 'w' 't']]]
-----------------
[[['i' 'q' 'z']
['h' 'p' 'y']
['g' 'o' 'x']]
[['f' 'n' 'w']
['e' '+' 'v']
['d' 'm' 'u']]
[['c' 'l' 't']
['b' 'k' 's']
['a' 'j' 'r']]]
-----------------
[[['c' 'b' 'a']
['l' 'k' 'j']
['t' 's' 'r']]
[['f' 'e' 'd']
['n' '+' 'm']
['w' 'v' 'u']]
[['i' 'h' 'g']
['q' 'p' 'o']
['z' 'y' 'x']]]
-----------------
[[['t' 'w' 'z']
['l' 'n' 'q']
['c' 'f' 'i']]
[['s' 'v' 'y']
['k' '+' 'p']
['b' 'e' 'h']]
[['r' 'u' 'x']
['j' 'm' 'o']
['a' 'd' 'g']]]
-----------------
[[['g' 'o' 'x']
['d' 'm' 'u']
['a' 'j' 'r']]
[['h' 'p' 'y']
['e' '+' 'v']
['b' 'k' 's']]
[['i' 'q' 'z']
['f' 'n' 'w']
['c' 'l' 't']]]
fliplrandflipudare orientation-reversing so I know I can't use them on their own. I only want the orientation-preserving isometries (24 not 48). – Caribouaxesargument to the rot90 function which may simplify some of the code below – Caribou